Polynomial Time Decidability of Weighted Synchronization under Partial Observability

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

• Centrum excelence - Institut teoretické informatiky