# Alternating Towers and Piecewise Testable Separators

From International Center for Computational Logic

# Alternating Towers and Piecewise Testable Separators

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

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

Technical Report,

**Alternating Towers and Piecewise Testable Separators**Technical Report,

*arXiv.org*, volume CoRR abs/1409.3943, September 2014**Kurzfassung****Abstract**

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}
}
```