Single semi-contextual insertion-deletion systems

DOI10.1007/s11047-021-09861-3zbMath1530.68136OpenAlexW3186484694MaRDI QIDQ6095514

Sergiu Ivanov, Sergey Verlan

Publication date: 8 September 2023

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-021-09861-3

zbMATH Keywords

regular languagescomputational completenessdescriptional complexityinsertion-deletion systemsforbidding grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational power of insertion-deletion (P) systems with rules of size two
• P systems with minimal insertion and deletion
• Recent developments on insertion-deletion systems
• Contextual insertions/deletions and computability
• Matrix insertion-deletion systems
• Insertion languages
• On the weight of universal insertion grammars
• A variant of random context grammars: Semi-conditional grammars
• On the computational power of insertion-deletion systems
• Insertion-deletion systems over relational words
• Context-free insertion-deletion systems
• Computational completeness of simple semi-conditional insertion-deletion systems
• On the power of generalized forbidding insertion-deletion systems
• Universal matrix insertion grammars with small size
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• Random Context and Semi-conditional Insertion-deletion Systems
• Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion
• On the decidability of accessibility problems (extended abstract)
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Further Results on Insertion-Deletion Systems with One-Sided Contexts
• Insertion-Deletion Systems with One-Sided Contexts
• Universality and Computational Completeness of Controlled Leftist Insertion-Deletion Systems
• A Pumping Lemma for Permitting Semi-Conditional Languages
• About One-Sided One-Symbol Insertion-Deletion P Systems
• Investigations on the power of matrix insertion-deletion systems with small sizes

This page was built for publication: Single semi-contextual insertion-deletion systems