---
_id: '3844'
abstract:
- lang: eng
text: The Hierarchical Timing Language (HTL) is a real-time coordination language
for distributed control systems. HTL programs must be checked for well-formedness,
race freedom, transmission safety (schedulability of inter-host communication),
and time safety (schedulability of host computation). We present a modular abstract
syntax and semantics for HTL, modular checks of well-formedness, race freedom,
and transmission safety, and modular code distribution. Our contributions here
complement previous results on HTL time safety and modular code generation. Modularity
in HTL can be utilized in easy program composition as well as fast program analysis
and code generation, but also in so-called runtime patching, where program components
may be modified at runtime.
acknowledgement: Supported by the EU ArtistDesign Network of Excellence on Embedded
Systems Design, the EU project COMBEST, the Austrian Science Funds P18913-N15 and
V00125, and Fundacao para a Ciencia e Tecnologia funds SFRH/BD/29461/2006 and PTDC/EIA/71462/2006
author:
- 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: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Eduardo
full_name: Marques, Eduardo
last_name: Marques
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
citation:
ama: 'Henzinger TA, Kirsch C, Marques E, Sokolova A. Distributed, modular HTL. In:
IEEE; 2009:171-180. doi:10.1109/RTSS.2009.9'
apa: 'Henzinger, T. A., Kirsch, C., Marques, E., & Sokolova, A. (2009). Distributed,
modular HTL (pp. 171–180). Presented at the RTSS: Real-Time Systems Symposium,
Washington, DC, United States: IEEE. https://doi.org/10.1109/RTSS.2009.9'
chicago: Henzinger, Thomas A, Christoph Kirsch, Eduardo Marques, and Ana Sokolova.
“Distributed, Modular HTL,” 171–80. IEEE, 2009. https://doi.org/10.1109/RTSS.2009.9.
ieee: 'T. A. Henzinger, C. Kirsch, E. Marques, and A. Sokolova, “Distributed, modular
HTL,” presented at the RTSS: Real-Time Systems Symposium, Washington, DC, United
States, 2009, pp. 171–180.'
ista: 'Henzinger TA, Kirsch C, Marques E, Sokolova A. 2009. Distributed, modular
HTL. RTSS: Real-Time Systems Symposium, 171–180.'
mla: Henzinger, Thomas A., et al. Distributed, Modular HTL. IEEE, 2009, pp.
171–80, doi:10.1109/RTSS.2009.9.
short: T.A. Henzinger, C. Kirsch, E. Marques, A. Sokolova, in:, IEEE, 2009, pp.
171–180.
conference:
end_date: 2009-12-04
location: Washington, DC, United States
name: 'RTSS: Real-Time Systems Symposium'
start_date: 2009-12-01
date_created: 2018-12-11T12:05:28Z
date_published: 2009-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:36Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1109/RTSS.2009.9
ec_funded: 1
file:
- access_level: open_access
checksum: b2b15a5ef71eb50d62eaa5aea7efd8c4
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:56Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4655'
file_name: IST-2012-65-v1+1_Distributed_modular_Htl.pdf
file_size: 526458
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 171 - 180
project:
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
publication_status: published
publisher: IEEE
publist_id: '2346'
pubrep_id: '65'
quality_controlled: '1'
status: public
title: Distributed, modular HTL
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...
---
_id: '3837'
abstract:
- lang: eng
text: In this paper we extend the work of Alfaro, Henzinger et al. on interface
theories for component-based design. Existing interface theories often fail to
capture functional relations between the inputs and outputs of an interface. For
example, a simple synchronous interface that takes as input a number n ≥ 0 and
returns, at the same time, as output n + 1, cannot be expressed in existing theories.
In this paper we provide a theory of relational interfaces, where such input-output
relations can be captured. Our theory supports synchronous interfaces, both stateless
and stateful. It includes explicit notions of environments and pluggability, and
satisfies fundamental properties such as preservation of refinement by composition,
and characterization of pluggability by refinement. We achieve these properties
by making reasonable restrictions on feedback loops in interface compositions.
acknowledgement: 'This work is supported by the Center for Hybrid and Embedded Software
Systems (CHESS) at UC Berkeley, which receives support from the National Science
Foundation (NSF awards #0720882 (CSR-EHS: PRET) and #0720841 (CSR-CPS)), the U.S.
Army Research Office (ARO #W911NF-07-2-0019), the U.S. Air Force Office of Scientific
Research (MURI #FA9550-06-0312), the Air Force Research Lab (AFRL), the State of
California Micro Program, and the following companies: Agilent, Bosch, Lockheed-Martin,
National Instruments, Thales and Toyota. This work is also supported by the COMBEST
and ArtistDesign projects of the European Union, and the Swiss National Science
Foundation. '
author:
- first_name: Stavros
full_name: Tripakis, Stavros
last_name: Tripakis
- first_name: Ben
full_name: Lickly, Ben
last_name: Lickly
- 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: Edward
full_name: Lee, Edward
last_name: Lee
citation:
ama: 'Tripakis S, Lickly B, Henzinger TA, Lee E. On relational interfaces. In: EMSOFT
’09 Proceedings of the Seventh ACM International Conference on Embedded Software.
ACM; 2009:67-76. doi:10.1145/1629335.1629346'
apa: 'Tripakis, S., Lickly, B., Henzinger, T. A., & Lee, E. (2009). On relational
interfaces. In EMSOFT ’09 Proceedings of the seventh ACM international conference
on Embedded software (pp. 67–76). Grenoble, France: ACM. https://doi.org/10.1145/1629335.1629346'
chicago: Tripakis, Stavros, Ben Lickly, Thomas A Henzinger, and Edward Lee. “On
Relational Interfaces.” In EMSOFT ’09 Proceedings of the Seventh ACM International
Conference on Embedded Software, 67–76. ACM, 2009. https://doi.org/10.1145/1629335.1629346.
ieee: S. Tripakis, B. Lickly, T. A. Henzinger, and E. Lee, “On relational interfaces,”
in EMSOFT ’09 Proceedings of the seventh ACM international conference on Embedded
software, Grenoble, France, 2009, pp. 67–76.
ista: 'Tripakis S, Lickly B, Henzinger TA, Lee E. 2009. On relational interfaces.
EMSOFT ’09 Proceedings of the seventh ACM international conference on Embedded
software. EMSOFT: Embedded Software , 67–76.'
mla: Tripakis, Stavros, et al. “On Relational Interfaces.” EMSOFT ’09 Proceedings
of the Seventh ACM International Conference on Embedded Software, ACM, 2009,
pp. 67–76, doi:10.1145/1629335.1629346.
short: S. Tripakis, B. Lickly, T.A. Henzinger, E. Lee, in:, EMSOFT ’09 Proceedings
of the Seventh ACM International Conference on Embedded Software, ACM, 2009, pp.
67–76.
conference:
end_date: 2009-10-16
location: Grenoble, France
name: 'EMSOFT: Embedded Software '
start_date: 2009-10-12
date_created: 2018-12-11T12:05:26Z
date_published: 2009-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:33Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.1145/1629335.1629346
ec_funded: 1
file:
- access_level: open_access
checksum: 3a70e21527dfaad2f198549ae5710786
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:57Z
date_updated: 2020-07-14T12:46:16Z
file_id: '5045'
file_name: IST-2012-70-v1+1_On_Relational_Interfaces.pdf
file_size: 310902
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 67 - 76
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication: EMSOFT '09 Proceedings of the seventh ACM international conference on
Embedded software
publication_status: published
publisher: ACM
publist_id: '2360'
pubrep_id: '70'
quality_controlled: '1'
status: public
title: On relational interfaces
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...
---
_id: '5393'
abstract:
- lang: eng
text: Gist is a tool that (a) solves the qualitative analysis problem of turn-based
probabilistic games with ω-regular objectives; and (b) synthesizes reasonable
environment assumptions for synthesis of unrealizable specifications. Our tool
provides efficient implementations of several reduction based techniques to solve
turn-based probabilistic games, and uses the analysis of turn-based probabilistic
games for synthesizing environment assumptions for unrealizable specifications.
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: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: 'Chatterjee K, Henzinger TA, Jobstmann B, Radhakrishna A. Gist: A Solver
for Probabilistic Games. IST Austria; 2009. doi:10.15479/AT:IST-2009-0003'
apa: 'Chatterjee, K., Henzinger, T. A., Jobstmann, B., & Radhakrishna, A. (2009).
Gist: A solver for probabilistic games. IST Austria. https://doi.org/10.15479/AT:IST-2009-0003'
chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, Barbara Jobstmann, and Arjun
Radhakrishna. Gist: A Solver for Probabilistic Games. IST Austria, 2009.
https://doi.org/10.15479/AT:IST-2009-0003.'
ieee: 'K. Chatterjee, T. A. Henzinger, B. Jobstmann, and A. Radhakrishna, Gist:
A solver for probabilistic games. IST Austria, 2009.'
ista: 'Chatterjee K, Henzinger TA, Jobstmann B, Radhakrishna A. 2009. Gist: A solver
for probabilistic games, IST Austria, 12p.'
mla: 'Chatterjee, Krishnendu, et al. Gist: A Solver for Probabilistic Games.
IST Austria, 2009, doi:10.15479/AT:IST-2009-0003.'
short: 'K. Chatterjee, T.A. Henzinger, B. Jobstmann, A. Radhakrishna, Gist: A Solver
for Probabilistic Games, IST Austria, 2009.'
date_created: 2018-12-12T11:39:05Z
date_published: 2009-10-09T00:00:00Z
date_updated: 2023-02-23T12:09:01Z
day: '09'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2009-0003
file:
- access_level: open_access
checksum: 49551ac552915b17593a14c993845274
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:52:58Z
date_updated: 2020-07-14T12:46:43Z
file_id: '5459'
file_name: IST-2009-0003_IST-2009-0003.pdf
file_size: 386866
relation: main_file
file_date_updated: 2020-07-14T12:46:43Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '12'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '29'
related_material:
record:
- id: '4388'
relation: later_version
status: public
status: public
title: 'Gist: A solver for probabilistic games'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...
---
_id: '5394'
abstract:
- lang: eng
text: We consider two-player games played on graphs with request-response and finitary
Streett objectives. We show these games are PSPACE-hard, improving the previous
known NP-hardness. We also improve the lower bounds on memory required by the
winning strategies for the players.
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: Florian
full_name: Horn, Florian
id: 37327ACE-F248-11E8-B48F-1D18A9856A87
last_name: Horn
citation:
ama: Chatterjee K, Henzinger TA, Horn F. Improved Lower Bounds for Request-Response
and Finitary Streett Games. IST Austria; 2009. doi:10.15479/AT:IST-2009-0002
apa: Chatterjee, K., Henzinger, T. A., & Horn, F. (2009). Improved lower
bounds for request-response and finitary Streett games. IST Austria. https://doi.org/10.15479/AT:IST-2009-0002
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. Improved
Lower Bounds for Request-Response and Finitary Streett Games. IST Austria,
2009. https://doi.org/10.15479/AT:IST-2009-0002.
ieee: K. Chatterjee, T. A. Henzinger, and F. Horn, Improved lower bounds for
request-response and finitary Streett games. IST Austria, 2009.
ista: Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response
and finitary Streett games, IST Austria, 11p.
mla: Chatterjee, Krishnendu, et al. Improved Lower Bounds for Request-Response
and Finitary Streett Games. IST Austria, 2009, doi:10.15479/AT:IST-2009-0002.
short: K. Chatterjee, T.A. Henzinger, F. Horn, Improved Lower Bounds for Request-Response
and Finitary Streett Games, IST Austria, 2009.
date_created: 2018-12-12T11:39:05Z
date_published: 2009-09-09T00:00:00Z
date_updated: 2020-07-14T23:07:47Z
day: '09'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2009-0002
file:
- access_level: open_access
checksum: 1c50a9723fbae1b2c46d18138968efb3
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:50Z
date_updated: 2020-07-14T12:46:43Z
file_id: '5511'
file_name: IST-2009-0002_IST-2009-0002.pdf
file_size: 238091
relation: main_file
file_date_updated: 2020-07-14T12:46:43Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '11'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '30'
status: public
title: Improved lower bounds for request-response and finitary Streett games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...
---
_id: '5395'
abstract:
- lang: eng
text: 'We study observation-based strategies for partially-observable Markov decision
processes (POMDPs) with omega-regular objectives. An observation-based strategy
relies on partial information about the history of a play, namely, on the past
sequence of observa- tions. We consider the qualitative analysis problem: given
a POMDP with an omega-regular objective, whether there is an observation-based
strategy to achieve the objective with probability 1 (almost-sure winning), or
with positive probability (positive winning). Our main results are twofold. First,
we present a complete picture of the computational complexity of the qualitative
analysis of POMDPs with parity objectives (a canonical form to express omega-regular
objectives) and its subclasses. Our contribution consists in establishing several
upper and lower bounds that were not known in literature. Second, we present optimal
bounds (matching upper and lower bounds) on the memory required by pure and randomized
observation-based strategies for the qualitative analysis of POMDPs with parity
objectives and its subclasses.'
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Chatterjee K, Doyen L, Henzinger TA. Qualitative Analysis of Partially-Observable
Markov Decision Processes. IST Austria; 2009. doi:10.15479/AT:IST-2009-0001
apa: Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). Qualitative analysis
of partially-observable Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2009-0001
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. Qualitative
Analysis of Partially-Observable Markov Decision Processes. IST Austria, 2009.
https://doi.org/10.15479/AT:IST-2009-0001.
ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, Qualitative analysis of partially-observable
Markov decision processes. IST Austria, 2009.
ista: Chatterjee K, Doyen L, Henzinger TA. 2009. Qualitative analysis of partially-observable
Markov decision processes, IST Austria, 20p.
mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of Partially-Observable
Markov Decision Processes. IST Austria, 2009, doi:10.15479/AT:IST-2009-0001.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, Qualitative Analysis of Partially-Observable
Markov Decision Processes, IST Austria, 2009.
date_created: 2018-12-12T11:39:05Z
date_published: 2009-09-09T00:00:00Z
date_updated: 2023-02-23T11:45:39Z
day: '09'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2009-0001
file:
- access_level: open_access
checksum: 04d9cc065cc19598a4e8631c47f1a562
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:25Z
date_updated: 2020-07-14T12:46:43Z
file_id: '5486'
file_name: IST-2009-0001_IST-2009-0001.pdf
file_size: 342088
relation: main_file
file_date_updated: 2020-07-14T12:46:43Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '31'
related_material:
record:
- id: '3855'
relation: later_version
status: public
status: public
title: Qualitative analysis of partially-observable Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...