50 citations · 146 across the 25 of their papers we have counts for
3 papers · 1 filter
On Separation by Locally Testable and Locally Threshold Testable Languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun
A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input…
Separating regular languages by piecewise testable and unambiguous languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun
Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation p…
The separation problem for regular languages by piecewise testable languages
Lorijn van Rooijen, Marc Zeitoun
Separation is a classical problem in mathematics and computer science. It asks whether, given two sets belonging to some class, it is possible to separate them by another set of a…