Electronic Notes in Theoretical Computer Science · 1997 · 148 citations · 16 references
ComputingComputer ScienceFormal MethodsLogicSystems ModelingAutomata TheoryDeductive VerificationFinite State Machine ModelingModel CheckingPushdown AutomataTemporal LogicLinear Temporal LogicLinear-time Temporal LogicPushdown Automata Model CheckingPushdown Automata ReachabilityPushdown System VerificationTemporal Logic VerificationTransition Systems
This paper gives a simple and direct algorithm for computing the always regular set of reachable states of a pushdown system. It then exploits this algorithm for obtaining model checking algorithms for linear-time temporal logic as well as for the logic CTL∗. For the latter, a new technical tool is introduced: pushdown automata with transitions conditioned on regular predicates on the stack content. Finally, this technical tool is also used to establish that CTL∗ model checking remains decidable when the formulas are allowed to include regular predicates on the stack content.
16
E. Allen Emerson · 1990 · 824 citations
Memory-efficient algorithms for the verification of temporal properties
C. Courcoubetis, M. Vardi, Pierre Wolper et al. · Formal Methods in System Design · 1992 · 498 citations · Full text