This volume contains the proceedings of the Ninth Conferenceon Fundamentalsof Computation Theory (FCT 93) held inSzeged, Hungary, in August 1993. The conference was devotedto a broad range of topics including:- Semanticsand logical concepts in the theory of computingand formal specification- Automata and formal languages- Computational geometry, algorithmic aspects of algebra andalgebraic 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 mathematicalcomputer scienceThe volume contains the texts of 8 invitedlectures and 32short communications selected by the international programcommittee from a large number of submitted papers.
Rewriting, mobius 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.
Series: Lecture Notes in Computer Science
Number Of Pages: 476
Published: 4th August 1993
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6
Weight (kg): 0.68