Fundamentals of Computation Theory: International Conference FCT ’89 Szeged, Hungary, August 21–25, 1989 Proceedings

Habib Abdulrab, Jean-Pierre Pécuchet (auth.), J. Csirik, J. Demetrovics, F. Gécseg (eds.)3540514988, 9783540514985

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.

---

Table of contents :
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