Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

BISIMULATION MINIMIZATION OF TREE AUTOMATA

PAROSH AZIZ ABDULLA

Dept. of Information Technology, Uppsala University, P.O. Box 337, S–751 05 Uppsala, Sweden

Search for more papers by this author

JOHANNA HÖGBERG

Department of Computing Science, Umeå University, S–901 87 Umeå, Sweden

Search for more papers by this author

, and

LISA KAATI

Dept. of Information Technology, Uppsala University, P.O. Box 337, S–751 05 Uppsala, Sweden

Search for more papers by this author

https://doi.org/10.1142/S0129054107004929Cited by:8 (Source: Crossref)

Abstract

We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of , where is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

Keywords:

References

P.A. Abdulla and J. Högberg and L.Kaati, "Bisimulation Minimization Of Tree Automata" Technical report, Uppsala University, 2006 . Google Scholar
P. A. Abdullaet al., Regular Tree Model Checking, CAV, LNCS 2404 (2002) pp. 555–568. Google Scholar
P. A. Abdullaet al., A Survey of Regular Model Checking, CONCUR, LNCS 3170 (2004) pp. 35–48. Google Scholar
P. A. Abdullaet al., Journal of Logic and Algebraic Programming 69(1–2), 93 (2006), DOI: 10.1016/j.jlap.2006.02.001. Crossref, Web of Science, Google Scholar
M. Biehl , N. Klarlund and T. Rauhe , Algorithms for guided tree automata , Proceedings of the First Workshop on Implementing Automata , LNCS 1260 ( 1997 ) . Google Scholar
W. S. Brainerd, Information and Computation 13(5), 484 (1968). Google Scholar
H. Comon and M. Dauchet and R. Gilleron and F. Jacquemard and D. Lugiez and S. Tison and M. Tommasi, "Tree Automata Techniques and Applications", Available on: http://www.grappa.univ-lille3.fr/tata, 1997 . Google Scholar
J. Carme and R. Gilleron and A. Lemay and A. Terlutte and M. Tommasi, "Residual finite tree automata", Technical report, GRAPPA, 2003 . Google Scholar
J. Cristau, C. Löding and W. Thomas, Deterministic automata on unranked trees, FCT, LNCS 3623 (2005) pp. 68–79. Google Scholar
G. Gramlich and G. Schnitger, Minimizing NFA's and Regular Expressions, STAGS, LNCS 3404 (2005) pp. 399–411. Google Scholar
J. E. Hopcroft, Theory of Machines and Computations 189 (1971). Google Scholar
Y. Kestenet al., TCS 256(1–2), 93 (2001), DOI: 10.1016/S0304-3975(00)00103-1. Crossref, Web of Science, Google Scholar
R. Milner , LNCS 92 ( 1980 ) . Google Scholar
W. Martens and J. Niehren, JCSS (2006). Google Scholar
A. R. Meyer and L. J. Stockmeyer, The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory (1972) pp. 125–129. Google Scholar
F. Neven, Automata, Logic, and XML, CSL (2002) pp. 2–26. Google Scholar
M. Nivat and A. Podelski, SIAM Journal on Computing 26, 39 (1997). Crossref, Web of Science, Google Scholar
R. Paige and R. Tarjan, SIAM Journal on Computing 16, 973 (1987), DOI: 10.1137/0216062. Crossref, Web of Science, Google Scholar