kUFLEITNER_ita130048.pdf (346.65 kB)
0/0

One quantifier alternation in first-order logic with modular predicates

Download (346.65 kB)
journal contribution
posted on 22.02.2018 by Manfred Kufleitner, Tobias Walter
© 2015 EDP Sciences. Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[ < , MOD] with order comparison x < y and predicates for x ≡ i mod n has been investigated by Barrington et al. The study of FO[ < , MOD]-fragments was initiated by Chaubard et al. More recently, Dartois and Paperman showed that definability in the two-variable fragment FO 2 [ < , MOD] is decidable. In this paper we continue this line of work. We give an effective algebraic characterization of the word languages in Σ 2 [ < , MOD]. The fragment Σ 2 consists of first-order formulas in prenex normal form with two blocks of quantifiers starting with an existential block. In addition we show that Δ 2 [ < , MOD], the largest subclass of Σ 2 [ < , MOD] which is closed under negation, has the same expressive power as two-variable logic FO 2 [ < , MOD]. This generalizes the result FO 2 [ < ] = Δ 2 [ < ] of Thérien and Wilke to modular predicates. As a byproduct, we obtain another decidable characterization of FO 2 [ < , MOD].

Funding

The first author was supported by the German Research Foundation (DFG) under grant DI 435/5-1

History

School

  • Science

Department

  • Computer Science

Published in

RAIRO - Theoretical Informatics and Applications

Volume

49

Issue

1

Pages

1 - 22

Citation

KUFLEITNER, M. and WALTER, T., 2015. One quantifier alternation in first-order logic with modular predicates. RAIRO - Theoretical Informatics and Applications, 49(1), pp. 1-22.

Publisher

© EDP Sciences

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2015

Notes

The original publication is available at www.rairo-ita.org.

ISSN

0988-3754

eISSN

1290-385X

Language

en

Exports

Logo branding

Keyword(s)

Exports