Representing recursively enumerable languages by iterated deletion

DOI10.1016/j.tcs.2004.01.002zbMath1072.68055OpenAlexW1986652500MaRDI QIDQ1826643

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)

Related Items (3)

Unnamed Item ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Parallel contextual array insertion deletion P systems and tabled matrix grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outfix and infix codes and related classes of languages
• Reversal-bounded multipushdown machines
• Insertion and deletion closure of languages
• Shuffle and scattered deletion closure of languages

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