+612 9045 4394
Fundamentals of Computation Theory : 11th International Symposium, Fct '97, Krakow, Poland, September 1-3, 1997. Proceedings - Bogdan S. Chlebus

Fundamentals of Computation Theory

11th International Symposium, Fct '97, Krakow, Poland, September 1-3, 1997. Proceedings

By: Bogdan S. Chlebus (Editor), Ludwik Czaja (Editor)


Published: 6th August 1997
Ships: 15 business days
15 business days
or 4 easy payments of $37.09 with Learn more

This book constitutes the refereed proceedings of the 11th International Symposium on Fundamentals of Computer Theory, FCT'97, held in Krakow, Poland, in September 1997.
The 34 revised full papers presented in the volume were selected from a total of 72 submissions. Also included are six invited papers by leading scientists. The papers address a variety of current topics in theoretical computer science including models of computation, concurrency, algorithms, complexity theory, programming theory, formal languages, graph theory and discrete mathematics, networking, automata theory, term rewriting, etc.

The Complexity Class [Theta][actual symbol not reproducible]: Recent Results and Applications in AI and Modal Logicp. 1
Proof Systems for Structured Algebraic Specifications: An Overviewp. 19
Average-Case Analysis via Incompressibilityp. 38
Locally Computable Enumerationsp. 51
The Complexity of Error-Correcting Codesp. 67
Stochastic Analysis of Dynamic Processesp. 85
k-k Sorting on the Multi-Meshp. 93
Refinement of Coloured Petri Netsp. 105
Stratified Petri Netsp. 117
Distributed Acyclic Orientation of Asynchronous Anonymous Networksp. 129
Generalized Rational Relations and their Logical Definabilityp. 138
A Note on Broadcasting with Linearly Bounded Transmission Faults in Constant Degree Networksp. 150
Logics which Capture Complexity Classes over the Realsp. 157
Criteria to Disprove Context-Freeness of Collage Languagesp. 169
The Subword Complexity of Fixed Points of Binary Uniform Morphismsp. 179
Efficient Parallel Computing with Memory Faultsp. 188
Bounded Concurrencyp. 198
Concerning the Time Bounds of Existing Shortest Watchman Route Algorithmsp. 210
Query Order in the Polynomial Hierarchyp. 222
Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteriap. 233
Pattern-Matching Problems for 2-Dimensional Images Described by Finite Automatap. 245
The Complexity of the Coverability, the Containment, and the Equivalence Problems for Commutative Semigroupsp. 257
Contextual Grammars with Distributed Catenation and Shufflep. 269
A Two-Dimensional Hierarchy for Attributed Tree Transducersp. 281
Synchronization of 1-Way Connected Processorsp. 293
A Linear-Time Heuristic for Minimum Rectangular Coveringsp. 305
On Occurrence Net Semantics for Petri Nets with Contactsp. 317
Cellular Automata Universality Revisitedp. 329
Trade-Off Results of Connection Managementp. 340
On the Average Complexity of the Membership Problem for a Generalized Dyck Languagep. 352
Towards Optimal Locality in Mesh-Indexingsp. 364
On the Hierarchy of Nondeterministic Branching k-programsp. 376
FDT Is Undecidable for Finitely Presented Monoids with Solvable Word Problemsp. 388
The Equivalence of Pebbles and Sensing Heads for Finite Automatap. 400
From Finite Automata toward Hybrid Systemsp. 411
On an Optimal Quantified Propositional Proof System and a Complete Language for NP [actual symbol not reproducible] co-NPp. 423
Lower Bounds in On-Line Geometric Searchingp. 429
The Complexity of Universal Text-Learnersp. 441
Unique Normal Forms for Nonlinear Term Rewriting Systems: Root Overlapsp. 452
Behavioural Characterisations of Partial Order Logicsp. 463
Author Indexp. 475
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540633860
ISBN-10: 3540633863
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 484
Published: 6th August 1997
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 2.54
Weight (kg): 0.69