On the state complexity of scattered substrings and superstrings

DOI10.3233/FI-2010-252zbMATH Open1208.68139OpenAlexW2158538677MaRDI QIDQ4932068FDOQ4932068

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

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

zbMATH Keywords

descriptional complexityfinite automatasubwordsubsequencestate complexitysubstringHigman-Haines sets

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• 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)