Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

Separating Regular Languages with First-Order Logic

Thomas Place ; Marc Zeitoun.
Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regular input languages of finite words, decide whether there exists a first-order definable separator. We prove that in&nbsp;[&hellip;]
Published on March 9, 2016
Volume 12, Issue 1

The Covering Problem

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&nbsp;[&hellip;]
Published on July 20, 2018
Volume 14, Issue 3
  • < Previous
  • 1
  • Next >