Fundamentals of Computation Theory [electronic resource] : International Conference FCT '89 Szeged, Hungary, August 21–25, 1989 Proceedings / edited by J. Csirik, J. Demetrovics, F. Gécseg.Material type: TextLanguage: English Series: Lecture Notes in Computer Science: 380Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg, 1989Description: XIV, 498 p. online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783540481805Subject(s): Computer science | Microprogramming | Computer software | Logic design | Combinatorics | Computer Science | Computation by Abstract Devices | Algorithm Analysis and Problem Complexity | Logics and Meanings of Programs | Mathematical Logic and Formal Languages | Control Structures and Microprogramming | CombinatoricsAdditional physical formats: Printed edition:: No titleDDC classification: 004.0151 LOC classification: QA75.5-76.95Online resources: Click here to access online
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 (extended abstract) -- 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.
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.