Cancellation in context-free languages: enrichment by reduction
From MaRDI portal
Publication:1325840
DOI10.1016/0304-3975(94)90104-XzbMath0805.68076MaRDI QIDQ1325840
Matthias Jantzen, Holger Petersen
Publication date: 26 January 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
cancellationdecidabilitycontext-free languagesrecursively enumerable setcontext-free grammarPetri net languagessymmetric Dyck set
Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42)
Related Items
\(\mathcal{L}\)-reduction computation revisited ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
Cites Work
- Monadic Thue systems
- A Supernormal-Form Theorem for Context-Free Grammars
- Using string languages to describe picture languages
- Finiteness Conditions on Subgroups and Formal Language Theory
- Normal forms for phrase-structure grammars
- How to Make Arbitrary Grammars Look Like Context-Free Grammars
- Some characterizations of lindenmayer systems in terms of chomsky-type grammars and stack machines
- Efficient reductions of picture words
- Some remarks on derivations in general rewriting systems
- Full AFLs and nested iterated substitution
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
