DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2012 · 19 citations · 3 references
ComputingComputer ScienceMathematicsFormal MethodsLogicTheory Of ComputationAutomata TheoryFinite AutomataFinite-state MachinesFirst-order LogicModel CheckingModel TheoryEmptiness ProblemInfinite LogicInfinite TreesMonadic Second-order LogicQuantifier EliminationQuantifier HandlingQuantifier Semantics
We prove that, over infinite trees, satisfiability is decidable for Weak Monadic Second-Order Logic extended by the unbounding quantifier U. We develop an automaton model, prove that it is effectively equivalent to the logic, and that the automaton model has decidable emptiness.
3
Weak MSO with the Unbounding Quantifier
Mikołaj Bojańczyk · Theory of Computing Systems · 2010 · 39 citations · Full text
Regular Cost Functions over Finite Trees
Thomas Colcombet, Christof Löding · 2010 · 37 citations