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.
Author(s): Habib Abdulrab, Jean-Pierre Pécuchet (auth.), J. Csirik, J. Demetrovics, F. Gécseg (eds.)
Series: Lecture Notes in Computer Science 380
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1989
Language: English
Pages: 498
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Control Structures and Microprogramming; Combinatorics
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
