Publication
Title
On delay and regret determinization of max-plus automata
Author
Abstract
Decidability of the determinization problem for weighted automata over the semiring (ℤ∪{-∞}, max; +), WA for short, is a long-standing open question. We propose two ways of approaching it by constraining the search space of deterministic WA: k-delay and r-regret. A WA N is k-delay determinizable if there exists a deterministic automaton D that defines the same function as N and for all words α in the language of N, the accepting run of D on α is always at most k-away from a maximal accepting run of N on α. That is, along all prefixes of the same length, the absolute difference between the running sums of weights of the two runs is at most k. A WA N is r-regret determinizable if for all words α in its language, its non-determinism can be resolved on the fly to construct a run of N such that the absolute difference between its value and the value assigned to α by N is at most r. We show that a WA is determinizable if and only if it is k-delay determinizable for some k. Hence deciding the existence of some k is as difficult as the general determinization problem. When k and r are given as input, the k-delay and r-regret determinization problems are shown to be EXPTIME-complete. We also show that determining whether a WA is r-regret determinizable for some r is in EXPTIME.
Language
English
Source (journal)
Proceedings. - Washington, D.C, 1986, currens
Source (book)
32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 20-23 June 2017, Reykjavik, Iceland
Publication
Washington, D.C : IEEE , 2017
ISSN
1043-6871
1043-6871
ISBN
978-1-5090-3018-7
978-1-5090-3019-4
DOI
10.1109/LICS.2017.8005096
Volume/pages
12 p.
ISI
000425849500034
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Publication type
Subject
External links
Web of Science
Record
Identifier
Creation 19.11.2018
Last edited 24.01.2023
To cite this reference