Selected publications at LSV

Abstract:
We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the Σ1 theory is undecidable (already over two letters). We investigate the decidability border by considering fragments where all but a certain number of variables are alternation bounded, meaning that the variable must always be quantified over languages with a bounded number of letter alternations. We prove that when at most two variables are not alternation bounded, the Σ1 fragment is decidable, and that it becomes undecidable when three variables are not alternation bounded. Regarding higher quantifier alternation depths, we prove that the Σ2 fragment is undecidable already for one variable without alternation bound and that when all variables are alternation bounded, the entire first-order theory is decidable.

@inproceedings{HSZ-lics17,
   address = {Reykjavik, Iceland},
   author = {Halfon, Simon and Schnoebelen, {\relax Ph}ilippe and Zetzsche, Georg},
   booktitle = {{P}roceedings of the 32nd {A}nnual {ACM\slash IEEE} {S}ymposium on {L}ogic {I}n {C}omputer {S}cience ({LICS}'17)},
   editor = {Ouaknine, Jo{\"e}l},
   month = jun,
   note = {To appear},
   publisher = {{IEEE} Press},
   title = {Decidability, complexity, and expressiveness of first-order logic over the subword ordering},
   url = {https://arxiv.org/abs/1701.07470},
   year = {2017},
}

About LSV

Select by Year