Fundamentals of Computation Theory: 9th International Conference, FCT ’93 Szeged, Hungary, August 23–27, 1993 Proceedings

Volker Diekert (auth.), Zoltán Ésik (eds.)3540571639, 9783540571636

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.

---

Table of contents :
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