LIPIcs.CSL.2011.67.pdf
- Filesize: 470 kB
- 15 pages
Document
Algebraic Characterization of FO for Scattered Linear Orderings
Authors
-
Part of:
Volume:
Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (CSL 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-08-31
Cite As Get 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.
Subject Classification
Keywords
- linear orderings
- first-order logic
- semigroups
- rational sets
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads