Fundamentals of Computation Theory

International Conference FCT '89, Szeged, Hungary, August 21-25, 1989. Proceedings

Janos Csirik, Ferenc Gecseg, Janos Demetrovics (Herausgeber)

Buch | Softcover

XIV, 498 Seiten

1989
Springer Berlin (Verlag)
9783540514985 (ISBN)

Artikel merken

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.

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.

Erscheint lt. Verlag	31.7.1989
Reihe/Serie	Lecture Notes in Computer Science
Zusatzinfo	XIV, 498 p.
Verlagsort	Berlin
Sprache	englisch
Maße	216 x 279 mm
Gewicht	712 g
Themenwelt	Informatik ► Software Entwicklung ► User Interfaces (HCI)
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Schlagworte	Algorithm analysis and problem complexity • algorithms • Automata • Calculus • combinatorics • Complexity • Computability • Computational Complexity • distributed programming • Efficient Algorithms • Effiziente Algorithmen • Formale Sprachtheorie • formal language • Formal Languages • Formal Language Theory • Grammars • Komplexität • Logic • Parallelprogrammierung • Parallel Programming • Petri net • Programmiertechniken • Programming Techniques • Program Transformation • RP • Semantics • turing degree • Turing Machine
ISBN-13	9783540514985 / 9783540514985
Zustand	Neuware