Fundamentals of Computation Theory
International Conference FCT '89, Szeged, Hungary, August 21-25, 1989. Proceedings
Published on 31. July 1989
Book
Paperback/Softback
XIV, 498 pages
978-3-540-51498-5 (ISBN)
Description
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.
More details
Series
Edition
1989 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XIV, 498 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 28 mm
Weight
774 gr
ISBN-13
978-3-540-51498-5 (9783540514985)
DOI
10.1007/3-540-51498-8
Schweitzer Classification
Content
On word equations and Makanin's algorithm.- Complexity classes with complete problems between P and NP-C.- Interpretations of synchronous flowchart schemes.- Generalized Boolean hierarchies and Boolean hierarchies over RP.- The equational logic of iterative processes.- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case.- The jump number problem for biconvex graphs and rectangle covers of rectangular regions.- Recent developments in the design of asynchronous circuits.- New simulations between CRCW PRAMs.- About connections between syntactical and computational complexity.- Completeness in approximation classes.- Separating completely complexity classes related to polynomial size ?-Decision trees.- On product hierarchies of automata.- On the communication complexity of planarity.- Context-free NCE graph grammars.- Dynamic data structures with finite population: A combinatorial analysis.- Iterated deterministic top-down look-ahead.- Using generating functions to compute concurrency.- A logic for nondeterministic functional programs extended abstract.- Decision problems and Coxeter groups.- Complexity of formula classes in first order logic with functions.- Normal and sinkless Petri nets.- Descriptive and computational complexity.- The effect of null-chains on the complexity of contact schemes.- Monte-Carlo inference and its relations to reliable frequency identification.- Semilinear real-time systolic trellis automata.- Inducibility of the composition of frontier-to-root tree transformations.- On oblivious branching programs of linear length.- Some time-space bounds for one-tape deterministic turing machines.- Rank of rational finitely generated W-languages.- Extensional properties of sets of time bounded complexity (extendedabstract).- Learning under uniform distribution.- An extended framework for default reasoning.- Logic programming of some mathematical paradoxes.- Analysis of compact 0-complete trees: A new access method to large databases.- Representation of recursively enumerable languages using alternating finite tree recognizers.- About a family of binary morphisms which stationary words are Sturmian.- On the finite degree of ambiguity of finite tree automata.- Approximation algorithms for channel assignment in cellular radio networks.- The Borel hierarchy is infinite in the class of regular sets of trees.- Parallel general prefix computations with geometric, algebraic and other applications.- Kolmogorov complexity and Hausdorff dimension.- Tree language problems in pattern recognition theory.- The computational complexity of cellular automata.- On restricted Boolean circuits.- The complexity of connectivity problems on context-free graph languages.- Constructivity, computability, and computational complexity in analysis.