S.M. Sadjadi, S. Chen, et al.
TAPIA 2009
The problem of complementing Büchi automata arises when developing decision procedures for temporal logics of programs. Unfortunately, previously known constructions for complementing Büchi automata involve a doubly exponential blow-up in the size of the automaton. We present a construction that involves only an exponential blow-up. We use this construction to prove a polynomial space upper bound for the propositional temporal logic of regular events and to prove a complexity hierarchy result for quantified propositional temporal logic. © 1987.
S.M. Sadjadi, S. Chen, et al.
TAPIA 2009
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Leo Liberti, James Ostrowski
Journal of Global Optimization
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research