An effective characterization of the alternation hierarchy in two-variable logic
classification
💻 cs.LO
keywords
alternationdecidablehierarchyindividuallevelslogicvarietycharacterization
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.