default search action
11th STACS 1994: Caen, France
- Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner:
STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings. Lecture Notes in Computer Science 775, Springer 1994, ISBN 3-540-57785-8
Invited Lecture
- Raimund Seidel:
The Nature and Meaning of Perturbations in Geometric Computing. 3-17
Logic
- Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, Jörg Würtz:
One Binary Horn Clause is Enough. 21-32 - Nacéra Bensaou, Irène Guessarian:
Transforming Constraint Logic Programs. 33-46 - François Laroussinie, Philippe Schnoebelen:
A Hierarchy of Temporal Logics with Past (Extended Abstract). 47-58 - Jean Goubault:
The Complexity of Resource-Bounded First-Order Classical Logic. 59-70 - Belaid Benhamou, Lakhdar Sais, Pierre Siegel:
Two Proof Procedures for a Cardinality Based Language in Propositional Calculus. 71-82
Complexity Classes
- Burchard von Braunmühl, Romain Gengler, Robert Rettinger:
The Alternation Hierarchy for Machines with Sublogarithmic Space is Infinite. 85-96 - Ashish V. Naik, Kenneth W. Regan, D. Sivakumar:
Quasilinear Time Complexity Theory. 97-108 - Ioan I. Macarie:
Space-Efficient Deterministic Simulation of Probabilistic Automata (Extended Abstract). 109-122 - Kousha Etessami, Neil Immerman:
Reachability and the Power of Local Ordering. 123-135 - Louis Mak:
Are Parallel Machines Always Faster than Sequential Machines? (Preliminary Version). 137-148
Term Rewriting and Unification
- Hubert Comon, Florent Jacquemard:
Ground Reducibility and Automata with Disequality Constraints. 151-162 - Zurab Khasidashvili:
Perpetuality and Strong Normalization in Orthogonal Term Rewriting Systems. 163-174 - Andrea Sattler-Klein:
About Changing the Ordering During Knuth-Bendix Completion. 175-186 - Christophe Ringeissen:
Combination of Matching Algorithms. 187-198
Parallel Algorithms 1
- Marcin Kik, Miroslaw Kutylowski, Grzegorz Stachowiak:
Periodic Constant Depth Sorting Networks. 201-212 - Bogdan S. Chlebus, Leszek Gasieniec:
Optimal Pattern Matching on Meshes. 213-224 - Manfred Kunde, Rolf Niedermeier, Peter Rossmanith:
Faster Sorting and Routing on Grids with Diagonals. 225-236 - Jop F. Sibeyn, Michael Kaufmann:
Deterministic 1-k Routing on Meshes. 237-248
Semantics and Specifications
- Martin Hofmann, Benjamin C. Pierce:
A Unifying Type-Theoretic Framework for Objects. 251-262 - Jürgen Avenhaus, Klaus Becker:
Operational Specifications with Built-Ins. 263-274 - E. Pascal Gribomont, Jacques Hagelstein:
Reactive Variables for System Specification and Design. 275-286
Complexity: NC Hierarchy
- Kenneth W. Regan:
A New Parallel Vector Model, with Exact Characterization of NC^k. 289-300 - Carme Àlvarez, Birgit Jenner:
On Adaptive Dlogtime and Polylogtime Reductions (Extended Abstract). 301-312 - Mitsunori Ogiwara
:
NC^k(NP) = AC^(k-1)(NP). 313-324
Invited Lecture
- André Arnold:
Hypertransition Systems. 327-338
Formal Languages
- Yves Métivier, Gwénaël Richomme:
On the Star Operation and the Finite Power Property in Free Partially Commutative Monoids (Extended Abstract). 341-352 - Véronique Bruyère, Clelia de Felice
Coding with Traces. 353-364 - Dora Giammarresi, Antonio Restivo, Sebastian Seibert, Wolfgang Thomas:
Monadic Second-Order Logic Over Pictures and Recognizability by Tiling Systems. 365-375 - Maylis Delest, Jean-Philippe Dubernard:
q-Grammars: Results, Implementation. 377-388 - Georg Karner:
A Topology for Complete Semirings. 389-400
Structural Complexity and Recursivity
- Ronald V. Book, Jack H. Lutz, David M. Martin Jr.:
The Global Power of Additional Queries to Random Oracles. 403-414 - Jack H. Lutz, Elvira Mayordomo:
Cook Versus Karp-Levin: Separating Completeness Notions if NP Is not Small (Extended Abstract). 415-426 - Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-selective Sets. 427-438 - Victor L. Selivanov:
Two Refinements of the Polynomial Hierarcht. 439-448 - Heribert Vollmer:
On Different Reducibility Notions for Function Classes. 449-460
Parallel Algorithms 2
- Michael Luby, Wolfgang Ertel
Optimal Parallelization of Las Vegas Algorithms. 463-474 - Amitava Datta
Efficient Parallel Algorithms for Geometric k-Clustering Problems. 475-486 - Anil Maheshwari, Andrzej Lingas:
A Simple Optimal Parallel Algorithm for Reporting Paths in a Tree. 487-495 - Alberto Apostolico, Dany Breslauer, Zvi Galil:
Parallel Detection of all Palindromes in a String. 497-506
Computational Complexity
- Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows:
On the Structure of Parameterized Problems in NP (Extended Abstract). 509-520 - Edoardo Amaldi, Viggo Kann:
On the Approximability of Finding Maximum Feasible Subsystems of Linear Systems. 521-532 - Bernd Borchert:
On the Acceptance Power of Regular Languages. 533-541 - Ulrich Hertrampf:
Complexity Classes with Finite Acceptance Types. 543-553
Theory of Parallel Computation
- Joachim Parrow, Peter Sjödin:
The Complete Axiomatization of Cs-congruence. 557-568 - Vincent van Oostrom
Transition System Specifications in Stalk Formal with Bisimulation as a Congruence. 569-580 - Petr Jancar
Decidability Questions for Bismilarity of Petri Nets and Some Related Problems. 581-592
Formal Languages and Complexity
- Gerhard Buntrock, Krzysztof Lorys:
The Variable Membership Problem: Succinctness Versus Complexity. 595-606 - Andreas Weber, Reinhard Klemm:
Economy of Description for Single-valued Transducers. 607-618 - Jeffrey O. Shallit, Yuri Breitbart:
Automaticity: Properties of a Measure of Descriptional Complexity. 619-630
Invited Lecture
- David Harel:
Towards a Theory of Recursive Structures. 633-645
Strings, Codes, Combinatorics
- Hiroki Arimura
Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data. 649-660 - Alexandru Mateescu, Arto Salomaa:
Nondeterminism in Patterns. 661-668 - Vlado Dancík, Mike Paterson:
Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. 669-678 - Holger Petersen:
The Ambiguity of Primitive Words. 679-690 - Nguyen Huong Lam:
On Codes Having no Finite Completion. 691-698 - Richard J. Lipton:
A New Approach To Information Theory. 699-708
Efficient Algorithms
- Ngoc-Minh Lê:
On Voronoi Diagrams in the L_p-Metric in Higher Dimensions. 711-722 - Ming-Yang Kao:
Total Protection of Analytic Invariant Information in Cross Tabulated Tables. 723-734 - Feodor F. Dragan, Andreas Brandstädt:
Dominating Cliques in Graphs with Hypertree Structures. 735-746 - Jitender S. Deogun, Ton Kloks, Dieter Kratsch, Haiko Müller
On Vertex Ranking for Permutations and Other Graphs. 747-758 - Ton Kloks, Dieter Kratsch:
Finding All Minimal Separators of a Graph. 759-768 - Hans L. Bodlaender
On the Complexity of the Maximum Cut Problem. 769-780
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-23 19:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: