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)
|
|
|
|
| |
|