2 results
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 languages, decide whether there exists a locally testable (resp. a locally threshold testable) separator. In both cases, […]
Published on September 18, 2014
Thomas Place ; Marc Zeitoun.
An important endeavor in computer science is to understand the expressive power of logical formalisms over discrete structures, such as words. Naturally, "understanding" is not a mathematical notion. This investigation requires therefore a concrete objective to capture this understanding. In the […]
Published on July 20, 2018