Zoltan Esik (ed.)

Fundamentals of Computation Theory

9th International Conference, FCT '93, Szeged, Hungary, August 23-27, 1993. Proceedings
Mitarbeit:Esik, Zoltan

• Broschiertes Buch

Produktbeschreibung

This volume contains the proceedings of the Ninth Conference on Fundamentalsof Computation Theory (FCT 93) held in Szeged, Hungary, in August 1993. The conference was devoted to a broad range of topics including:

- Semanticsand logical concepts in the theory of computing and formal specification

- Automata and formal languages

- Computational geometry, algorithmic aspects of algebra and algebraic geometry, cryptography

- Complexity (sequential, parallel, distributed computing, structure, lower bounds, complexity of analytical problems, general concepts)

- Algorithms (efficient, probabilistic, parallel, sequential, distributed)

- Counting and combinatorics in connection with mathematical computer science

The volume contains the texts of 8 invitedlectures and 32 short communications selected by the international program committee from a large number of submitted papers.

Produktdetails

• Lecture Notes in Computer Science 710
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-57163-6
• 1993.
• Seitenzahl: 488
• Erscheinungstermin: 4. August 1993
• Englisch
• Abmessung: 235mm x 155mm x 27mm
• Gewicht: 644g
• ISBN-13: 9783540571636
• ISBN-10: 3540571639
• Artikelnr.: 09225320

Inhaltsangabe

Rewriting, möbius functions and semi-commutations.- Simulations between different models of parallel computers.- Dense and disjunctive properties of languages.- The hierarchy of codes.- Five facets of hyperedge replacement beyond context-freeness.- An action structure for synchronous ?-calculus.- AC0 circuit complexity.- Pattern languages: Problems of decidability and generation.- General solution of mirror equation.- Decidability of equivalence for linear letter to letter top-down tree transducers.- Translations between flowchart schemes and process graphs.- Local equational logic.- Liveness of weighted circuits and the diophantine problem of Frobenius.- Context-free graph grammars: Separating vertex replacement from hyperedge replacement.- Formal languages consisting of primitive words.- Undecidability of the surjectivity problem for 2D cellular automata: A simplified proof.- Efficient interpretation of state charts.- Implementation of a universal unification algorithm for macro tree transducers.- Finding maximum convex polygons.- Approximations with axis-aligned rectangles (extended abstract).- Vector sequence analysis and full weak safety for concurrent systems.- Does transitivity help? On the complexity of poset properties.- Generalized topological sorting in linear time.- Easily checked self-reducibility.- On the complexities of linear LL(1) and LR(1) grammars.- On the relation between firing sequences and processes of Petri nets.- Maximum covering with D cliques.- Monotonically labelled ordered trees and multidimensional binary trees.- A maximum path length pumping lemma for edge-replacement languages.- Regular approximations to shuffle products of context-free languages, and convergence of their generating functions.- The equational theory of a Boolean monad.-Non erasing Taring machines: a frontier between a decidable halting problem and Universality.- On scattered syntactic monoids.- Regular tree languages without unary symbols are star-free.- One-way cellular automata on cayley graphs.- ON tree pattern unification problems.- Structural Equivalence and ETOL grammars.- A hierarchy of deterministic top-down tree transformations.- Synthesis of O(lg n) testable trees.- On the learnability of a restricted predicate formulae.