L-reduction computation revisited

DOI10.1007/S00236-022-00418-0MaRDI QIDQ2170281zbMATH OpenOpenAlexFDO

Authors Kaoru Fujioka, Fumiya Okubo, 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)

Recommendations

• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• scientific article; zbMATH DE number 4047162
• scientific article; zbMATH DE number 4139308
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

Cites work

• scientific article; zbMATH DE number 4139308 (Why is no real title available?)
• scientific article; zbMATH DE number 4024816 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3999315 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Cancellation in context-free languages: enrichment by reduction
• Context-free insertion-deletion systems
• Finiteness Conditions on Subgroups and Formal Language Theory
• Monadic Thue systems
• Morphic characterizations of language families in terms of insertion systems and star languages
• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• Normal forms for phrase-structure grammars
• On characterizations of recursively enumerable languages
• On parallel deletions applied to a word
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• On the impossibility of the homomorphic characterization of context- sensitive languages
• On the weight of universal insertion grammars
• One-sided and two-sided context in formal grammars
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Recent developments on insertion-deletion systems
• Shuffle and scattered deletion closure of languages
• Some characterizations of lindenmayer systems in terms of chomsky-type grammars and stack machines
• Universal insertion grammars of size two

Cited in

(5)

• scientific article; zbMATH DE number 1722667 (Why is no real title available?)
• L-packets and reducibilities
• scientific article; zbMATH DE number 1124612 (Why is no real title available?)
• \(L^1\)-computability, layerwise computability and Solovay reducibility
• scientific article; zbMATH DE number 1303639 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170281)