Algebraic Characterization of FO for Scattered Linear Orderings

Authors Alexis Bès, Olivier Carton



PDF
Thumbnail PDF

File

LIPIcs.CSL.2011.67.pdf
  • Filesize: 470 kB
  • 15 pages

Document Identifiers

Author Details

Alexis Bès
Olivier Carton

Cite AsGet BibTex

Alexis Bès and Olivier Carton. Algebraic Characterization of FO for Scattered Linear Orderings. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 67-81, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.CSL.2011.67

Abstract

We prove that for the class of sets of words indexed by countable scattered linear orderings, there is an equivalence between definability in first-order logic, star-free expressions with marked product, and recognizability by finite aperiodic semigroups which satisfy some additional equation.
Keywords
  • linear orderings
  • first-order logic
  • semigroups
  • rational sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail