Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

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

Year of publication 2015
Type Article in Proceedings
Conference 26th International Conference on Concurrency Theory (CONCUR 2015)
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.