pith. sign in

arxiv: 1606.03217 · v2 · pith:KEF2OFDCnew · submitted 2016-06-10 · 💻 cs.FL

Decidable Characterization of FO2(<,+1) and locality of DA

classification 💻 cs.FL
keywords decidablecharacterizationdefinablelocalitysemigrouplanguagesproofresult
0
0 comments X
read the original abstract

Several years ago Th\'erien and Wilke exhibited a decidable characterization of the languages of words that are definable in FO2(<,+1). Their proof relies on three separate ingredients. The first one is the characterization of the languages that are definable in FO2(<) as those whose syntactic semigroup belongs to the variety DA. Then, this result is combined with a wreath product argument showing that being definable in FO2(<,+1) corresponds to having a syntactic semigroup in DA*D. Finally, proving that membership of a semigroup in DA*D is decidable requires a third ingredient: the "locality" of DA, a result proved by Almeida. In this note we present a new self-contained and simple proof that definability in FO2(<,+1) is decidable. We obtain the locality of DA as a corollary.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.