Title




On delay and regret determinization of maxplus automata
 
Author




 
Abstract




Decidability of the determinization problem for weighted automata over the semiring (ℤ∪{∞}, max; +), WA for short, is a longstanding open question. We propose two ways of approaching it by constraining the search space of deterministic WA: kdelay and rregret. A WA N is kdelay 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 kaway 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 rregret determinizable if for all words α in its language, its nondeterminism 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 kdelay 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 kdelay and rregret determinization problems are shown to be EXPTIMEcomplete. We also show that determining whether a WA is rregret 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), 2023 June 2017, Reykjavik, Iceland
 
Publication




Washington, D.C
:
IEEE
,
2017
 
ISSN




10436871
10436871
 
ISBN




9781509030187
9781509030194
 
DOI




10.1109/LICS.2017.8005096
 
Volume/pages




12 p.
 
ISI




000425849500034
 
Full text (Publisher's DOI)




 
Full text (open access)




 
