Nondeterministic state complexity of site-directed insertion

MaRDI QIDQ5867523FDOQ5867523

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

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)

zbMATH Keywords

finite automatonnondeterministic state complexityfooling setbio-inspired language operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• A Second Course in Formal Languages and Automata Theory
• Descriptional and computational complexity of finite automata -- a survey
• Intersection and union of regular languages and state complexity
• Partial orders on words, minimal elements of regular languages, and state complexity
• Self-assembly of strings and languages
• On the computational power of insertion-deletion systems
• Contextual insertions/deletions and computability
• Title not available (Why is that?)
• A survey on operational state complexity
• The chop of languages
• On the overlap assembly of strings and languages
• State complexity of overlap assembly
• Outfix-guided insertion
• Site-directed insertion: language equations and decision problems
• State complexity of insertion
• Descriptional complexity of chop operations on unary and finite 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)