Nondeterministic state complexity of site-directed insertion

MaRDI QIDQ5867523zbMATH OpenFDO

Authors Oliver A. S. Lyon, Kai Salomaa

Publication date 14 September 2022

Full work available at URL http://www.jalc.de/issues/2022/issue_27_1-3/jalc-2022-187-197.php

zbMATH Keywords

bio-inspired language operationsfinite automatonfooling setnondeterministic state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of insertion
• Site-directed insertion: language equations and decision problems
• Site-directed insertion: decision problems, maximality and minimality
• Outfix-guided insertion
• Outfix-guided insertion (extended abstract)

Cites work

• A Second Course in Formal Languages and Automata Theory
• A survey on operational state complexity
• Contextual insertions/deletions and computability
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of chop operations on unary and finite languages
• scientific article; zbMATH DE number 3872708 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• On the computational power of insertion-deletion systems
• On the overlap assembly of strings and languages
• Outfix-guided insertion
• Partial orders on words, minimal elements of regular languages, and state complexity
• Self-assembly of strings and languages
• Site-directed insertion: language equations and decision problems
• State complexity of insertion
• State complexity of overlap assembly
• The chop of languages

Cited in

(1)

• The nondeterministic state complexity of the site-directed deletion language operation

This page was built for publication: Nondeterministic state complexity of site-directed insertion

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