Polynomial Time Decidability of Weighted Synchronization under Partial Observability
| Authors | |
|---|---|
| Year of publication | 2015 |
| Type | Article in Proceedings |
| Conference | 26th International Conference on Concurrency Theory (CONCUR 2015) |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.CONCUR.2015.142 |
| Field | Informatics |
| Keywords | weighted automata; partial observability; synchronization; complexity |
| Description | 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. |
| Related projects: |