Normal forms for phrase-structure grammars

DOI10.1051/ita/1991250504731zbMath0755.68092OpenAlexW143770919MaRDI QIDQ3991298

Viliam Geffert

Publication date: 28 June 1992

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92402

zbMATH Keywords

normal forms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (33)

Cancellation in context-free languages: enrichment by reduction ⋮ On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Parsimonious computational completeness ⋮ Iterated sequential transducers as language generating devices ⋮ Computational completeness of path-structured graph-controlled insertion-deletion systems ⋮ \(\mathcal{L}\)-reduction computation revisited ⋮ One-sided random context grammars with a limited number of right random context rules ⋮ Unnamed Item ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ Unnamed Item ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ Nonterminal complexity of one-sided random context grammars ⋮ When Stars Control a Grammar's Work ⋮ Networks of Watson-Crick D0L systems with communication by substrings ⋮ CD GRAMMAR SYSTEMS WITH REGULAR START CONDITIONS ⋮ On path-controlled insertion-deletion systems ⋮ Unnamed Item ⋮ Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Universal insertion grammars of size two ⋮ Descriptional complexity of multi-parallel grammars ⋮ Hybrid networks of evolutionary processors are computationally complete ⋮ Matrix insertion-deletion systems ⋮ A note on the descriptional complexity of semi-conditional grammars ⋮ Formal properties of PA-matching ⋮ Operations and language generating devices suggested by the genome evolution ⋮ Improved descriptional complexity results on generalized forbidding grammars ⋮ Deterministic Lindenmayer Systems with Dynamic Control of Parallelism ⋮ Generalized forbidding matrix grammars and their membrane computing perspective ⋮ DNA computing based on splicing: Universality results ⋮ Languages of distributed reaction systems ⋮ On the computational completeness of matrix simple semi-conditional grammars ⋮ Networks of evolutionary processors: computationally complete normal forms

Cites Work

• A representation of recursively enumerable languages by two homomorphisms and a quotient
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• A Grammatical Characterization of One-Way Nondeterministic Stack Languages
• A Note on Bracketed Grammars
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Normal forms for phrase-structure grammars