24 citations · 63 across the 14 of their papers we have counts for
3 papers · 1 filter
Piecewise testable tree languages
Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing
This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem,…
Wreath Products of Forest Algebras, with Applications to Tree Logics
Mikolaj Bojanczyk, Igor Walukiewicz, Howard Straubing
We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These includ…
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…