On state complexity for subword-closed languages
<|reference_start|>On state complexity for subword-closed languages: This paper investigates the state complexities of subword-closed and superword-closed languages, comparing them to regular languages. We focus on the square root operator and the substitution operator. We establish an exponential lower bound for superword-closed languages for the k-th root. For subword-closed languages we analyze in detail a specific instance of the square root problem for which a quadratic complexity is proven. For the substitution operator, we show an exponential lower bound for the general substitution. We then find some conditions for which we prove a quadratic upper bound.<|reference_end|>
@article{guyot2024on,
    title={On state complexity for subword-closed languages},
    author={J'er^ome Guyot},
    journal={arXiv preprint arXiv:2407.10355},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10355},
    primaryClass={cs.FL}
}