Showing cs.LOShow all
3 papers · 1 filter
cs.LO2022
Regular languages defined by first-order formulas without quantifier alternation
Andreas Krebs, Howard Straubing
We give a simple new proof that regular languages defined by first-order sentences with no quantifier alteration can be defined by such sentences in which only regular atomic formu…
cs.LO2014
EF+EX Forest Algebras
Andreas Krebs, Howard Straubing
We examine languages of unranked forests definable using the temporal operators EF and EX. We characterize the languages definable in this logic, and various fragments thereof, usi…
cs.LO2012
An effective characterization of the alternation hierarchy in two-variable logic
Andreas Krebs, Howard Straubing
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 t…