Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KŘETÍNSKÝ Jan LARSEN Kim Guldstrand LAURSEN Simon SRBA Jiří

Rok publikování 2015
Druh Článek ve sborníku
Konference 26th International Conference on Concurrency Theory (CONCUR 2015)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2015.142
Obor Informatika
Klíčová slova weighted automata; partial observability; synchronization; complexity
Popis We consider weighted automata with both positive and negative integer weights on edges and study the problem of synchronization using adaptive strategies that may only observe whether the current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.