Lecture Notes in Computer Science, Volume 380: Fundamentals of Computation Theory, FCT '89, Proceedings, 21-25 August 1989, Szeged, Hungary

Csrik, J; Demetrovics, J.; Gecseg, F. (Editors)

ISBN 10: 3540514988 / ISBN 13: 9783540514985

Editore: Springer-Verlag, Berlin, Germany, 1988

Riguardo questo articolo

w/full markings, pocket, and/or bookplate. Wear, soil. slight Wave to pages from improper storage. 493 numbered pages. Size: 8vo.

Codice articolo 015943

Dati bibliografici

• Titolo: Lecture Notes in Computer Science, Volume 380: Fundamentals of Computation Theory, FCT '89, Proceedings, 21-25 August 1989, Szeged, Hungary
• Editore: Springer-Verlag, Berlin, Germany
• Data di pubblicazione: 1988
• Lingua: Inglese
• ISBN 10: 3540514988
• ISBN 13: 9783540514985
• Rilegatura: Paperback
• Edizione: 1st.
• Condizione: Good
• Condizione della sovraccoperta: No Jacket
• Tipo di libro: Ex-Library
• Cataloghi dei venditori:
  • ARTIFICIAL INTELLIGENCE
  • COMPUTERS
  • PROGRAMMING

Descrizione articolo

Riassunto

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.

Contenuti

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.