On the state complexity of closures and interiors of regular languages with subwords and superwords

Abstract

The downward and upward closures of a regular language $L$ are obtained by collecting all the subwords and superwords of its elements, respectively. The downward and upward interiors of $L$ are obtained dually by collecting words having all their subwords and superwords in $L$, respectively. We provide lower and upper bounds on the size of the smallest automata recognizing these closures and interiors. We also consider the computational complexity of decision problems for closures of regular languages.

References in corpus (2)

• Alternating Towers and Piecewise Testable Separators
• Computing downward closures for stacked counter automata

Cited by in corpus (4)

• Counting the number of non-zero coefficients in rows of generalized Pascal triangles
• The height of piecewise-testable languages and the complexity of the logic of subwords
• A Characterization for Decidable Separability by Piecewise Testable Languages
• Alternating Towers and Piecewise Testable Separators