Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

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

Separation for dot-depth two

Thomas Place ; Marc Zeitoun.
The dot-depth hierarchy of Brzozowski and Cohen classifies the star-free languages of finite words. By a theorem of McNaughton and Papert, these are also the first-order definable languages. The dot-depth rose to prominence following the work of Thomas, who proved an exact correspondence with the&nbsp;[&hellip;]
Published on September 17, 2021
Volume 17, Issue 3
  • < Previous
  • 1
  • Next >