\(\mathcal{L}\)-reduction computation revisited

DOI10.1007/S00236-022-00418-0OpenAlexW4220954793MaRDI QIDQ2170281

Fumiya Okubo, Kaoru Fujioka, Takashi Yokomori

Publication date: 30 August 2022

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-022-00418-0

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• Recent developments on insertion-deletion systems
• On the weight of universal insertion grammars
• On the impossibility of the homomorphic characterization of context- sensitive languages
• Monadic Thue systems
• On characterizations of recursively enumerable languages
• Cancellation in context-free languages: enrichment by reduction
• Shuffle and scattered deletion closure of languages
• Context-free insertion-deletion systems
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• Universal insertion grammars of size two
• MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Finiteness Conditions on Subgroups and Formal Language Theory
• Normal forms for phrase-structure grammars
• Some characterizations of lindenmayer systems in terms of chomsky-type grammars and stack machines
• On parallel deletions applied to a word
• One-sided and two-sided context in formal grammars

This page was built for publication: \(\mathcal{L}\)-reduction computation revisited