---
_id: '1499'
abstract:
- lang: eng
  text: "We consider weighted automata with both positive and negative integer weights
    on edges and\r\nstudy the problem of synchronization using adaptive strategies
    that may only observe whether\r\nthe current weight-level is negative or nonnegative.
    We show that the synchronization problem is decidable in polynomial time for deterministic
    weighted automata."
acknowledgement: "The research leading to these results has received funding from
  the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement
  601148 (CASSTING), EU FP7 FET project SENSATION, Sino-Danish Basic Research Center
  IDAE4CPS, the European Research Council (ERC) under grant agreement 267989 (QUAREM),
  the Austrian Science Fund (FWF) project S11402-N23 (RiSE) and Z211-N23 (Wittgenstein
  Award), the Czech Science Foundation under grant agreement P202/12/G061, and People
  Programme (Marie Curie Actions) of the European Union’s Seventh Framework\r\nProgramme
  (FP7/2007-2013) REA Grant No 291734."
alternative_title:
- LIPIcs
author:
- first_name: Jan
  full_name: Kretinsky, Jan
  id: 44CEF464-F248-11E8-B48F-1D18A9856A87
  last_name: Kretinsky
  orcid: 0000-0002-8122-2881
- first_name: Kim
  full_name: Larsen, Kim
  last_name: Larsen
- first_name: Simon
  full_name: Laursen, Simon
  last_name: Laursen
- first_name: Jiří
  full_name: Srba, Jiří
  last_name: Srba
citation:
  ama: 'Kretinsky J, Larsen K, Laursen S, Srba J. Polynomial time decidability of
    weighted synchronization under partial observability. In: Vol 42. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2015:142-154. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2015.142">10.4230/LIPIcs.CONCUR.2015.142</a>'
  apa: 'Kretinsky, J., Larsen, K., Laursen, S., &#38; Srba, J. (2015). Polynomial
    time decidability of weighted synchronization under partial observability (Vol.
    42, pp. 142–154). Presented at the CONCUR: Concurrency Theory, Madrid, Spain:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2015.142">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>'
  chicago: Kretinsky, Jan, Kim Larsen, Simon Laursen, and Jiří Srba. “Polynomial Time
    Decidability of Weighted Synchronization under Partial Observability,” 42:142–54.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2015.142">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>.
  ieee: 'J. Kretinsky, K. Larsen, S. Laursen, and J. Srba, “Polynomial time decidability
    of weighted synchronization under partial observability,” presented at the CONCUR:
    Concurrency Theory, Madrid, Spain, 2015, vol. 42, pp. 142–154.'
  ista: 'Kretinsky J, Larsen K, Laursen S, Srba J. 2015. Polynomial time decidability
    of weighted synchronization under partial observability. CONCUR: Concurrency Theory,
    LIPIcs, vol. 42, 142–154.'
  mla: Kretinsky, Jan, et al. <i>Polynomial Time Decidability of Weighted Synchronization
    under Partial Observability</i>. Vol. 42, Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2015, pp. 142–54, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2015.142">10.4230/LIPIcs.CONCUR.2015.142</a>.
  short: J. Kretinsky, K. Larsen, S. Laursen, J. Srba, in:, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2015, pp. 142–154.
conference:
  end_date: 2015-09-04
  location: Madrid, Spain
  name: 'CONCUR: Concurrency Theory'
  start_date: 2015-09-01
date_created: 2018-12-11T11:52:22Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2025-04-15T06:26:02Z
day: '01'
ddc:
- '000'
- '003'
department:
- _id: ToHe
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2015.142
ec_funded: 1
file:
- access_level: open_access
  checksum: 49eb5021caafaabe5356c65b9c5f8c9c
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:08:12Z
  date_updated: 2020-07-14T12:44:58Z
  file_id: '4672'
  file_name: IST-2016-498-v1+1_32.pdf
  file_size: 623563
  relation: main_file
file_date_updated: 2020-07-14T12:44:58Z
has_accepted_license: '1'
intvolume: '        42'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 142 - 154
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5680'
pubrep_id: '498'
quality_controlled: '1'
scopus_import: 1
status: public
title: Polynomial time decidability of weighted synchronization under partial observability
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 42
year: '2015'
...