The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
The Complexity of Tree Automata and Logics of Programs
E. Allen Emerson, Charanjit S. Jutla,
Pages. 132-158
Abstract
Contents 1. Introduction 2. Preliminaries 2.1. Logics of programs 2.1.1. Full branching
time logic 2.1.2. Propositional dynamic logic plus repeat 2.1.3.
Propositional Mu-calculus 2.1.4. Conventions 2.2. Automata on
infinite trees 3. Small model theorems 3.1. Tree automata running
on graphs 3.2. The transition diagram of a tree automaton 3.3. One
symbol alphabets 3.4. Generation and containment 3.5. Linear size
model theorems 3.6. Pseudomodels 4. Complexity of pairs tree
automata 5. Complexity of complemented pairs tree automata 6.
Applications to logics of programs 7. Conclusion 8. Appendix A
Key words complexity, tree automata, logics of programs, games
Mathmatical Subject Classification 68Q68, 68Q60, 03B45