Polynomial Time Decidability of Weighted Synchronization under Partial Observability
Autoři | |
---|---|
Rok publikování | 2015 |
Druh | Článek ve sborníku |
Konference | 26th International Conference on Concurrency Theory (CONCUR 2015) |
Fakulta / Pracoviště MU | |
Citace | KŘETÍNSKÝ, Jan, Kim Guldstrand LARSEN, Simon LAURSEN a Jiří SRBA. Polynomial Time Decidability of Weighted Synchronization under Partial Observability. Online. In 26th International Conference on Concurrency Theory (CONCUR 2015). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015, s. 142-154. ISBN 978-3-939897-91-0. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2015.142. |
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: |