On the State Complexity of Scattered Substrings and Superstrings

DOI10.3233/FI-2010-252zbMath1208.68139OpenAlexW2158538677MaRDI QIDQ4932068

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

finite automatastate complexitydescriptional complexitysubwordsubsequencesubstringHigman-Haines sets

Mathematics Subject Classification ID

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

Related Items

Quotient complexity of closed languages ⋮ Decidability of involution hypercodes ⋮ State complexity of pattern matching in regular languages ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Further closure properties of input-driven pushdown automata ⋮ Language operations with regular expressions of polynomial size ⋮ Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity ⋮ On the State Complexity of the Shuffle of Regular Languages ⋮ 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