On the finite degree of ambiguity of finite tree automata

Helmut Seidl

doi:10.1007/3-540-51498-8_38

On the finite degree of ambiguity of finite tree automata

Helmut Seidl

Saarland University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<∞. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t₁ of depth less than 2²ⁿ·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 2^{2^{2·log(L+1)·n}}.

Original language	English
Title of host publication	Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings
Editors	Janos Demetrovics, Janos Csirik, Ferenc Gecseg
Publisher	Springer Verlag
Pages	395-404
Number of pages	10
ISBN (Print)	9783540514985
DOIs	https://doi.org/10.1007/3-540-51498-8_38
State	Published - 1989
Externally published	Yes
Event	7th International Conference on Fundamentals of Computation Theory, FCT 1989 - Szeged, Hungary Duration: 21 Aug 1989 → 25 Aug 1989

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	380 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Fundamentals of Computation Theory, FCT 1989
Country/Territory	Hungary
City	Szeged
Period	21/08/89 → 25/08/89

Access to Document

10.1007/3-540-51498-8_38

Cite this

Seidl, H. (1989). On the finite degree of ambiguity of finite tree automata. In J. Demetrovics, J. Csirik, & F. Gecseg (Eds.), Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings (pp. 395-404). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 380 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-51498-8_38

Seidl, Helmut. / On the finite degree of ambiguity of finite tree automata. Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings. editor / Janos Demetrovics ; Janos Csirik ; Ferenc Gecseg. Springer Verlag, 1989. pp. 395-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f469d53b43e840e4a41f788160826d39,

title = "On the finite degree of ambiguity of finite tree automata",

abstract = "The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<∞. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t1 of depth less than 22n·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 222·log(L+1)·n.",

author = "Helmut Seidl",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1989.; 7th International Conference on Fundamentals of Computation Theory, FCT 1989 ; Conference date: 21-08-1989 Through 25-08-1989",

year = "1989",

doi = "10.1007/3-540-51498-8_38",

language = "English",

isbn = "9783540514985",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "395--404",

editor = "Janos Demetrovics and Janos Csirik and Ferenc Gecseg",

booktitle = "Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings",

}

Seidl, H 1989, On the finite degree of ambiguity of finite tree automata. in J Demetrovics, J Csirik & F Gecseg (eds), Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 380 LNCS, Springer Verlag, pp. 395-404, 7th International Conference on Fundamentals of Computation Theory, FCT 1989, Szeged, Hungary, 21/08/89. https://doi.org/10.1007/3-540-51498-8_38

On the finite degree of ambiguity of finite tree automata. / Seidl, Helmut.
Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings. ed. / Janos Demetrovics; Janos Csirik; Ferenc Gecseg. Springer Verlag, 1989. p. 395-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 380 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the finite degree of ambiguity of finite tree automata

AU - Seidl, Helmut

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1989.

PY - 1989

Y1 - 1989

N2 - The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<∞. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t1 of depth less than 22n·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 222·log(L+1)·n.

AB - The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<∞. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t1 of depth less than 22n·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 222·log(L+1)·n.

UR - http://www.scopus.com/inward/record.url?scp=84881062658&partnerID=8YFLogxK

U2 - 10.1007/3-540-51498-8_38

DO - 10.1007/3-540-51498-8_38

M3 - Conference contribution

AN - SCOPUS:84881062658

SN - 9783540514985

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 395

EP - 404

BT - Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings

A2 - Demetrovics, Janos

A2 - Csirik, Janos

A2 - Gecseg, Ferenc

PB - Springer Verlag

T2 - 7th International Conference on Fundamentals of Computation Theory, FCT 1989

Y2 - 21 August 1989 through 25 August 1989

ER -

Seidl H. On the finite degree of ambiguity of finite tree automata. In Demetrovics J, Csirik J, Gecseg F, editors, Fundamentals of Computation Theory - International Conference, FCT 1989, Proceedings. Springer Verlag. 1989. p. 395-404. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-51498-8_38

On the finite degree of ambiguity of finite tree automata

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this