Finite-Degree Predicates and Two-Variable First-Order Logic

DOI10.4230/LIPICS.CSL.2015.616zbMATH Open1373.03013arXiv1507.05175OpenAlexW2963620838MaRDI QIDQ5351986

Charles Paperman

Publication date: 31 August 2017

Abstract: We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature.

Full work available at URL: https://arxiv.org/abs/1507.05175

zbMATH Keywords

automata theorysemigroupfirst-order logicmodular predicates

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20) Descriptive complexity and finite models (68Q19)

Related Items (3)

Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable ⋮ On bijunctive predicates over a finite set ⋮ Title not available (Why is that?)

This page was built for publication: Finite-Degree Predicates and Two-Variable First-Order Logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351986)