Effective characterizations of tree logics
Mikolaj Bojanńzyk · 2008
A survey of effective characterizations of tree logics. If L is a logic, then an effective characterization for L is an algorithm, which inputs a tree automaton and replies if the recognized language can be defined by a formula in L. The logics L considered include path testable languages, frontier testable languages, fragments of Core XPath, and fragments of monadic second-order logic.