pith. sign in

arxiv: 1205.4802 · v1 · pith:7HHYCSISnew · submitted 2012-05-22 · 💻 cs.LO

An effective characterization of the alternation hierarchy in two-variable logic

classification 💻 cs.LO
keywords alternationdecidablehierarchyindividuallevelslogicvarietycharacterization
0
0 comments X
read the original abstract

We characterize the languages in the individual levels of the quantifier alternation hierarchy of first-order logic with two variables by identities. This implies decidability of the individual levels. More generally we show that the two-sided semidirect product of a decidable variety with the variety J is decidable.

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.