This book constitutes the refereed proceedings of the 12th International Symposium on Fundamentals of Computation Theory, FCT '99, held in Iasi, Romania in August/September 1999.
The 42 revised full papers presented together with four invited papers were carefully selected from a total of 102 submissions.

Randomized complexity of linear arrangements and polyhedra?.- Tile transition systems as structured coalgebras?.- Caesar and DNA — views on cryptology.- Automata and their interaction: Definitional suggestions.- Axiomatising asynchronous process calculi.- A polynomial time approximation scheme for dense MupIN 2S{upAT}.- Decidable classes of the verification problem in a timed predicate logic.- Interpretations of extensible objects and types.- Restrictive acceptance suffices for equivalence problems.- Grammar systems as language analyzers and recursively enumerable languages.- An interpretation of extensible objects.- Modeling operating systems schedulers with multi-stack-queue grammars.- Iterative arrays with a wee bit alternation.- Secret sharing schemes with detection of cheaters for a general access structure.- Constructive notes on uniform and locally convex spaces.- Graph automorphisms with maximal projection distances.- Kleene theorems for event-clock automata.- Strong iteration lemmata for regular, linear, context-free, and linear indexed languages.- Exponential output size of top-down tree transducers.- On recognizable languages in divisibility monoids.- Expressiveness of point-to-point versus broadcast communications.- On relative loss bounds in generalized linear regression.- Generalized P-systems.- Optimal, distributed decision-making: The case of no communication.- Generalized PCP is decidable for marked morphisms.- On time-constructible functions in one-dimensional cellular automata.- Dichotomy theorem for the generalized unique satisfiability problem.- A general categorical connection between local event structures and local traces.- Correct translation of mutually recursive function systems into TOL collage grammars.- Synchronized product of linearbounded machines.- On maximal repetitions in words.- Axiomatization of the coherence property for categories of symmetries.- Sewing grammars.- State and transition complexity of Watson-Crick finite automata.- A confluence result for a typed ?-calculus of exception handling with fixed-point.- ?-Uniformly decidable sets and turing machines.- A parallel context-free derivation hierarchy.- Generalized synchronization languages.- A generalization of Dijkstra’s calculus to typed program specifications.- Homomorphisms and concurrent term rewriting.- On two-sided infinite fixed points of morphisms.- Tiling multi-dimensional arrays.- Modeling interaction by sheaves and geometric logic.- The operators minCh and maxCh on the polynomial hierarchy.- The Kolmogorov complexity of real numbers.- A partial order method for the verification of time Petri nets.- Deriving formulas for domination numbers of fasciagraphs and rotagraphs.

GPSR Compliance The European Union's (EU) General Product Safety Regulation (GPSR) is a set of rules that requires consumer products to be safe and our obligations to ensure this. If you have any concerns about our products you can contact us on ProductSafety@springernature.com. In case Publisher is established outside the EU, the EU authorized representative is: Springer Nature Customer Service Center GmbH Europaplatz 3 69115 Heidelberg, Germany ProductSafety@springernature.com