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.
Author(s): Volker Diekert (auth.), Zoltán Ésik (eds.)
Series: Lecture Notes in Computer Science 710
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1993
Language: English
Pages: 476
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Combinatorics; Computer Graphics
Rewriting, möbius functions and semi-commutations....Pages 1-15
Simulations between different models of parallel computers....Pages 16-30
Dense and disjunctive properties of languages....Pages 31-49
The hierarchy of codes....Pages 50-68
Five facets of hyperedge replacement beyond context-freeness....Pages 69-86
An action structure for synchronous π-calculus....Pages 87-105
AC 0 circuit complexity....Pages 106-120
Pattern languages: Problems of decidability and generation....Pages 121-132
General solution of mirror equation....Pages 133-141
Decidability of equivalence for linear letter to letter top-down tree transducers....Pages 142-151
Translations between flowchart schemes and process graphs....Pages 152-161
Local equational logic....Pages 162-170
Liveness of weighted circuits and the diophantine problem of Frobenius....Pages 171-180
Context-free graph grammars: Separating vertex replacement from hyperedge replacement....Pages 181-193
Formal languages consisting of primitive words....Pages 194-203
Undecidability of the surjectivity problem for 2D cellular automata: A simplified proof....Pages 204-211
Efficient interpretation of state charts....Pages 212-221
Implementation of a universal unification algorithm for macro tree transducers....Pages 222-233
Finding maximum convex polygons....Pages 234-243
Approximations with axis-aligned rectangles (extended abstract)....Pages 244-255
Vector sequence analysis and full weak safety for concurrent systems....Pages 256-265
Does transitivity help? On the complexity of poset properties....Pages 266-278
Generalized topological sorting in linear time....Pages 279-288
Easily checked self-reducibility....Pages 289-298
On the complexities of linear LL(1) and LR(1) grammars....Pages 299-308
On the relation between firing sequences and processes of Petri nets....Pages 309-318
Maximum covering with D cliques....Pages 319-328
Monotonically labelled ordered trees and multidimensional binary trees....Pages 329-341
A maximum path length pumping lemma for edge-replacement languages....Pages 342-351
Regular approximations to shuffle products of context-free languages, and convergence of their generating functions....Pages 352-362
The equational theory of a Boolean monad....Pages 363-374
Non erasing Taring machines: a frontier between a decidable halting problem and Universality....Pages 375-385
On scattered syntactic monoids....Pages 386-395
Regular tree languages without unary symbols are star-free....Pages 396-405
One-way cellular automata on cayley graphs....Pages 406-417
ON tree pattern unification problems....Pages 418-429
Structural Equivalence and ETOL grammars....Pages 430-439
A hierarchy of deterministic top-down tree transformations....Pages 440-451
Synthesis of O (lg n ) testable trees....Pages 452-461
On the learnability of a restricted predicate formulae....Pages 462-471
