11. 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
Logic
- Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, Jörg Würtz:
One Binary Horn Clause is Enough. 21-32 - François Laroussinie, Philippe Schnoebelen:
A Hierarchy of Temporal Logics with Past (Extended Abstract). 47-58 - 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 - Ioan I. Macarie:
Space-Efficient Deterministic Simulation of Probabilistic Automata (Extended Abstract). 109-122 - 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
Parallel Algorithms 1
- Marcin Kik, Miroslaw Kutylowski, Grzegorz Stachowiak:
Periodic Constant Depth Sorting Networks. 201-212 - Manfred Kunde, Rolf Niedermeier, Peter Rossmanith:
Faster Sorting and Routing on Grids with Diagonals. 225-236
Semantics and Specifications
- E. Pascal Gribomont, Jacques Hagelstein:
Reactive Variables for System Specification and Design. 275-286
Complexity: NC Hierarchy
- Carme Àlvarez, Birgit Jenner:
On Adaptive Dlogtime and Polylogtime Reductions (Extended Abstract). 301-312
Invited Lecture
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 - Dora Giammarresi, Antonio Restivo, Sebastian Seibert, Wolfgang Thomas:
Monadic Second-Order Logic Over Pictures and Recognizability by Tiling Systems. 365-375
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
Parallel Algorithms 2
- 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
Theory of Parallel Computation
- Vincent van Oostrom, Erik P. de Vink:
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 - Jeffrey Shallit, Yuri Breitbart:
Automaticity: Properties of a Measure of Descriptional Complexity. 619-630
Invited Lecture
Strings, Codes, Combinatorics
- Hiroki Arimura, Takeshi Shinohara, Setsuko Otsuki:
Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data. 649-660 - Vlado Dancík, Mike Paterson:
Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. 669-678
Efficient Algorithms
- 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