State Complexity of Insertion

DOI10.1142/S0129054116500349zbMath1404.68069MaRDI QIDQ2970209

Yo-Sub Han, Timothy Ng, Sang-Ki Ko, Kai Salomaa

Publication date: 28 March 2017

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular languagesstate complexityinsertion operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Nondeterministic state complexity of site-directed deletion ⋮ Unnamed Item ⋮ The nondeterministic state complexity of the site-directed deletion language operation ⋮ Further closure properties of input-driven pushdown automata ⋮ Site-directed insertion: language equations and decision problems

Cites Work

• Computational power of insertion-deletion (P) systems with rules of size two
• Language-theoretic problems arising from Richelieu cryptosystems
• State complexity of basic operations on suffix-free regular languages
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• On language equations with invertible operations
• On the computational power of insertion-deletion systems
• Context-free insertion-deletion systems
• Regulated RNA rewriting: Modelling RNA editing with guided insertion
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• State complexity of deletion and bipolar deletion

This page was built for publication: State Complexity of Insertion