DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2011.67

Algebraic Characterization of FO for Scattered Linear Orderings

Authors: Alexis Bès and Olivier Carton

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bes_et_al:LIPIcs.CSL.2011.67,
  author =	{B\`{e}s, Alexis and Carton, Olivier},
  title =	{{Algebraic Characterization of FO for Scattered Linear Orderings}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{67--81},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.67},
  URN =		{urn:nbn:de:0030-drops-32233},
  doi =		{10.4230/LIPIcs.CSL.2011.67},
  annote =	{Keywords: linear orderings, first-order logic, semigroups, rational sets}
}

Search Results

Documents authored by Bès, Alexis

Algebraic Characterization of FO for Scattered Linear Orderings

Abstract

Cite as

Thanks for your feedback!

Could not send message