Decidability questions for insertion systems and related models

DOI10.3233/FI-2021-2034MaRDI QIDQ5164868zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Insertion languages
• Context-free insertion-deletion systems
• Insertion-deletion systems with substitutions. I
• On minimal context-free insertion-deletion systems
• Insertion-deletion systems over relational words

Cites work

• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 2040896 (Why is no real title available?)
• Clearing restarting automata
• Fundamentals of computation theory. 10th international conference, FCT'95, Dresden, Germany, August 22--25, 1995. Proceedings
• Graph-controlled insertion-deletion systems
• Marcus contextual grammars
• Membership for growing context-sensitive grammars is polynomial
• On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
• On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
• On the descriptional complexity of the window size for deleting restarting automata
• Post correspondence problem for short words
• Pure grammars
• Random context and semi-conditional insertion-deletion systems
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Small size insertion and deletion systems
• Some decidability problems of sentential formst †
• Universal matrix insertion grammars with small size
• Universality and computational completeness of controlled leftist insertion-deletion systems
• \(\Delta \)-clearing restarting automata and CFL

Cited in

(2)

• Contextual insertions/deletions and computability
• On decision problems concerning contextual insertions and deletions

This page was built for publication: Decidability questions for insertion systems and related models

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