Fundamentals of Computation Theory: International Conference FCT '89, Szeged, Hungary, August 21-25, 1989. Proceedings (Lecture Notes in Computer Science, 380)

"This volume contains the proceedings of the conference on Fundamentals of Computation Theory held in Szeged, Hungary, August 21-25, 1989. The conference is the seventh in the series of the FCT conferences initiated in 1977 in Poznan-Kornik, Poland. The papers collected in this volume are the texts of invited contributions and shorter communications falling into one of the following sections: - Efficient Computation by Abstract Devices: Automata, Computability, Probabilistic Computations, Parallel and Distributed Computing; - Logics and Meanings of Programs: Algebraic and Categorical Approaches to Semantics, Computational Logic, Logic Programming, Verification, Program Transformations, Functional Programming; - Formal Languages: Rewriting Systems, Algebraic Language Theory; - Computational Complexity: Analysis and Complexity of Algorithms, Design of Efficient Algorithms, Algorithms and Data Structures, Computational Geometry, Complexity Classes and Hierarchies, Lower Bounds."--Publisher's website On word equations and Makanin's algorithm....Pages 1-12 Complexity classes with complete problems between P and NP-C....Pages 13-24 Interpretations of synchronous flowchart schemes....Pages 25-34 Generalized Boolean hierarchies and Boolean hierarchies over RP....Pages 35-46 The equational logic of iterative processes....Pages 47-57 The distributed bit complexity of the ring: From the anonymous to the non-anonymous case....Pages 58-67 The jump number problem for biconvex graphs and rectangle covers of rectangular regions....Pages 68-77 Recent developments in the design of asynchronous circuits....Pages 78-94 New simulations between CRCW PRAMs....Pages 95-104 About connections between syntactical and computational complexity....Pages 105-115 Completeness in approximation classes....Pages 116-126 Separating completely complexity classes related to polynomial size Ω-Decision trees....Pages 127-136 On product hierarchies of automata....Pages 137-144 On the communication complexity of planarity....Pages 145-147 Context-free NCE graph grammars....Pages 148-161 Dynamic data structures with finite population: A combinatorial analysis....Pages 162-174 Iterated deterministic top-down look-ahead....Pages 175-184 Using generating functions to compute concurrency....Pages 185-196 A logic for nondeterministic functional programs extended abstract....Pages 197-208 Decision problems and Coxeter groups....Pages 209-223 Complexity of formula classes in first order logic with functions....Pages 224-233 Normal and sinkless Petri nets....Pages 234-243 Descriptive and computational complexity....Pages 244-245 The effect of null-chains on the complexity of contact schemes....Pages 246-256 Monte-Carlo inference and its relations to reliable frequency identification....Pages 257-266 Semilinear real-time systolic trellis automata....Pages 267-276 Inducibility of the composition of frontier-to-root tree transformations....Pages 277-286 On oblivious branching programs of linear length....Pages 287-296 Some time-space bounds for one-tape deterministic turing machines....Pages 297-307 Rank of rational finitely generated W-languages....Pages 308-317 Extensional properties of sets of time bounded complexity (extended abstract)....Pages 318-326 Learning under uniform distribution....Pages 327-338 An extended framework for default reasoning....Pages 339-348 Logic programming of some mathematical paradoxes....Pages 349-361 Analysis of compact 0-complete trees: A new access method to large databases....Pages 362-371 Representation of recursively enumerable languages using alternating finite tree recognizers....Pages 372-383 About a family of binary morphisms which stationary words are Sturmian....Pages 384-394 On the finite degree of ambiguity of finite tree automata....Pages 395-404 Approximation algorithms for channel assignment in cellular radio networks....Pages 405-415 The Borel hierarchy is infinite in the class of regular sets of trees....Pages 416-423 Parallel general prefix computations with geometric, algebraic and other applications....Pages 424-433 Kolmogorov complexity and Hausdorff dimension....Pages 434-443 Tree language problems in pattern recognition theory....Pages 444-450 The computational complexity of cellular automata....Pages 451-459 On restricted Boolean circuits....Pages 460-469 The complexity of connectivity problems on context-free graph languages....Pages 470-479 Constructivity, computability, and computational complexity in analysis....Pages 480-493 Annotation This volume contains the proceedings of the conference on Fundamentals of Computation Theory held in Szeged, Hungary, August 21-25, 1989. The conference is the seventh in the series of the FCT conferences initiated in 1977 in Poznan-Kornik, Poland. The papers collected in this volume are the texts of invited contributions and shorter communications falling into one of the following sections: - Efficient Computation by Abstract Devices: Automata, Computability, Probabilistic Computations, Parallel and Distributed Computing; - Logics and Meanings of Programs: Algebraic and Categorical Approaches to Semantics, Computational Logic, Logic Programming, Verification, Program Transformations, Functional Programming; - Formal Languages: Rewriting Systems, Algebraic Language Theory; - Computational Complexity: Analysis and Complexity of Algorithms, Design of Efficient Algorithms, Algorithms and Data Structures, Computational Geometry, Complexity Classes and Hierarchies, Lower Bounds