Fundamentals of Computation Theory : 9th International Conference, FCT '93, Szeged, Hungary, August 23-27, 1993 Book

	Rewriting, Mobius Functions and Semi-Commutations	1
	Simulations between Different Models of Parallel Computers	16
	Dense and Disjunctive Properties of Languages	31
	The Hierarchy of Codes	50
	Five Facets of Hyperedge Replacement Beyond Context-Freeness	69
	An Action Structure for Synchronous [pi]-Calculus	87
	AC[superscript 0] Circuit Complexity. A Survey of Lower Bounds	106
	Pattern Languages: Problems of Decidability and Generation	121
	General Solution of Mirror Equation	133
	Decidability of Equivalence for Linear Letter to Letter Top-Down Tree Transducers	142
	Translations Between Flowchart Schemes and Process Graphs	152
	Local Equational Logic	162
	Liveness of Weighted Circuits and the Diophantine Problem of Frobenius	171
	Context-Free Graph Grammars: Separating Vertex Replacement from Hyperedge Replacement	181
	Formal Languages Consisting of Primitive Words	194
	Undecidability of the Surjectivity Problem for 2D Cellular Automata: A Simplified Proof	204
	Efficient Interpretation of State Charts	212
	Implementation of a Universal Unification Algorithm for Macro Tree Transducers	222
	Finding Maximum Convex Polygons	234
	Approximations with Axis-Aligned Rectangles	244
	Vector Sequence Analysis and Full Weak Safety for Concurrent Systems	256
	Does Transitivity Help? On the Complexity of Poset Properties	266
	Generalized Topological Sorting in Linear Time	279
	Easily Checked Self-Reducibility	289
	On the Complexities of Linear LL(1) and LR(1) Grammars	299
	On the Relation Between Firing Sequences and Processes of Petri Nets	309
	Maximum Covering with D Cliques	319
	Monotonically Labelled Ordered Trees and Multidimensional Binary Trees	329
	Maximum Path Length Pumping Lemma for Edge-Replacement Languages	342
	Regular Approximations to Shuffle Products of Context-Free Languages, and Convergence of their Generating Functions	352
	The Equational Theory of a Boolean Monad	363
	Non Erasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality	375
	On Scattered Syntactic Monoids	386
	Regular Tree Languages without Unary Symbols are Star-Free	396
	One-Way Cellular Automata on Cayley Graphs	406
	On Tree Pattern Unification Problems	418
	Structural Equivalence and ETOL Grammars	430
	A Hierarchy of Deterministic Top-Down Tree Transformations	440
	Synthesis of O(lg n) Testable Trees	452
	On the Learnability of a Restricted Predicate Formulae	462