Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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	https://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:	Centrum excelence - Institut teoretické informatiky