Decidability Questions for Insertion Systems and Related Models

DOI10.3233/FI-2021-2034OpenAlexW3162757880MaRDI QIDQ5164868

Andreas Malcher

Publication date: 15 November 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2034

zbMATH Keywords

restarting automatadecidability questionspure grammarsinsertion systemsforgetting automataclearing restarting automata

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Post correspondence problem for short words
• Marcus contextual grammars
• Fundamentals of computation theory. 10th international conference, FCT'95, Dresden, Germany, August 22--25, 1995. Proceedings
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• Universal matrix insertion grammars with small size
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Random Context and Semi-conditional Insertion-deletion Systems
• Clearing Restarting Automata
• Pure grammars
• Some decidability problems of sentential formst †
• Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• Δ-Clearing Restarting Automata and $\makebox{\sf CFL} $
• ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA

This page was built for publication: Decidability Questions for Insertion Systems and Related Models