Improved upper and lower bounds for modal logics of programs

Moshe Y. Vardi, Larry Stockmeyer

1985 · 142 citations · 17 references

DOIFull text

Open access

Concepts

TL;DR

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.

Abstract

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.

References

17