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 automataHigman-Haines setsstate complexitysubsequencesubstringsubword

Mathematics Subject Classification ID

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

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

(14)

• Descriptional complexity of regular languages
• 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
• Language operations with regular expressions of polynomial size
• State complexity of pattern matching in regular languages
• Finite automata for the sub- and superword closure of CFLs: descriptional and computational complexity
• On the State Complexity of the Shuffle of Regular Languages
• scientific article; zbMATH DE number 5990082 (Why is no real title available?)
• Decidability of involution hypercodes
• Further closure properties of input-driven pushdown automata
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• Binary right-distinguishability operation
• Linear time subsequence and supersequence regex matching
• On the state complexity of closures and interiors of regular languages with subwords and superwords

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)