On the state complexity of scattered substrings and superstrings

DOI10.3233/FI-2010-252MaRDI QIDQ4932068zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin

Publication date 1 October 2010

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2010-252

zbMATH Keywords

descriptional complexityfinite automatasubwordsubsequencestate complexitysubstringHigman-Haines sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• State complexity of power
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of pattern matching in regular languages
• State complexity of prefix distance
• On the state complexity of closures and interiors of regular languages with subwords

Cited in

(12)

• Decidability of involution hypercodes
• On the State Complexity of the Shuffle of Regular Languages
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• Finite automata for the sub- and superword closure of CFLs: descriptional and computational complexity
• Language operations with regular expressions of polynomial size
• Descriptional complexity of regular languages
• Further closure properties of input-driven pushdown automata
• State complexity of pattern matching in regular languages
• On the state complexity of closures and interiors of regular languages with subwords and superwords
• scientific article; zbMATH DE number 5990082 (Why is no real title available?)
• Commutative regular languages with product-form minimal automata
• State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages

This page was built for publication: On the state complexity of scattered substrings and superstrings

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