pith. sign in

arxiv: 1507.05175 · v2 · pith:WRAJLCTPnew · submitted 2015-07-18 · 💻 cs.LO

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

classification 💻 cs.LO
keywords logictwo-variabledefinablefinite-degreefirst-orderorderpredicatesalternation
0
0 comments X
read the original 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.

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.