Automata: from logics to algorithms

Automata: from logics to algorithms,Moshe Y. Vardi,Thomas Wilke

Automata: from logics to algorithms   (Citations: 7)
BibTex | RIS | RefWorks Download
We review, in a unified framework, translations from five dif- ferent logics—monadic second-order logic of one and two successors (S1S and S2S), linear-time temporal logic (LTL), computation tree logic (CTL), and modal µ-calculus (MC)—into appropriate models of finite-state automata on infinite words or infinite trees. Together with emptiness-testing algorithms for these models of automata, this yields decision procedures for these logics. The translations are presented in a modular fashion and in a way such that optimal complexity bounds for satisfiability, conformance (model checking), and realizability are obtained for all logics.
Published in 2008.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: