Alternating Towers and Piecewise Testable Separators

Štěpán HolubŠtěpán Holub, Tomáš MasopustTomáš Masopust, Michaël ThomazoMichaël Thomazo

Download

Štěpán Holub, Tomáš Masopust, Michaël Thomazo
Alternating Towers and Piecewise Testable Separators
Technical Report, arXiv.org, volume CoRR abs/1409.3943, September 2014

Details
Bibtex

KurzfassungAbstract
Two languages are separable by a piecewise testable language if and only if there exists no infinite tower between them. An infinite tower is an infinite sequence of strings alternating between the two languages such that every string is a subsequence (scattered substring) of all the strings that follow. For regular languages represented by nondeterministic finite automata, the existence of an infinite tower is decidable in polynomial time. In this paper, we investigate the complexity of a particular method to compute a piecewise testable separator. We show that it is closely related to the height of maximal finite towers, and provide the upper and lower bounds with respect to the size of the given nondeterministic automata. Specifically, we show that the upper bound is polynomial with respect to the number of states with the cardinality of the alphabet in the exponent. Concerning the lower bound, we show that towers of exponential height with respect to the cardinality of the alphabet exist. Since these towers mostly turn out to be sequences of prefixes, we also provide a comparison with towers of prefixes.
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@techreport{HMT2014,
  author      = {{\v{S}}t{\v{e}}p{\'{a}}n Holub and Tom{\'{a}}{\v{s}} Masopust
                 and Micha{\"{e}}l Thomazo},
  title       = {Alternating Towers and Piecewise Testable Separators},
  institution = {arXiv.org},
  year        = {2014},
  month       = {September}
}