Proceedings - Symposium on Logic in Computer Science · 2008 · 25 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsGame TheoryAutomata TheoryFinite AutomataFinite-state MachinesPushdown AutomataRecursion TheoryRegular LanguagesHigher-order Pushdown AutomataNested Stack AutomataPushdown Automata Model CheckingPushdown GamesRecursion SchemesRegular SetsStack Automata
In this paper we consider parity games defined by higher-order pushdown automata. These automata generalise pushdown automata by the use of higher-order stacks, which are nested "stack of stacks" structures. Representing higher-order stacks as well-bracketed words in the usual way, we show that the winning regions of these games are regular sets of words. Moreover a finite automaton recognising this region can be effectively computed.A novelty of our work are abstract pushdown processes which can be seen as (ordinary) pushdown automata but with an infinite stack alphabet. We use the device to give a uniform presentation of our results.From our main result on winning regions of parity games we derive a solution to the Modal Mu-Calculus Global Model-Checking Problem for higher-order pushdown graphs as well as for ranked trees generated by higher-order safe recursion schemes.
22
Results on the propositional μ-calculus
Dexter Kozen · Theoretical Computer Science · 1983 · 1.8K citations
Humanities, Mathematics, Logic +4
Tree automata, mu-calculus and determinacy
E. Allen Emerson, Charanjit S. Jutla · 2002 · 742 citations
Donald A. Martin · Annals of Mathematics · 1975 · 581 citations
Indexed Grammars—An Extension of Context-Free Grammars
Alfred V. Aho · Journal of the ACM · 1968 · 441 citations · Full text