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 BibTeX

@proceedings{DBLP:conf/stacs/1994,
  editor    = {Patrice Enjalbert and
               Ernst W. Mayr and
               Klaus W. Wagner},
  title     = {STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer
               Science, Caen, France, February 24-26, 1994, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {775},
  year      = {1994},
  isbn      = {3-540-57785-8},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Lecture

Raimund Seidel: The Nature and Meaning of Perturbations in Geometric Computing. 3-17 BibTeX

Logic

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, Jörg Würtz: One Binary Horn Clause is Enough. 21-32 BibTeX
N. Bensaou, Irène Guessarian: Transforming Constraint Logic Programs. 33-46 BibTeX
François Laroussinie, Ph. Schnoebelen: A Hierarchy of Temporal Logics with Past (Extended Abstract). 47-58 BibTeX
Jean Goubault: The Complexity of Resource-Bounded First-Order Classical Logic. 59-70 BibTeX
Belaid Benhamou, Lakhdar Sais, Pierre Siegel: Two Proof Procedures for a Cardinality Based Language in Propositional Calculus. 71-82 BibTeX

Complexity Classes

Burchard von Braunmühl, Romain Gengler, Robert Rettinger: The Alternation Hierarchy for Machines with Sublogarithmic Space is Infinite. 85-96 BibTeX
Ashish V. Naik, Kenneth W. Regan, D. Sivakumar: Quasilinear Time Complexity Theory. 97-108 BibTeX
Ioan I. Macarie: Space-Efficient Deterministic Simulation of Probabilistic Automata (Extended Abstract). 109-122 BibTeX
Kousha Etessami, Neil Immerman: Reachability and the Power of Local Ordering. 123-135 BibTeX
Louis Mak: Are Parallel Machines Always Faster than Sequential Machines? (Preliminary Version). 137-148 BibTeX

Term Rewriting and Unification

Hubert Comon, Florent Jacquemard: Ground Reducibility and Automata with Disequality Constraints. 151-162 BibTeX
Zurab Khasidashvili: Perpetuality and Strong Normalization in Orthogonal Term Rewriting Systems. 163-174 BibTeX
Andrea Sattler-Klein: About Changing the Ordering During Knuth-Bendix Completion. 175-186 BibTeX
Christophe Ringeissen: Combination of Matching Algorithms. 187-198 BibTeX

Parallel Algorithms 1

Marcin Kik, Miroslaw Kutylowski, Grzegorz Stachowiak: Periodic Constant Depth Sorting Networks. 201-212 BibTeX
Bogdan S. Chlebus, Leszek Gasieniec: Optimal Pattern Matching on Meshes. 213-224 BibTeX
Manfred Kunde, Rolf Niedermeier, Peter Rossmanith: Faster Sorting and Routing on Grids with Diagonals. 225-236 BibTeX
Jop F. Sibeyn, Michael Kaufmann: Deterministic 1-k Routing on Meshes. 237-248 BibTeX

Semantics and Specifications

Martin Hofmann, Benjamin C. Pierce: A Unifying Type-Theoretic Framework for Objects. 251-262 BibTeX
Jürgen Avenhaus, Klaus Becker: Operational Specifications with Built-Ins. 263-274 BibTeX
E. Pascal Gribomont, Jacques Hagelstein: Reactive Variables for System Specification and Design. 275-286 BibTeX

Complexity: NC Hierarchy

Kenneth W. Regan: A New Parallel Vector Model, with Exact Characterization of NC^k. 289-300 BibTeX
Carme Àlvarez, Birgit Jenner: On Adaptive Dlogtime and Polylogtime Reductions (Extended Abstract). 301-312 BibTeX
Mitsunori Ogiwara: NC^k(NP) = AC^(k-1)(NP). 313-324 BibTeX

Invited Lecture

André Arnold: Hypertransition Systems. 327-338 BibTeX

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 BibTeX
Véronique Bruyère, Clelia de Felice, Giovanna Guaiana: Coding with Traces. 353-364 BibTeX
Dora Giammarresi, Antonio Restivo, Sebastian Seibert, Wolfgang Thomas: Monadic Second-Order Logic Over Pictures and Recognizability by Tiling Systems. 365-375 BibTeX
Maylis Delest, Jean-Philippe Dubernard: q-Grammars: Results, Implementation. 377-388 BibTeX
Georg Karner: A Topology for Complete Semirings. 389-400 BibTeX

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 BibTeX
Jack H. Lutz, Elvira Mayordomo: Cook Versus Karp-Levin: Separating Completeness Notions if NP Is not Small (Extended Abstract). 415-426 BibTeX
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-selective Sets. 427-438 BibTeX
Victor L. Selivanov: Two Refinements of the Polynomial Hierarcht. 439-448 BibTeX
Heribert Vollmer: On Different Reducibility Notions for Function Classes. 449-460 BibTeX

Parallel Algorithms 2

Michael Luby, Wolfgang Ertel: Optimal Parallelization of Las Vegas Algorithms. 463-474 BibTeX
Amitava Datta: Efficient Parallel Algorithms for Geometric k-Clustering Problems. 475-486 BibTeX
Anil Maheshwari, Andrzej Lingas: A Simple Optimal Parallel Algorithm for Reporting Paths in a Tree. 487-495 BibTeX
Alberto Apostolico, Dany Breslauer, Zvi Galil: Parallel Detection of all Palindromes in a String. 497-506 BibTeX

Computational Complexity

Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows: On the Structure of Parameterized Problems in NP (Extended Abstract). 509-520 BibTeX
Edoardo Amaldi, Viggo Kann: On the Approximability of Finding Maximum Feasible Subsystems of Linear Systems. 521-532 BibTeX
Bernd Borchert: On the Acceptance Power of Regular Languages. 533-541 BibTeX
Ulrich Hertrampf: Complexity Classes with Finite Acceptance Types. 543-553 BibTeX

Theory of Parallel Computation

Joachim Parrow, Peter Sjödin: The Complete Axiomatization of Cs-congruence. 557-568 BibTeX
Vincent van Oostrom, Erik P. de Vink: Transition System Specifications in Stalk Formal with Bisimulation as a Congruence. 569-580 BibTeX
Petr Jancar: Decidability Questions for Bismilarity of Petri Nets and Some Related Problems. 581-592 BibTeX

Formal Languages and Complexity

Gerhard Buntrock, Krzysztof Lorys: The Variable Membership Problem: Succinctness Versus Complexity. 595-606 BibTeX
Andreas Weber, Reinhard Klemm: Economy of Description for Single-valued Transducers. 607-618 BibTeX
Jeffrey Shallit, Yuri Breitbart: Automaticity: Properties of a Measure of Descriptional Complexity. 619-630 BibTeX

Invited Lecture

David Harel: Towards a Theory of Recursive Structures. 633-645 BibTeX

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 BibTeX
Alexandru Mateescu, Arto Salomaa: Nondeterminism in Patterns. 661-668 BibTeX
Vlado Dancík, Mike Paterson: Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. 669-678 BibTeX
H. Petersen: The Ambiguity of Primitive Words. 679-690 BibTeX
Nguyen Huong Lam: On Codes Having no Finite Completion. 691-698 BibTeX
Richard J. Lipton: A New Approach To Information Theory. 699-708 BibTeX

Efficient Algorithms

Ngoc-Minh Lê: On Voronoi Diagrams in the L_p-Metric in Higher Dimensions. 711-722 BibTeX
Ming-Yang Kao: Total Protection of Analytic Invariant Information in Cross Tabulated Tables. 723-734 BibTeX
Feodor F. Dragan, Andreas Brandstädt: Dominating Cliques in Graphs with Hypertree Structures. 735-746 BibTeX
Jitender S. Deogun, Ton Kloks, Dieter Kratsch, Haiko Müller: On Vertex Ranking for Permutations and Other Graphs. 747-758 BibTeX
Ton Kloks, Dieter Kratsch: Finding All Minimal Separators of a Graph. 759-768 BibTeX
Hans L. Bodlaender, Klaus Jansen: On the Complexity of the Maximum Cut Problem. 769-780 BibTeX