L-reduction computation revisited

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

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

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

Cited In (5)

• Title not available (Why is that?)
• L-packets and reducibilities
• Title not available (Why is that?)
• \(L^1\)-computability, layerwise computability and Solovay reducibility
• Title not available (Why is that?)

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)