License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2015.142
URN: urn:nbn:de:0030-drops-53927
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5392/
Go to the corresponding LIPIcs Volume Portal

Kretinsky, Jan ; Larsen, Kim Guldstrand ; Laursen, Simon ; Srba, Jiri

Polynomial Time Decidability of Weighted Synchronization under Partial Observability

pdf-format:
32.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{kretinsky_et_al:LIPIcs:2015:5392,
  author =	{Jan Kretinsky and Kim Guldstrand Larsen and Simon Laursen and Jiri Srba},
  title =	{{Polynomial Time Decidability of Weighted Synchronization under Partial Observability}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{142--154},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5392},
  URN =		{urn:nbn:de:0030-drops-53927},
  doi =		{10.4230/LIPIcs.CONCUR.2015.142},
  annote =	{Keywords: weighted automata, partial observability, synchronization, complexity}
}

Keywords: weighted automata, partial observability, synchronization, complexity
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI