1985 · 142 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsProgramming LanguagesTheory Of ComputationAutomata TheoryComputational ModelsFinite-state MachinesModal LogicModel CheckingTuring MachinesEmptiness ProblemHybrid AutomataKripke StructuresLower BoundsNondeterministic ComplexitySatisfiabilitySatisfiability ProblemTree Automata
The paper introduces hybrid tree automata as a novel technique to establish tighter upper and lower bounds for modal logics of programs. It reduces satisfiability for several logics to the emptiness problem of hybrid tree automata and encodes Turing machine computations via Kripke structures where each state represents a tape cell. Hybrid tree automata are shown to be doubly exponential more powerful than Rabin tree automata yet their emptiness problem is only exponentially harder, yielding nondeterministic exponential‑time decision procedures for Streett’s delta‑PDL, Kozen’s μ‑calculus, and Parikh’s game logic, nondeterministic doubly exponential‑time procedures for CTL and YAPL, and deterministic doubly exponential‑time lower bounds and completeness for finite‑computation variants.
We describe novel techniques for establishing improved upper and lower bounds for modal logics of programs: 1) We introduce hybrid tree automata. These automata seems to be doubly exponential more powerful than Rabin tree automata but their emptiness problem is only exponentially harder (nondeterministic exponential time vs. nondeterministic polynomial time). The satisfiability problem for several logics is reducible to the emptiness problem for hybrid tree automata. Using this reduction we show that the satisfiability problems for Streett's delta-PDL. Kozen's μ-calculus and Parikh's game logic are solvable in nondeterministic exponential time, and the satisfiability problem for Emerson and Halpern's CTL and Vardi and Wolper's process logic (YAPL) are solvable in nondeterministic doubly exponential time. 2) We encode Turing machine computations by Kripke structures where every state in the structure represents a single tape cell. This yields a deterministic doubly exponential time lower bound for CTL and YAPL. 3) For variants of CTL and YAPL that deal only with finite computations we prove completeness for deterministic doubly exponential time.
17
Finite Automata and Their Decision Problems
M. O. Rabin, D. Scott · IBM Journal of Research and Development · 1959 · 1.9K citations
The temporal semantics of concurrent programs
Amir Pnueli · Theoretical Computer Science · 1981 · 701 citations
The temporal logic of branching time
Mordechai Ben‐Ari, Zohar Manna, Amir Pnueli · 1981 · 216 citations · Full text