Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Jan Kretínsky; Kim Guldstrand Larsen; Simon Laursen; Jiri Srba

doi:10.4230/LIPIcs.CONCUR.2015.142

Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Jan Kretínsky, Kim Guldstrand Larsen, Simon Laursen, Jiri Srba

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

6 Citationer (Scopus)

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.

Originalsprog	Engelsk
Titel	26th International Conference on Concurrency Theory (CONCUR 2015)
Redaktører	Luca Aceto, David de Frutos Escrig
Antal sider	13
Udgivelsessted	Germany
Forlag	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato	2015
Sider	142-154
ISBN (Trykt)	978-3-939897-91-0
DOI	https://doi.org/10.4230/LIPIcs.CONCUR.2015.142
Status	Udgivet - 2015
Begivenhed	26th International Conference on Concurrency Theory - Madrid, Spanien Varighed: 1 sep. 2015 → 4 sep. 2015 Konferencens nummer: 26

Konference

Konference	26th International Conference on Concurrency Theory
Nummer	26
Land/Område	Spanien
By	Madrid
Periode	01/09/2015 → 04/09/2015

Navn	Leibniz International Proceedings in Informatics
Vol/bind	42
ISSN	1868-8969

Adgang til dokumentet

10.4230/LIPIcs.CONCUR.2015.142

http://drops.dagstuhl.de/opus/volltexte/2015/5392/pdf/32.pdf

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Andre filer og links

Citationsformater

Kretínsky, J., Larsen, K. G., Laursen, S., & Srba, J. (2015). Polynomial Time Decidability of Weighted Synchronization under Partial Observability. I L. Aceto, & D. de Frutos Escrig (red.), 26th International Conference on Concurrency Theory (CONCUR 2015) (s. 142-154). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CONCUR.2015.142

Kretínsky, Jan ; Larsen, Kim Guldstrand ; Laursen, Simon et al. / Polynomial Time Decidability of Weighted Synchronization under Partial Observability. 26th International Conference on Concurrency Theory (CONCUR 2015). red. / Luca Aceto ; David de Frutos Escrig. Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. s. 142-154 (Leibniz International Proceedings in Informatics, Bind 42).

@inproceedings{0e835a555ca24e4fad754b72faeaed9d,

title = "Polynomial Time Decidability of Weighted Synchronization under Partial Observability",

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. ",

keywords = "weighted automata, partical observability, sycnhronization, complexity",

author = "Jan Kret{\'i}nsky and Larsen, {Kim Guldstrand} and Simon Laursen and Jiri Srba",

year = "2015",

doi = "10.4230/LIPIcs.CONCUR.2015.142",

language = "English",

isbn = "978-3-939897-91-0",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "142--154",

editor = "Luca Aceto and {de Frutos Escrig}, David",

booktitle = "26th International Conference on Concurrency Theory (CONCUR 2015)",

note = "26th International Conference on Concurrency Theory, CONCUR'15 ; Conference date: 01-09-2015 Through 04-09-2015",

}

Kretínsky, J, Larsen, KG, Laursen, S & Srba, J 2015, Polynomial Time Decidability of Weighted Synchronization under Partial Observability. i L Aceto & D de Frutos Escrig (red), 26th International Conference on Concurrency Theory (CONCUR 2015). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Germany, Leibniz International Proceedings in Informatics, bind 42, s. 142-154, 26th International Conference on Concurrency Theory, Madrid, Spanien, 01/09/2015. https://doi.org/10.4230/LIPIcs.CONCUR.2015.142

Polynomial Time Decidability of Weighted Synchronization under Partial Observability. / Kretínsky, Jan; Larsen, Kim Guldstrand; Laursen, Simon et al.
26th International Conference on Concurrency Theory (CONCUR 2015). red. / Luca Aceto; David de Frutos Escrig. Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. s. 142-154 (Leibniz International Proceedings in Informatics, Bind 42).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

TY - GEN

T1 - Polynomial Time Decidability of Weighted Synchronization under Partial Observability

AU - Kretínsky, Jan

AU - Larsen, Kim Guldstrand

AU - Laursen, Simon

AU - Srba, Jiri

N1 - Conference code: 26

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - weighted automata, partical observability, sycnhronization, complexity

UR - http://drops.dagstuhl.de/opus/volltexte/2015/5392/

UR - http://mafalda.fdi.ucm.es/concur2015/

U2 - 10.4230/LIPIcs.CONCUR.2015.142

DO - 10.4230/LIPIcs.CONCUR.2015.142

M3 - Article in proceeding

SN - 978-3-939897-91-0

T3 - Leibniz International Proceedings in Informatics

SP - 142

EP - 154

BT - 26th International Conference on Concurrency Theory (CONCUR 2015)

A2 - Aceto, Luca

A2 - de Frutos Escrig, David

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

CY - Germany

T2 - 26th International Conference on Concurrency Theory

Y2 - 1 September 2015 through 4 September 2015

ER -

Kretínsky J, Larsen KG, Laursen S, Srba J. Polynomial Time Decidability of Weighted Synchronization under Partial Observability. I Aceto L, de Frutos Escrig D, red., 26th International Conference on Concurrency Theory (CONCUR 2015). Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2015. s. 142-154. (Leibniz International Proceedings in Informatics, Bind 42). doi: 10.4230/LIPIcs.CONCUR.2015.142

Polynomial Time Decidability of Weighted Synchronization under Partial Observability

Abstract

Konference

Adgang til dokumentet

AUB Link

Andre filer og links

Fingeraftryk

Citationsformater