11. STACS 1994: Caen, France

Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner (Eds.): 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

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, Jörg Würtz:
One Binary Horn Clause is Enough. 21-32
N. Bensaou, Irène Guessarian:
Transforming Constraint Logic Programs. 33-46
François Laroussinie, Ph. 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

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

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

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

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

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

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, Giovanna Guaiana:
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

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

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

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

Joachim Parrow, Peter Sjödin:
The Complete Axiomatization of Cs-congruence. 557-568
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

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 Shallit, Yuri Breitbart:
Automaticity: Properties of a Measure of Descriptional Complexity. 619-630

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
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
H. 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

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, Klaus Jansen:
On the Complexity of the Maximum Cut Problem. 769-780