Polynomial time decidability of weighted synchronization under partial observability

Jan Křetínský, Kim Guldstrand Larsen, Simon Laursen, Jiří Srba

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication26th International Conference on Concurrency Theory, CONCUR 2015
EditorsLuca Aceto, David de Frutos Escrig
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages142-154
Number of pages13
ISBN (Electronic)9783939897910
DOIs
StatePublished - 1 Aug 2015
Externally publishedYes
Event26th International Conference on Concurrency Theory, CONCUR 2015 - Madrid, Spain
Duration: 1 Sep 20154 Sep 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume42
ISSN (Print)1868-8969

Conference

Conference26th International Conference on Concurrency Theory, CONCUR 2015
Country/TerritorySpain
CityMadrid
Period1/09/154/09/15

Keywords

  • Complexity
  • Partial observability
  • Synchronization
  • Weighted automata

Fingerprint

Dive into the research topics of 'Polynomial time decidability of weighted synchronization under partial observability'. Together they form a unique fingerprint.

Cite this