×

Deciding equivalence of finite tree automata. (English) Zbl 1492.68081

Monien, Burkhard (ed.) et al., STACS 89. 6th annual symposium on theoretical aspects of computer science, Paderborn, FRG, February 16–18, 1989. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 349, 480-492 (1989).
Summary: We show: for every constant \(m\) it can be decided in polynomial time whether or not two \(m\)-ambiguous finite tree automata are equivalent. In general, inequivalence for finite tree automata is DEXPTIME-complete w.r.t. logspace reductions, and PSPACE-complete w.r.t. logspace reductions, if the automata in question are supposed to accept only finite languages. For finite tree automata with coefficients in a field \(R\) we give a polynomial time algorithm for deciding ambiguity-equivalence provided \(R\)-operations and \(R\)-tests for 0 can be performed in constant time. We apply this algorithm for deciding ambiguity-inequivalence of finite tree automata in randomized polynomial time.
Furthermore, for every constant \(m\) we show that it can be decided in polynomial time whether or not a given finite tree automaton is \(m\)-ambiguous.
For the journal version see [SIAM J. Comput. 19, No. 3, 424–437 (1990; Zbl 0699.68075)].
For the entire collection see [Zbl 1369.68034].

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0699.68075
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman: The design and analysis of computer algorithms. Addison-Wesley 1974 · Zbl 0326.68005
[2] T. Apostol: Introduction to analytic number theory. Springer Verlag New York, 1976 · Zbl 0335.10001
[3] A.K. Chandra, D.C. Kozen, L.J. Stockmeyer: Alternation. JACM 28 (1981) pp. 114-133 · Zbl 0473.68043
[4] J. Doner: Tree acceptors and some of their applications. JCSS 4 (1970) pp. 406-451 · Zbl 0212.02901
[5] S. Eilenberg: Automata, languages, and machines, Vol. A. Academic Press, New York, 1974 · Zbl 0317.94045
[6] F. Gecseg, M. Steinby: Tree automata. Akademiai Kiado, Budapest, 1984 · Zbl 0537.68056
[7] G.H. Hardy, E.M. Wright: An introduction to the theory of numbers. Oxford, 4th edition 1960 · Zbl 0086.25803
[8] W. Kuich: Finite automata and ambiguity. Manuscript 1987 · Zbl 0668.68063
[9] A.R. Meyer, L.J. Stockmeyer: The equivalence problem for regular expressions with squaring requires exponential space. 13th SWAT (1972) pp. 125-129
[10] W.J. Paul: Komplexitätstheorie. B.G. Teubner Stuttgart 1978 · Zbl 0382.68044
[11] M.O. Rabin: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969) pp. 1-35 · Zbl 0221.02031
[12] B. Rosser, L. Schoenfeld: Approximate formulas for some functions of prime numbers. Illinois J. of Mathematics 6 (1962) pp. 64-94 · Zbl 0122.05001
[13] R. Stearns, H. Hunt III: On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. 22th FOCS (1981) pp. 74-81
[14] R. Stearns, H. Hunt III: On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM J. Comp. 14 (1985) pp. 598-611 · Zbl 0577.68074
[15] L.J. Stockmeyer, A.R. Meyer: Word problems requiring exponential time. 5th ACM-STOC pp. 1-9, 1973 · Zbl 0359.68050
[16] J.W. Thatcher, J.B. Wright: Generalized finite automata theory with an application to a decision problem of second order logic. Math. Syst. Th. 2 (1968) pp. 57-81 · Zbl 0157.02201
[17] W. Thomas: Logical aspects in the study of tree languages. In: 9th Coll. on Trees in Algebra and Programming”, B. Courcelle, Ed., Cambridge Univ. Press, 1984, pp. 31-49 · Zbl 0557.68051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.