---
_id: '5406'
abstract:
- lang: eng
  text: 'We consider the distributed synthesis problem fortemporal logic specifications.
    Traditionally, the problem has been studied for LTL, and the previous results
    show that the problem is decidable iff there is no information fork in the architecture.
    We consider the problem for fragments of LTLand our main results are as follows:
    (1) We show that the problem is undecidable for architectures with information
    forks even for the fragment of LTL with temporal operators restricted to next
    and eventually. (2) For specifications restricted to globally along with non-nested
    next operators, we establish decidability (in EXPSPACE) for star architectures
    where the processes receive disjoint inputs, whereas we establish undecidability
    for architectures containing an information fork-meet structure. (3)Finally, we
    consider LTL without the next operator, and establish decidability (NEXPTIME-complete)
    for all architectures for a fragment that consists of a set of safety assumptions,
    and a set of guarantees where each guarantee is a safety, reachability, or liveness
    condition.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
- first_name: Andreas
  full_name: Pavlogiannis, Andreas
  id: 49704004-F248-11E8-B48F-1D18A9856A87
  last_name: Pavlogiannis
  orcid: 0000-0002-8943-0722
citation:
  ama: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. <i>Distributed Synthesis
    for LTL Fragments</i>. IST Austria; 2013. doi:<a href="https://doi.org/10.15479/AT:IST-2013-130-v1-1">10.15479/AT:IST-2013-130-v1-1</a>
  apa: Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Pavlogiannis, A. (2013).
    <i>Distributed synthesis for LTL Fragments</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2013-130-v1-1">https://doi.org/10.15479/AT:IST-2013-130-v1-1</a>
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
    <i>Distributed Synthesis for LTL Fragments</i>. IST Austria, 2013. <a href="https://doi.org/10.15479/AT:IST-2013-130-v1-1">https://doi.org/10.15479/AT:IST-2013-130-v1-1</a>.
  ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, <i>Distributed
    synthesis for LTL Fragments</i>. IST Austria, 2013.
  ista: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
    for LTL Fragments, IST Austria, 11p.
  mla: Chatterjee, Krishnendu, et al. <i>Distributed Synthesis for LTL Fragments</i>.
    IST Austria, 2013, doi:<a href="https://doi.org/10.15479/AT:IST-2013-130-v1-1">10.15479/AT:IST-2013-130-v1-1</a>.
  short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis
    for LTL Fragments, IST Austria, 2013.
date_created: 2018-12-12T11:39:09Z
date_published: 2013-07-08T00:00:00Z
date_updated: 2025-06-26T08:33:42Z
day: '08'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2013-130-v1-1
file:
- access_level: open_access
  checksum: 855513ebaf6f72228800c5fdb522f93c
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:54:18Z
  date_updated: 2020-07-14T12:46:45Z
  file_id: '5540'
  file_name: IST-2013-130-v1+1_Distributed_Synthesis.pdf
  file_size: 467895
  relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '11'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '130'
related_material:
  record:
  - id: '1376'
    relation: later_version
    status: public
status: public
title: Distributed synthesis for LTL Fragments
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...