DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2015.142

Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Authors: Jan Kretinsky, Kim Guldstrand Larsen, Simon Laursen, and Jiri Srba

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

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.

Cite as

Jan Kretinsky, Kim Guldstrand Larsen, Simon Laursen, and Jiri Srba. Polynomial Time Decidability of Weighted Synchronization under Partial Observability. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 142-154, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kretinsky_et_al:LIPIcs.CONCUR.2015.142,
  author =	{Kretinsky, Jan and Larsen, Kim Guldstrand and Laursen, Simon and Srba, Jiri},
  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 =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.142},
  URN =		{urn:nbn:de:0030-drops-53927},
  doi =		{10.4230/LIPIcs.CONCUR.2015.142},
  annote =	{Keywords: weighted automata, partial observability, synchronization, complexity}
}

Search Results

Documents authored by Laursen, Simon

Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Abstract

Cite as

Thanks for your feedback!

Could not send message