Conference paper
Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
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.
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Fan Jing Meng, Ying Huang, et al.
ICEBE 2007
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Nanda Kambhatla
ACL 2004