2014/06/30 by Prateek Karandikar, Matthias Niewerth, Philippe Schnoebelen · 1 citation
Computer Science · #cs.FL
paper · pdf · doi:10.1016/j.tcs.2015.09.028
published as Theoretical Computer Science, 610:91-107, 2016
arxiv created 2015/12/01 · arxiv updated 2015/12/02
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.