Representing recursively enumerable languages by iterated deletion

DOI10.1016/J.TCS.2004.01.002MaRDI QIDQ1826643zbMATH OpenOpenAlexFDO

Authors Michael Domaratzki, Alexander Okhotin

Publication date 6 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.01.002

zbMATH Keywords

Recursively enumerable languagesIterated sequential deletionLinear context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Publication:4005180
• On characterizations of recursively enumerable languages
• On representing recursively enumerable languages by internal contextual languages
• Publication:4005181
• Publication:4541813
• A homomorphic characterization of recursively enumerable languages
• Publication:4681308
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Characterizations of recursively enumerable languages by means of insertion grammars
• Publication:3974879

Cites work

• scientific article; zbMATH DE number 1142312 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 840350 (Why is no real title available?)
• Insertion and deletion closure of languages
• Outfix and infix codes and related classes of languages
• Remarks on deletions, scattered deletions and related operations on languages
• Reversal-bounded multipushdown machines
• Shuffle and scattered deletion closure of languages

Cited in

(9)

• scientific article; zbMATH DE number 58294 (Why is no real title available?)
• Developments in Language Theory
• Insertion-deletion with substitutions. II: About the role of one-sided context
• Parallel contextual array insertion deletion P systems and tabled matrix grammars
• scientific article; zbMATH DE number 7324347 (Why is no real title available?)
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Parallel contextual array insertion-deletion P systems and array rewriting P systems with pure 2D context-free rules
• Iterated TGR Languages: Membership Problem and Effective Closure Properties
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages

This page was built for publication: Representing recursively enumerable languages by iterated deletion

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