Finite tree automata with cost functions

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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 cardinalities of occurring cost sets are bounded. In all three cases, we derive explicit upper bounds. For semiring T, we prove decidability of boundedness as well, but obtain a polynomial-time algorithm only in case that the degrees of occurring polynomials are at most 1. For N and A, we extend our results to multidimensional cost functions.

Original languageEnglish
Pages (from-to)113-142
Number of pages30
JournalTheoretical Computer Science
Volume126
Issue number1
DOIs
StatePublished - 11 Apr 1994
Externally publishedYes

Fingerprint

Dive into the research topics of 'Finite tree automata with cost functions'. Together they form a unique fingerprint.

Cite this