TY - GEN
T1 - Finite tree automata with cost functions
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - Cost functions for tree automata are mappings from transitions to (tuples of) polynomials over some semiring. We consider four semirings, namely N the semiring of nonnegative integers, A the “arctical semiring”, T the tropical semiring and F the semiring of finite subsets of nonnegative integers. We show: for semirings N and A it is decidable in polynomial time whether or not the costs of accepting computations is bounded; for F it is decidable in polynomial time whether or not the cardinality of occurring cost sets is bounded. In all three cases we derive explicit upper bounds. For semiring T we are able to derive similar results at least in case of polynomials of degree at most 1. For N and A we extend our results to multi-dimensional cost functions.
AB - Cost functions for tree automata are mappings from transitions to (tuples of) polynomials over some semiring. We consider four semirings, namely N the semiring of nonnegative integers, A the “arctical semiring”, T the tropical semiring and F the semiring of finite subsets of nonnegative integers. We show: for semirings N and A it is decidable in polynomial time whether or not the costs of accepting computations is bounded; for F it is decidable in polynomial time whether or not the cardinality of occurring cost sets is bounded. In all three cases we derive explicit upper bounds. For semiring T we are able to derive similar results at least in case of polynomials of degree at most 1. For N and A we extend our results to multi-dimensional cost functions.
UR - https://www.scopus.com/pages/publications/85010969934
U2 - 10.1007/3-540-55251-0_16
DO - 10.1007/3-540-55251-0_16
M3 - Conference contribution
AN - SCOPUS:85010969934
SN - 9783540552512
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 289
BT - CAAP 1992 - 17th Colloquium on Trees in Algebra and Programming, Proceedings
A2 - Raoult, Jean-Claude
PB - Springer Verlag
T2 - 17th Colloquium on Trees in Algebra and Programming, CAAP 1992
Y2 - 26 February 1992 through 28 February 1992
ER -