11. FCT 1997: Kraków, Poland

@proceedings{DBLP:conf/fct/1997,
  editor    = {Bogdan S. Chlebus and
               Ludwik Czaja},
  title     = {Fundamentals of Computation Theory, 11th International Symposium,
               FCT '97, Krak{\'o}w, Poland, September 1-3, 1997, Proceedings},
  booktitle = {FCT},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1279},
  year      = {1997},
  isbn      = {3-540-63386-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Lectures

• Thomas Eiter, Georg Gottlob: The Complexity Class Theta₂^p: Recent Results and Applications in AI and Modal Logic. 1-18 BibTeX
• Rolf Hennicker, Martin Wirsing: Proof Systems for Struvtured Algebraic Specifications: An Overview. 19-37 BibTeX
• Ming Li, Paul M. B. Vitányi: Average-Case Analysis via Incompressibility. 38-50 BibTeX
• Antoni W. Mazurkiewicz: Locally Computable Enumerations. 51-66 BibTeX
• Daniel A. Spielman: The Complexity of Error-Correcting Codes. 67-84 BibTeX
• Eli Upfal: Stochastic Analysis of Dynamic Processes. 85-92 BibTeX

Technical Contributions

• Alfons Avermiddig, Manfred Kunde, Andre Osterloh: k-k Sorting on the Multi-Mesh. 93-104 BibTeX
• Eike Best, Thomas Thielke: Refinement of Coloured Petri Nets. 105-116 BibTeX
• Eric Badouel, Philippe Darondeau: Stratified Petri Nets. 117-128 BibTeX
• Antonio Calabrese: Distributed Acyclic Orientation of Asynchronous Networks. 129-137 BibTeX
• Christian Choffrut, Leucio Guerra: Generalized Rational Relations and their Logical Definability. 138-149 BibTeX
• Krzysztof Ciebiera, Adam Malinowski: A Note on Broadcasting with Linearly Bounded Transmission Faults in Constant Degree Networks. 150-156 BibTeX
• Felipe Cucker, Klaus Meer: Logics Which Capture Complexity Classes over the Reals. 157-167 BibTeX
• Frank Drewes, Hans-Jörg Kreowski, Denis Lapoire: Criteria to Disprove Context-Freeness of Collage Languages. 169-178 BibTeX
• Anna E. Frid: The Subword Complexity of Fixed Points of Binary Uniform Morphisms. 179-187 BibTeX
• Leszek Gasieniec, Piotr Indyk: Efficient Parallel Computing with Memory Faults. 188-197 BibTeX
• Damas P. Gruska: Bounded Concurrency. 198-209 BibTeX
• Mikael Hammar, Bengt J. Nilsson: Concerning the Time Bounds of Existing Shortest Watchman Route Algorithms. 210-221 BibTeX
• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order in the Polynomial Hierarchy. 222-232 BibTeX
• Ulrich Hertrampf: Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteria. 233-244 BibTeX
• Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter: Pattern-Matching Problems for 2-Dimensional Images Described by Finite Automata. 245-256 BibTeX
• Ulla Koppenhagen, Ernst W. Mayr: The Complexity of the Coverability, the Containment, and the Equivalence Problems for Commutative Semigroups. 257-268 BibTeX
• Manfred Kudlek, Solomon Marcus, Alexandru Mateescu: Contextual Grammars with Distributed Catenation and Shuffle. 269-280 BibTeX
• Armin Kühnemann: A Two-Dimensional Hierarchy for Attributed Tree Transducers. 281-292 BibTeX
• Salvatore La Torre, Margherita Napoli, Mimmo Parente: Synchronization of 1-Way Connected Processors. 293-304 BibTeX
• Christos Levcopoulos, Joachim Gudmundsson: A Linear-Time Heuristic for Minimum Rectangular Coverings (Extended Abstract). 305-316 BibTeX
• Irina A. Lomazova: On Occurrence Net Semantics for Petri Nets with Contacts. 317-328 BibTeX
• Bruno Martin: Cellular Automata Universality Revisited. 329-339 BibTeX
• Marios Mavronicolas, Nikos Papadakis: Trade-Off Results for Connection Management. 340-351 BibTeX
• Markus E. Nebel: On the Average Complexity of the Membership Problem for a Generalized Dyck Language. 352-363 BibTeX
• Rolf Niedermeier, Klaus Reinhardt, Peter Sanders: Towards Optimal Locality in Mesh-Indexings. 364-375 BibTeX
• Elizaveta A. Okol'nishnikova: On the Hierarchy of Nondeterministic Branching k-Programs. 376-387 BibTeX
• Friedrich Otto, Andrea Sattler-Klein: FDT is Undecidable for Finitely Presented Monoids with Solvable Word Problems. 388-399 BibTeX
• H. Petersen: The Equivalence of Pebbles and Sensing Heads for Finite Automata. 400-410 BibTeX
• Alexander Moshe Rabinovich, Boris A. Trakhtenbrot: From Finite Automata toward Hybrid Systems (Extended Abstract). 411-422 BibTeX
• Zenon Sadowski: On an Optimal Quantified Propositional Proof System and a Complete Language for NP cap co-NP. 423-428 BibTeX
• Sven Schuierer: Lower Bounds in On-Line Geometric Searching. 429-440 BibTeX
• Frank Stephan, Sebastiaan Terwijn: The Complexity of Universal Text-Learners. 441-451 BibTeX
• Rakesh M. Verma: Unique Normal Forms for Nonlinear Term Rewriting Systems: Root Overlaps. 452-462 BibTeX
• Irina Virbitskaite, Anzhelika Votintseva: Behavioural Characterizations of Partial Order Logics. 463-474 BibTeX