---
_id: '3302'
abstract:
- lang: eng
text: Cloud computing aims to give users virtually unlimited pay-per-use computing
resources without the burden of managing the underlying infrastructure. We present
a new job execution environment Flextic that exploits scal- able static scheduling
techniques to provide the user with a flexible pricing model, such as a tradeoff
between dif- ferent degrees of execution speed and execution price, and at the
same time, reduce scheduling overhead for the cloud provider. We have evaluated
a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various
data parallel jobs from machine learning, im- age processing, and gene sequencing
that we considered, Flextic has low scheduling overhead and reduces job du- ration
by up to 15% compared to Hadoop, a dynamic cloud scheduler.
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: Anmol
full_name: Singh, Anmol
id: 72A86902-E99F-11E9-9F62-915534D1B916
last_name: Singh
- first_name: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: 'Henzinger TA, Singh A, Singh V, Wies T, Zufferey D. Static scheduling in clouds.
In: USENIX; 2011:1-6.'
apa: 'Henzinger, T. A., Singh, A., Singh, V., Wies, T., & Zufferey, D. (2011).
Static scheduling in clouds (pp. 1–6). Presented at the HotCloud: Workshop on
Hot Topics in Cloud Computing, USENIX.'
chicago: Henzinger, Thomas A, Anmol Singh, Vasu Singh, Thomas Wies, and Damien Zufferey.
“Static Scheduling in Clouds,” 1–6. USENIX, 2011.
ieee: 'T. A. Henzinger, A. Singh, V. Singh, T. Wies, and D. Zufferey, “Static scheduling
in clouds,” presented at the HotCloud: Workshop on Hot Topics in Cloud Computing,
2011, pp. 1–6.'
ista: 'Henzinger TA, Singh A, Singh V, Wies T, Zufferey D. 2011. Static scheduling
in clouds. HotCloud: Workshop on Hot Topics in Cloud Computing, 1–6.'
mla: Henzinger, Thomas A., et al. Static Scheduling in Clouds. USENIX, 2011,
pp. 1–6.
short: T.A. Henzinger, A. Singh, V. Singh, T. Wies, D. Zufferey, in:, USENIX, 2011,
pp. 1–6.
conference:
end_date: 2011-06-15
name: 'HotCloud: Workshop on Hot Topics in Cloud Computing'
start_date: 2011-06-14
corr_author: '1'
date_created: 2018-12-11T12:02:33Z
date_published: 2011-06-14T00:00:00Z
date_updated: 2024-10-09T20:54:34Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: ToHe
file:
- access_level: open_access
checksum: 21a461ac004bb535c83320fe79b30375
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:14Z
date_updated: 2020-07-14T12:46:06Z
file_id: '5333'
file_name: IST-2012-90-v1+1_Static_scheduling_in_clouds.pdf
file_size: 232770
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 1 - 6
publication_status: published
publisher: USENIX
publist_id: '3338'
pubrep_id: '90'
quality_controlled: '1'
status: public
title: Static scheduling in clouds
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3315'
abstract:
- lang: eng
text: We consider two-player games played in real time on game structures with clocks
where the objectives of players are described using parity conditions. The games
are concurrent in that at each turn, both players independently propose a time
delay and an action, and the action with the shorter delay is chosen. To prevent
a player from winning by blocking time, we restrict each player to play strategies
that ensure that the player cannot be responsible for causing a zeno run. First,
we present an efficient reduction of these games to turn-based (i.e., not concurrent)
finite-state (i.e., untimed) parity games. Our reduction improves the best known
complexity for solving timed parity games. Moreover, the rich class of algorithms
for classical parity games can now be applied to timed parity games. The states
of the resulting game are based on clock regions of the original game, and the
state space of the finite game is linear in the size of the region graph. Second,
we consider two restricted classes of strategies for the player that represents
the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust
winning strategies. Using a limit-robust winning strategy, the controller cannot
choose an exact real-valued time delay but must allow for some nonzero jitter
in each of its actions. If there is a given lower bound on the jitter, then the
strategy is bounded-robust winning. We show that exact strategies are more powerful
than limit-robust strategies, which are more powerful than bounded-robust winning
strategies for any bound. For both kinds of robust strategies, we present efficient
reductions to standard timed automaton games. These reductions provide algorithms
for the synthesis of robust real-time controllers.
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: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: Complexity and robustness.
Logical Methods in Computer Science. 2011;7(4). doi:10.2168/LMCS-7(4:8)2011'
apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2011). Timed parity games:
Complexity and robustness. Logical Methods in Computer Science. International
Federation of Computational Logic. https://doi.org/10.2168/LMCS-7(4:8)2011'
chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Timed
Parity Games: Complexity and Robustness.” Logical Methods in Computer Science.
International Federation of Computational Logic, 2011. https://doi.org/10.2168/LMCS-7(4:8)2011.'
ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Timed parity games: Complexity
and robustness,” Logical Methods in Computer Science, vol. 7, no. 4. International
Federation of Computational Logic, 2011.'
ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2011. Timed parity games: Complexity
and robustness. Logical Methods in Computer Science. 7(4).'
mla: 'Chatterjee, Krishnendu, et al. “Timed Parity Games: Complexity and Robustness.”
Logical Methods in Computer Science, vol. 7, no. 4, International Federation
of Computational Logic, 2011, doi:10.2168/LMCS-7(4:8)2011.'
short: K. Chatterjee, T.A. Henzinger, V. Prabhu, Logical Methods in Computer Science
7 (2011).
corr_author: '1'
date_created: 2018-12-11T12:02:37Z
date_published: 2011-12-14T00:00:00Z
date_updated: 2024-10-09T20:54:33Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.2168/LMCS-7(4:8)2011
ec_funded: 1
file:
- access_level: open_access
checksum: 3480e1594bbef25ff7462fa93a8a814e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:42Z
date_updated: 2020-07-14T12:46:07Z
file_id: '5231'
file_name: IST-2016-86-v2+1_1011.0688_3_.pdf
file_size: 588863
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 7'
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '3324'
pubrep_id: '506'
quality_controlled: '1'
related_material:
record:
- id: '3876'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Timed parity games: Complexity and robustness'
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2011'
...
---
_id: '3316'
abstract:
- lang: eng
text: In addition to being correct, a system should be robust, that is, it should
behave reasonably even after receiving unexpected inputs. In this paper, we summarize
two formal notions of robustness that we have introduced previously for reactive
systems. One of the notions is based on assigning costs for failures on a user-provided
notion of incorrect transitions in a specification. Here, we define a system to
be robust if a finite number of incorrect inputs does not lead to an infinite
number of incorrect outputs. We also give a more refined notion of robustness
that aims to minimize the ratio of output failures to input failures. The second
notion is aimed at liveness. In contrast to the previous notion, it has no concept
of recovery from an error. Instead, it compares the ratio of the number of liveness
constraints that the system violates to the number of liveness constraints that
the environment violates.
article_processing_charge: No
author:
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Karin
full_name: Greimel, Karin
last_name: Greimel
- 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
citation:
ama: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. Specification-centered
robustness. In: 6th IEEE International Symposium on Industrial and Embedded
Systems. IEEE; 2011:176-185. doi:10.1109/SIES.2011.5953660'
apa: 'Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., & Jobstmann,
B. (2011). Specification-centered robustness. In 6th IEEE International Symposium
on Industrial and Embedded Systems (pp. 176–185). Vasteras, Sweden: IEEE.
https://doi.org/10.1109/SIES.2011.5953660'
chicago: Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger,
and Barbara Jobstmann. “Specification-Centered Robustness.” In 6th IEEE International
Symposium on Industrial and Embedded Systems, 176–85. IEEE, 2011. https://doi.org/10.1109/SIES.2011.5953660.
ieee: R. Bloem, K. Chatterjee, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Specification-centered
robustness,” in 6th IEEE International Symposium on Industrial and Embedded
Systems, Vasteras, Sweden, 2011, pp. 176–185.
ista: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. 2011. Specification-centered
robustness. 6th IEEE International Symposium on Industrial and Embedded Systems.
SIES: International Symposium on Industrial Embedded Systems, 176–185.'
mla: Bloem, Roderick, et al. “Specification-Centered Robustness.” 6th IEEE International
Symposium on Industrial and Embedded Systems, IEEE, 2011, pp. 176–85, doi:10.1109/SIES.2011.5953660.
short: R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, B. Jobstmann, in:, 6th
IEEE International Symposium on Industrial and Embedded Systems, IEEE, 2011, pp.
176–185.
conference:
end_date: 2011-06-17
location: Vasteras, Sweden
name: 'SIES: International Symposium on Industrial Embedded Systems'
start_date: 2011-06-15
date_created: 2018-12-11T12:02:38Z
date_published: 2011-07-14T00:00:00Z
date_updated: 2025-07-10T11:52:29Z
day: '14'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/SIES.2011.5953660
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openlib.tugraz.at/download.php?id=5cb57c8a49344&location=browse
month: '07'
oa: 1
oa_version: Published Version
page: 176 - 185
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 6th IEEE International Symposium on Industrial and Embedded Systems
publication_status: published
publisher: IEEE
publist_id: '3323'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Specification-centered robustness
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3323'
abstract:
- lang: eng
text: We present a new decidable logic called TREX for expressing constraints about
imperative tree data structures. In particular, TREX supports a transitive closure
operator that can express reachability constraints, which often appear in data
structure invariants. We show that our logic is closed under weakest precondition
computation, which enables its use for automated software verification. We further
show that satisfiability of formulas in TREX is decidable in NP. The low complexity
makes it an attractive alternative to more expensive logics such as monadic second-order
logic (MSOL) over trees, which have been traditionally used for reasoning about
tree data structures.
alternative_title:
- 'LNAI '
author:
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Marco
full_name: Muñiz, Marco
last_name: Muñiz
- first_name: Viktor
full_name: Kuncak, Viktor
last_name: Kuncak
citation:
ama: 'Wies T, Muñiz M, Kuncak V. An efficient decision procedure for imperative
tree data structures. In: Vol 6803. Springer; 2011:476-491. doi:10.1007/978-3-642-22438-6_36'
apa: 'Wies, T., Muñiz, M., & Kuncak, V. (2011). An efficient decision procedure
for imperative tree data structures (Vol. 6803, pp. 476–491). Presented at the
CADE 23: Automated Deduction , Wrocław, Poland: Springer. https://doi.org/10.1007/978-3-642-22438-6_36'
chicago: Wies, Thomas, Marco Muñiz, and Viktor Kuncak. “An Efficient Decision Procedure
for Imperative Tree Data Structures,” 6803:476–91. Springer, 2011. https://doi.org/10.1007/978-3-642-22438-6_36.
ieee: 'T. Wies, M. Muñiz, and V. Kuncak, “An efficient decision procedure for imperative
tree data structures,” presented at the CADE 23: Automated Deduction , Wrocław,
Poland, 2011, vol. 6803, pp. 476–491.'
ista: 'Wies T, Muñiz M, Kuncak V. 2011. An efficient decision procedure for imperative
tree data structures. CADE 23: Automated Deduction , LNAI , vol. 6803, 476–491.'
mla: Wies, Thomas, et al. An Efficient Decision Procedure for Imperative Tree
Data Structures. Vol. 6803, Springer, 2011, pp. 476–91, doi:10.1007/978-3-642-22438-6_36.
short: T. Wies, M. Muñiz, V. Kuncak, in:, Springer, 2011, pp. 476–491.
conference:
end_date: 2011-08-05
location: Wrocław, Poland
name: 'CADE 23: Automated Deduction '
start_date: 2011-07-31
corr_author: '1'
date_created: 2018-12-11T12:02:40Z
date_published: 2011-07-19T00:00:00Z
date_updated: 2024-10-09T20:54:31Z
day: '19'
department:
- _id: ToHe
doi: 10.1007/978-3-642-22438-6_36
intvolume: ' 6803'
language:
- iso: eng
month: '07'
oa_version: None
page: 476 - 491
publication_status: published
publisher: Springer
publist_id: '3312'
quality_controlled: '1'
related_material:
record:
- id: '5383'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: An efficient decision procedure for imperative tree data structures
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6803
year: '2011'
...
---
_id: '3324'
abstract:
- lang: eng
text: 'Automated termination provers often use the following schema to prove that
a program terminates: construct a relational abstraction of the program''s transition
relation and then show that the relational abstraction is well-founded. The focus
of current tools has been on developing sophisticated techniques for constructing
the abstractions while relying on known decidable logics (such as linear arithmetic)
to express them. We believe we can significantly increase the class of programs
that are amenable to automated termination proofs by identifying more expressive
decidable logics for reasoning about well-founded relations. We therefore present
a new decision procedure for reasoning about multiset orderings, which are among
the most powerful orderings used to prove termination. We show that, using our
decision procedure, one can automatically prove termination of natural abstractions
of programs.'
alternative_title:
- LNCS
author:
- first_name: Ruzica
full_name: Piskac, Ruzica
last_name: Piskac
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
citation:
ama: 'Piskac R, Wies T. Decision procedures for automating termination proofs. In:
Jhala R, Schmidt D, eds. Vol 6538. Springer; 2011:371-386. doi:10.1007/978-3-642-18275-4_26'
apa: 'Piskac, R., & Wies, T. (2011). Decision procedures for automating termination
proofs. In R. Jhala & D. Schmidt (Eds.) (Vol. 6538, pp. 371–386). Presented
at the VMCAI: Verification Model Checking and Abstract Interpretation, Texas,
USA: Springer. https://doi.org/10.1007/978-3-642-18275-4_26'
chicago: Piskac, Ruzica, and Thomas Wies. “Decision Procedures for Automating Termination
Proofs.” edited by Ranjit Jhala and David Schmidt, 6538:371–86. Springer, 2011.
https://doi.org/10.1007/978-3-642-18275-4_26.
ieee: 'R. Piskac and T. Wies, “Decision procedures for automating termination proofs,”
presented at the VMCAI: Verification Model Checking and Abstract Interpretation,
Texas, USA, 2011, vol. 6538, pp. 371–386.'
ista: 'Piskac R, Wies T. 2011. Decision procedures for automating termination proofs.
VMCAI: Verification Model Checking and Abstract Interpretation, LNCS, vol. 6538,
371–386.'
mla: Piskac, Ruzica, and Thomas Wies. Decision Procedures for Automating Termination
Proofs. Edited by Ranjit Jhala and David Schmidt, vol. 6538, Springer, 2011,
pp. 371–86, doi:10.1007/978-3-642-18275-4_26.
short: R. Piskac, T. Wies, in:, R. Jhala, D. Schmidt (Eds.), Springer, 2011, pp.
371–386.
conference:
end_date: 2011-01-25
location: Texas, USA
name: 'VMCAI: Verification Model Checking and Abstract Interpretation'
start_date: 2011-01-23
date_created: 2018-12-11T12:02:40Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:39Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-18275-4_26
editor:
- first_name: Ranjit
full_name: Jhala, Ranjit
last_name: Jhala
- first_name: David
full_name: Schmidt, David
last_name: Schmidt
intvolume: ' 6538'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/170697/
month: '01'
oa: 1
oa_version: Submitted Version
page: 371 - 386
publication_status: published
publisher: Springer
publist_id: '3311'
quality_controlled: '1'
scopus_import: 1
status: public
title: Decision procedures for automating termination proofs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6538
year: '2011'
...
---
_id: '3325'
abstract:
- lang: eng
text: We introduce streaming data string transducers that map input data strings
to output data strings in a single left-to-right pass in linear time. Data strings
are (unbounded) sequences of data values, tagged with symbols from a finite set,
over a potentially infinite data do- main that supports only the operations of
equality and ordering. The transducer uses a finite set of states, a finite set
of variables ranging over the data domain, and a finite set of variables ranging
over data strings. At every step, it can make decisions based on the next in-
put symbol, updating its state, remembering the input data value in its data variables,
and updating data-string variables by concatenat- ing data-string variables and
new symbols formed from data vari- ables, while avoiding duplication. We establish
that the problems of checking functional equivalence of two streaming transducers,
and of checking whether a streaming transducer satisfies pre/post verification
conditions specified by streaming acceptors over in- put/output data-strings,
are in PSPACE. We identify a class of imperative and a class of functional pro-
grams, manipulating lists of data items, which can be effectively translated to
streaming data-string transducers. The imperative pro- grams dynamically modify
a singly-linked heap by changing next- pointers of heap-nodes and by adding new
nodes. The main re- striction specifies how the next-pointers can be used for
traversal. We also identify an expressively equivalent fragment of functional
programs that traverse a list using syntactically restricted recursive calls.
Our results lead to algorithms for assertion checking and for checking functional
equivalence of two programs, written possibly in different programming styles,
for commonly used routines such as insert, delete, and reverse.
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
citation:
ama: 'Alur R, Cerny P. Streaming transducers for algorithmic verification of single
pass list processing programs. In: Vol 46. ACM; 2011:599-610. doi:10.1145/1926385.1926454'
apa: 'Alur, R., & Cerny, P. (2011). Streaming transducers for algorithmic verification
of single pass list processing programs (Vol. 46, pp. 599–610). Presented at the
POPL: Principles of Programming Languages, Texas, USA: ACM. https://doi.org/10.1145/1926385.1926454'
chicago: Alur, Rajeev, and Pavol Cerny. “Streaming Transducers for Algorithmic Verification
of Single Pass List Processing Programs,” 46:599–610. ACM, 2011. https://doi.org/10.1145/1926385.1926454.
ieee: 'R. Alur and P. Cerny, “Streaming transducers for algorithmic verification
of single pass list processing programs,” presented at the POPL: Principles of
Programming Languages, Texas, USA, 2011, vol. 46, no. 1, pp. 599–610.'
ista: 'Alur R, Cerny P. 2011. Streaming transducers for algorithmic verification
of single pass list processing programs. POPL: Principles of Programming Languages
vol. 46, 599–610.'
mla: Alur, Rajeev, and Pavol Cerny. Streaming Transducers for Algorithmic Verification
of Single Pass List Processing Programs. Vol. 46, no. 1, ACM, 2011, pp. 599–610,
doi:10.1145/1926385.1926454.
short: R. Alur, P. Cerny, in:, ACM, 2011, pp. 599–610.
conference:
end_date: 2011-01-28
location: Texas, USA
name: 'POPL: Principles of Programming Languages'
start_date: 2011-01-26
date_created: 2018-12-11T12:02:41Z
date_published: 2011-01-26T00:00:00Z
date_updated: 2025-09-30T09:10:38Z
day: '26'
department:
- _id: ToHe
doi: 10.1145/1926385.1926454
external_id:
isi:
- '000289656100050'
intvolume: ' 46'
isi: 1
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 599 - 610
publication_status: published
publisher: ACM
publist_id: '3310'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Streaming transducers for algorithmic verification of single pass list processing
programs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 46
year: '2011'
...
---
_id: '3326'
abstract:
- lang: eng
text: 'Weighted automata map input words to numerical values. Ap- plications of
weighted automata include formal verification of quantitative properties, as well
as text, speech, and image processing. A weighted au- tomaton is defined with
respect to a semiring. For the tropical semiring, the weight of a run is the sum
of the weights of the transitions taken along the run, and the value of a word
is the minimal weight of an accepting run on it. In the 90’s, Krob studied the
decidability of problems on rational series defined with respect to the tropical
semiring. Rational series are strongly related to weighted automata, and Krob’s
results apply to them. In par- ticular, it follows from Krob’s results that the
universality problem (that is, deciding whether the values of all words are below
some threshold) is decidable for weighted automata defined with respect to the
tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable
when the domain is ∪ {∞}. In this paper we continue the study of the borders of
decidability in weighted automata, describe alternative and direct proofs of the
above results, and tighten them further. Unlike the proofs of Krob, which are
algebraic in their nature, our proofs stay in the terrain of state machines, and
the reduction is from the halting problem of a two-counter machine. This enables
us to significantly simplify Krob’s reasoning, make the un- decidability result
accessible to the automata-theoretic community, and strengthen it to apply already
to a very simple class of automata: all the states are accepting, there are no
initial nor final weights, and all the weights on the transitions are from the
set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten
also the decidability re- sults and to show that the universality problem for
weighted automata defined with respect to the tropical semiring with domain ∪
{∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus
draw a sharper picture about the decidability of decision problems for weighted
automata, in both the front of containment vs. universality and the front of the
∪ {∞} vs. the ∪ {∞} domains.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shaull
full_name: Almagor, Shaull
last_name: Almagor
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: 'Almagor S, Boker U, Kupferman O. What’s decidable about weighted automata.
In: Vol 6996. Springer; 2011:482-491. doi:10.1007/978-3-642-24372-1_37'
apa: 'Almagor, S., Boker, U., & Kupferman, O. (2011). What’s decidable about
weighted automata (Vol. 6996, pp. 482–491). Presented at the ATVA: Automated Technology
for Verification and Analysis, Taipei, Taiwan: Springer. https://doi.org/10.1007/978-3-642-24372-1_37'
chicago: Almagor, Shaull, Udi Boker, and Orna Kupferman. “What’s Decidable about
Weighted Automata,” 6996:482–91. Springer, 2011. https://doi.org/10.1007/978-3-642-24372-1_37.
ieee: 'S. Almagor, U. Boker, and O. Kupferman, “What’s decidable about weighted
automata,” presented at the ATVA: Automated Technology for Verification and Analysis,
Taipei, Taiwan, 2011, vol. 6996, pp. 482–491.'
ista: 'Almagor S, Boker U, Kupferman O. 2011. What’s decidable about weighted automata.
ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6996, 482–491.'
mla: Almagor, Shaull, et al. What’s Decidable about Weighted Automata. Vol.
6996, Springer, 2011, pp. 482–91, doi:10.1007/978-3-642-24372-1_37.
short: S. Almagor, U. Boker, O. Kupferman, in:, Springer, 2011, pp. 482–491.
conference:
end_date: 2011-10-14
location: Taipei, Taiwan
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2011-10-11
date_created: 2018-12-11T12:02:41Z
date_published: 2011-10-14T00:00:00Z
date_updated: 2025-01-14T12:09:37Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-24372-1_37
file:
- access_level: open_access
checksum: a7ca08a2cb1b6925f4c18a3034ae5659
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:08:32Z
date_updated: 2020-07-14T12:46:07Z
file_id: '7868'
file_name: 2011_LNCS_Almagor.pdf
file_size: 182309
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 6996'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 482 - 491
publication_status: published
publisher: Springer
publist_id: '3309'
quality_controlled: '1'
scopus_import: '1'
status: public
title: What’s decidable about weighted automata
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6996
year: '2011'
...
---
_id: '3352'
abstract:
- lang: eng
text: Exploring the connection of biology with reactive systems to better understand
living systems.
article_processing_charge: No
author:
- first_name: Jasmin
full_name: Fisher, Jasmin
last_name: Fisher
- first_name: David
full_name: Harel, David
last_name: Harel
- 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: Fisher J, Harel D, Henzinger TA. Biology as reactivity. Communications of
the ACM. 2011;54(10):72-82. doi:10.1145/2001269.2001289
apa: Fisher, J., Harel, D., & Henzinger, T. A. (2011). Biology as reactivity.
Communications of the ACM. ACM. https://doi.org/10.1145/2001269.2001289
chicago: Fisher, Jasmin, David Harel, and Thomas A Henzinger. “Biology as Reactivity.”
Communications of the ACM. ACM, 2011. https://doi.org/10.1145/2001269.2001289.
ieee: J. Fisher, D. Harel, and T. A. Henzinger, “Biology as reactivity,” Communications
of the ACM, vol. 54, no. 10. ACM, pp. 72–82, 2011.
ista: Fisher J, Harel D, Henzinger TA. 2011. Biology as reactivity. Communications
of the ACM. 54(10), 72–82.
mla: Fisher, Jasmin, et al. “Biology as Reactivity.” Communications of the ACM,
vol. 54, no. 10, ACM, 2011, pp. 72–82, doi:10.1145/2001269.2001289.
short: J. Fisher, D. Harel, T.A. Henzinger, Communications of the ACM 54 (2011)
72–82.
date_created: 2018-12-11T12:02:50Z
date_published: 2011-10-01T00:00:00Z
date_updated: 2025-09-30T09:06:32Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2001269.2001289
ec_funded: 1
external_id:
isi:
- '000296022500019'
intvolume: ' 54'
isi: 1
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
page: 72 - 82
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Communications of the ACM
publication_status: published
publisher: ACM
publist_id: '3267'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Biology as reactivity
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 54
year: '2011'
...
---
_id: '3353'
abstract:
- lang: eng
text: 'Compositional theories are crucial when designing large and complex systems
from smaller components. In this work we propose such a theory for synchronous
concurrent systems. Our approach follows so-called interface theories, which use
game-theoretic interpretations of composition and refinement. These are appropriate
for systems with distinct inputs and outputs, and explicit conditions on inputs
that must be enforced during composition. Our interfaces model systems that execute
in an infinite sequence of synchronous rounds. At each round, a contract must
be satisfied. The contract is simply a relation specifying the set of valid input/output
pairs. Interfaces can be composed by parallel, serial or feedback composition.
A refinement relation between interfaces is defined, and shown to have two main
properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability,
namely, the ability to replace an interface by another one in any context. Shared
refinement and abstraction operators, corresponding to greatest lower and least
upper bounds with respect to refinement, are also defined. Input-complete interfaces,
that impose no restrictions on inputs, and deterministic interfaces, that produce
a unique output for any legal input, are discussed as special cases, and an interesting
duality between the two classes is exposed. A number of illustrative examples
are provided, as well as algorithms to compute compositions, check refinement,
and so on, for finite-state interfaces.'
article_number: '14'
article_processing_charge: No
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. A theory of synchronous relational
interfaces. ACM Transactions on Programming Languages and Systems (TOPLAS).
2011;33(4). doi:10.1145/1985342.1985345
apa: Tripakis, S., Lickly, B., Henzinger, T. A., & Lee, E. (2011). A theory
of synchronous relational interfaces. ACM Transactions on Programming Languages
and Systems (TOPLAS). ACM. https://doi.org/10.1145/1985342.1985345
chicago: Tripakis, Stavros, Ben Lickly, Thomas A Henzinger, and Edward Lee. “A Theory
of Synchronous Relational Interfaces.” ACM Transactions on Programming Languages
and Systems (TOPLAS). ACM, 2011. https://doi.org/10.1145/1985342.1985345.
ieee: S. Tripakis, B. Lickly, T. A. Henzinger, and E. Lee, “A theory of synchronous
relational interfaces,” ACM Transactions on Programming Languages and Systems
(TOPLAS), vol. 33, no. 4. ACM, 2011.
ista: Tripakis S, Lickly B, Henzinger TA, Lee E. 2011. A theory of synchronous relational
interfaces. ACM Transactions on Programming Languages and Systems (TOPLAS). 33(4),
14.
mla: Tripakis, Stavros, et al. “A Theory of Synchronous Relational Interfaces.”
ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 33,
no. 4, 14, ACM, 2011, doi:10.1145/1985342.1985345.
short: S. Tripakis, B. Lickly, T.A. Henzinger, E. Lee, ACM Transactions on Programming
Languages and Systems (TOPLAS) 33 (2011).
date_created: 2018-12-11T12:02:51Z
date_published: 2011-07-01T00:00:00Z
date_updated: 2025-09-30T09:05:52Z
day: '01'
ddc:
- '000'
- '005'
department:
- _id: ToHe
doi: 10.1145/1985342.1985345
ec_funded: 1
external_id:
isi:
- '000292766400003'
file:
- access_level: open_access
checksum: 5d44a8aa81e33210649beae507602138
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:45Z
date_updated: 2020-07-14T12:46:09Z
file_id: '5235'
file_name: IST-2012-85-v1+1_A_theory_of_synchronous_relational_interfaces.pdf
file_size: 775662
relation: main_file
file_date_updated: 2020-07-14T12:46:09Z
has_accepted_license: '1'
intvolume: ' 33'
isi: 1
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
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
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: ACM Transactions on Programming Languages and Systems (TOPLAS)
publication_status: published
publisher: ACM
publist_id: '3263'
pubrep_id: '85'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A theory of synchronous relational interfaces
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 33
year: '2011'
...
---
_id: '3354'
abstract:
- lang: eng
text: 'We consider two-player games played on a finite state space for an infinite
number of rounds. The games are concurrent: in each round, the two players (player
1 and player 2) choose their moves independently and simultaneously; the current
state and the two moves determine the successor state. We consider ω-regular winning
conditions specified as parity objectives. Both players are allowed to use randomization
when choosing their moves. We study the computation of the limit-winning set of
states, consisting of the states where the sup-inf value of the game for player
1 is 1: in other words, a state is limit-winning if player 1 can ensure a probability
of winning arbitrarily close to 1. We show that the limit-winning set can be computed
in O(n2d+2) time, where n is the size of the game structure and 2d is the number
of priorities (or colors). The membership problem of whether a state belongs to
the limit-winning set can be decided in NP ∩ coNP. While this complexity is the
same as for the simpler class of turn-based parity games, where in each state
only one of the two players has a choice of moves, our algorithms are considerably
more involved than those for turn-based games. This is because concurrent games
do not satisfy two of the most fundamental properties of turn-based parity games.
First, in concurrent games limit-winning strategies require randomization; and
second, they require infinite memory.'
article_number: '28'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- 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, De Alfaro L, Henzinger TA. Qualitative concurrent parity games.
ACM Transactions on Computational Logic (TOCL). 2011;12(4). doi:10.1145/1970398.1970404
apa: Chatterjee, K., De Alfaro, L., & Henzinger, T. A. (2011). Qualitative concurrent
parity games. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/1970398.1970404
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Qualitative
Concurrent Parity Games.” ACM Transactions on Computational Logic (TOCL).
ACM, 2011. https://doi.org/10.1145/1970398.1970404.
ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Qualitative concurrent
parity games,” ACM Transactions on Computational Logic (TOCL), vol. 12,
no. 4. ACM, 2011.
ista: Chatterjee K, De Alfaro L, Henzinger TA. 2011. Qualitative concurrent parity
games. ACM Transactions on Computational Logic (TOCL). 12(4), 28.
mla: Chatterjee, Krishnendu, et al. “Qualitative Concurrent Parity Games.” ACM
Transactions on Computational Logic (TOCL), vol. 12, no. 4, 28, ACM, 2011,
doi:10.1145/1970398.1970404.
short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, ACM Transactions on Computational
Logic (TOCL) 12 (2011).
corr_author: '1'
date_created: 2018-12-11T12:02:51Z
date_published: 2011-07-04T00:00:00Z
date_updated: 2025-09-30T09:05:13Z
day: '04'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1145/1970398.1970404
external_id:
isi:
- '000296202300006'
intvolume: ' 12'
isi: 1
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: ACM Transactions on Computational Logic (TOCL)
publication_status: published
publisher: ACM
publist_id: '3262'
quality_controlled: '1'
related_material:
record:
- id: '2054'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Qualitative concurrent parity games
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12
year: '2011'
...
---
_id: '3355'
abstract:
- lang: eng
text: Byzantine Fault Tolerant (BFT) protocols aim to improve the reliability of
distributed systems. They enable systems to tolerate arbitrary failures in a bounded
number of nodes. BFT protocols are usually proven correct for certain safety and
liveness properties. However, recent studies have shown that the performance of
state-of-the-art BFT protocols decreases drastically in the presence of even a
single malicious node. This motivates a formal quantitative analysis of BFT protocols
to investigate their performance characteristics under different scenarios. We
present HyPerf, a new hybrid methodology based on model checking and simulation
techniques for evaluating the performance of BFT protocols. We build a transition
system corresponding to a BFT protocol and systematically explore the set of behaviors
allowed by the protocol. We associate certain timing information with different
operations in the protocol, like cryptographic operations and message transmission.
After an elaborate state exploration, we use the time information to evaluate
the performance characteristics of the protocol using simulation techniques. We
integrate our framework in Mace, a tool for building and verifying distributed
systems. We evaluate the performance of PBFT using our framework. We describe
two different use-cases of our methodology. For the benign operation of the protocol,
we use the time information as random variables to compute the probability distribution
of the execution times. In the presence of faults, we estimate the worst-case
performance of the protocol for various attacks that can be employed by malicious
nodes. Our results show the importance of hybrid techniques in systematically
analyzing the performance of large-scale systems.
author:
- first_name: Raluca
full_name: Halalai, Raluca
id: 584C6850-E996-11E9-805B-F01764644770
last_name: Halalai
- 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: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
citation:
ama: 'Halalai R, Henzinger TA, Singh V. Quantitative evaluation of BFT protocols.
In: IEEE; 2011:255-264. doi:10.1109/QEST.2011.40'
apa: 'Halalai, R., Henzinger, T. A., & Singh, V. (2011). Quantitative evaluation
of BFT protocols (pp. 255–264). Presented at the QEST: Quantitative Evaluation
of Systems, Aachen, Germany: IEEE. https://doi.org/10.1109/QEST.2011.40'
chicago: Halalai, Raluca, Thomas A Henzinger, and Vasu Singh. “Quantitative Evaluation
of BFT Protocols,” 255–64. IEEE, 2011. https://doi.org/10.1109/QEST.2011.40.
ieee: 'R. Halalai, T. A. Henzinger, and V. Singh, “Quantitative evaluation of BFT
protocols,” presented at the QEST: Quantitative Evaluation of Systems, Aachen,
Germany, 2011, pp. 255–264.'
ista: 'Halalai R, Henzinger TA, Singh V. 2011. Quantitative evaluation of BFT protocols.
QEST: Quantitative Evaluation of Systems, 255–264.'
mla: Halalai, Raluca, et al. Quantitative Evaluation of BFT Protocols. IEEE,
2011, pp. 255–64, doi:10.1109/QEST.2011.40.
short: R. Halalai, T.A. Henzinger, V. Singh, in:, IEEE, 2011, pp. 255–264.
conference:
end_date: 2011-09-08
location: Aachen, Germany
name: 'QEST: Quantitative Evaluation of Systems'
start_date: 2011-09-05
corr_author: '1'
date_created: 2018-12-11T12:02:51Z
date_published: 2011-10-13T00:00:00Z
date_updated: 2024-10-09T20:54:27Z
day: '13'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1109/QEST.2011.40
file:
- access_level: open_access
checksum: 4dc8750ab7921f51de992000b13d1b01
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:49Z
date_updated: 2020-07-14T12:46:09Z
file_id: '4648'
file_name: IST-2012-84-v1+1_Quantitative_evaluation_of_BFT_protocols.pdf
file_size: 272017
relation: main_file
file_date_updated: 2020-07-14T12:46:09Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 255 - 264
publication_status: published
publisher: IEEE
publist_id: '3260'
pubrep_id: '84'
quality_controlled: '1'
scopus_import: 1
status: public
title: Quantitative evaluation of BFT protocols
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3356'
abstract:
- lang: eng
text: There is recently a significant effort to add quantitative objectives to formal
verification and synthesis. We introduce and investigate the extension of temporal
logics with quantitative atomic assertions, aiming for a general and flexible
framework for quantitative-oriented specifications. In the heart of quantitative
objectives lies the accumulation of values along a computation. It is either the
accumulated summation, as with the energy objectives, or the accumulated average,
as with the mean-payoff objectives. We investigate the extension of temporal logics
with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is
a numeric variable of the system, c is a constant rational number, and Sum(v)
and Avg(v) denote the accumulated sum and average of the values of v from the
beginning of the computation up to the current point of time. We also allow the
path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring
to the average value along an entire computation. We study the border of decidability
for extensions of various temporal logics. In particular, we show that extending
the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities by
prefix-accumulation assertions and extending LTL with path-accumulation assertions,
result in temporal logics whose model-checking problem is decidable. The extended
logics allow to significantly extend the currently known energy and mean-payoff
objectives. Moreover, the prefix-accumulation assertions may be refined with "controlled-accumulation",
allowing, for example, to specify constraints on the average waiting time between
a request and a grant. On the negative side, we show that the fragment we point
to is, in a sense, the maximal logic whose extension with prefix-accumulation
assertions permits a decidable model-checking procedure. Extending a temporal
logic that has the EG or EU modalities, and in particular CTL and LTL, makes the
problem undecidable.
article_number: '5970226'
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- 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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: 'Boker U, Chatterjee K, Henzinger TA, Kupferman O. Temporal specifications
with accumulative values. In: IEEE; 2011. doi:10.1109/LICS.2011.33'
apa: 'Boker, U., Chatterjee, K., Henzinger, T. A., & Kupferman, O. (2011). Temporal
specifications with accumulative values. Presented at the LICS: Logic in Computer
Science, Toronto, Canada: IEEE. https://doi.org/10.1109/LICS.2011.33'
chicago: Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman.
“Temporal Specifications with Accumulative Values.” IEEE, 2011. https://doi.org/10.1109/LICS.2011.33.
ieee: 'U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, “Temporal specifications
with accumulative values,” presented at the LICS: Logic in Computer Science, Toronto,
Canada, 2011.'
ista: 'Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2011. Temporal specifications
with accumulative values. LICS: Logic in Computer Science, 5970226.'
mla: Boker, Udi, et al. Temporal Specifications with Accumulative Values.
5970226, IEEE, 2011, doi:10.1109/LICS.2011.33.
short: U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, in:, IEEE, 2011.
conference:
end_date: 2011-06-24
location: Toronto, Canada
name: 'LICS: Logic in Computer Science'
start_date: 2011-06-21
date_created: 2018-12-11T12:02:52Z
date_published: 2011-06-21T00:00:00Z
date_updated: 2025-09-30T09:27:30Z
day: '21'
ddc:
- '000'
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1109/LICS.2011.33
ec_funded: 1
external_id:
isi:
- '000297350400007'
file:
- access_level: open_access
checksum: 792128f5455f0f40f1105f0398e05fa9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:42Z
date_updated: 2020-07-14T12:46:09Z
file_id: '4960'
file_name: IST-2012-83-v1+1_Temporal_specifications_with_accumulative_values.pdf
file_size: 225426
relation: main_file
file_date_updated: 2020-07-14T12:46:09Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: IEEE
publist_id: '3259'
pubrep_id: '83'
related_material:
record:
- id: '5385'
relation: earlier_version
status: public
- id: '2038'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Temporal specifications with accumulative values
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2011'
...
---
_id: '3357'
abstract:
- lang: eng
text: We consider two-player graph games whose objectives are request-response condition,
i.e conjunctions of conditions of the form "if a state with property Rq is visited,
then later a state with property Rp is visited". The winner of such games can
be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we
close this gap by showing that this problem is, in fact, EXPTIME-complete. We
show that the problem becomes PSPACE-complete if we only consider games played
on DAGs, and NP-complete or PTIME-complete if there is only one player (depending
on whether he wants to enforce or spoil the request-response condition). We also
present near-optimal bounds on the memory needed to design winning strategies
for each player, in each case.
alternative_title:
- LNCS
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. The complexity of request-response games.
In: Dediu A-H, Inenaga S, Martín-Vide C, eds. Vol 6638. Springer; 2011:227-237.
doi:10.1007/978-3-642-21254-3_17'
apa: 'Chatterjee, K., Henzinger, T. A., & Horn, F. (2011). The complexity of
request-response games. In A.-H. Dediu, S. Inenaga, & C. Martín-Vide (Eds.)
(Vol. 6638, pp. 227–237). Presented at the LATA: Language and Automata Theory
and Applications, Tarragona, Spain: Springer. https://doi.org/10.1007/978-3-642-21254-3_17'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “The Complexity
of Request-Response Games.” edited by Adrian-Horia Dediu, Shunsuke Inenaga, and
Carlos Martín-Vide, 6638:227–37. Springer, 2011. https://doi.org/10.1007/978-3-642-21254-3_17.
ieee: 'K. Chatterjee, T. A. Henzinger, and F. Horn, “The complexity of request-response
games,” presented at the LATA: Language and Automata Theory and Applications,
Tarragona, Spain, 2011, vol. 6638, pp. 227–237.'
ista: 'Chatterjee K, Henzinger TA, Horn F. 2011. The complexity of request-response
games. LATA: Language and Automata Theory and Applications, LNCS, vol. 6638, 227–237.'
mla: Chatterjee, Krishnendu, et al. The Complexity of Request-Response Games.
Edited by Adrian-Horia Dediu et al., vol. 6638, Springer, 2011, pp. 227–37, doi:10.1007/978-3-642-21254-3_17.
short: K. Chatterjee, T.A. Henzinger, F. Horn, in:, A.-H. Dediu, S. Inenaga, C.
Martín-Vide (Eds.), Springer, 2011, pp. 227–237.
conference:
end_date: 2011-05-31
location: Tarragona, Spain
name: 'LATA: Language and Automata Theory and Applications'
start_date: 2011-05-26
corr_author: '1'
date_created: 2018-12-11T12:02:52Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2024-10-09T20:54:27Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-21254-3_17
editor:
- first_name: Adrian-Horia
full_name: Dediu, Adrian-Horia
last_name: Dediu
- first_name: Shunsuke
full_name: Inenaga, Shunsuke
last_name: Inenaga
- first_name: Carlos
full_name: Martín-Vide, Carlos
last_name: Martín-Vide
intvolume: ' 6638'
language:
- iso: eng
month: '01'
oa_version: None
page: 227 - 237
publication_status: published
publisher: Springer
publist_id: '3258'
quality_controlled: '1'
scopus_import: 1
status: public
title: The complexity of request-response games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6638
year: '2011'
...
---
_id: '3358'
abstract:
- lang: eng
text: The static scheduling problem often arises as a fundamental problem in real-time
systems and grid computing. We consider the problem of statically scheduling a
large job expressed as a task graph on a large number of computing nodes, such
as a data center. This paper solves the large-scale static scheduling problem
using abstraction refinement, a technique commonly used in formal verification
to efficiently solve computationally hard problems. A scheduler based on abstraction
refinement first attempts to solve the scheduling problem with abstract representations
of the job and the computing resources. As abstract representations are generally
small, the scheduling can be done reasonably fast. If the obtained schedule does
not meet specified quality conditions (like data center utilization or schedule
makespan) then the scheduler refines the job and data center abstractions and,
again solves the scheduling problem. We develop different schedulers based on
abstraction refinement. We implemented these schedulers and used them to schedule
task graphs from various computing domains on simulated data centers with realistic
topologies. We compared the speed of scheduling and the quality of the produced
schedules with our abstraction refinement schedulers against a baseline scheduler
that does not use any abstraction. We conclude that abstraction refinement techniques
give a significant speed-up compared to traditional static scheduling heuristics,
at a reasonable cost in the quality of the produced schedules. We further used
our static schedulers in an actual system that we deployed on Amazon EC2 and compared
it against the Hadoop dynamic scheduler for large MapReduce jobs. Our experiments
indicate that there is great potential for static scheduling techniques.
article_processing_charge: No
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: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: 'Henzinger TA, Singh V, Wies T, Zufferey D. Scheduling large jobs by abstraction
refinement. In: ACM; 2011:329-342. doi:10.1145/1966445.1966476'
apa: 'Henzinger, T. A., Singh, V., Wies, T., & Zufferey, D. (2011). Scheduling
large jobs by abstraction refinement (pp. 329–342). Presented at the EuroSys,
Salzburg, Austria: ACM. https://doi.org/10.1145/1966445.1966476'
chicago: Henzinger, Thomas A, Vasu Singh, Thomas Wies, and Damien Zufferey. “Scheduling
Large Jobs by Abstraction Refinement,” 329–42. ACM, 2011. https://doi.org/10.1145/1966445.1966476.
ieee: T. A. Henzinger, V. Singh, T. Wies, and D. Zufferey, “Scheduling large jobs
by abstraction refinement,” presented at the EuroSys, Salzburg, Austria, 2011,
pp. 329–342.
ista: Henzinger TA, Singh V, Wies T, Zufferey D. 2011. Scheduling large jobs by
abstraction refinement. EuroSys, 329–342.
mla: Henzinger, Thomas A., et al. Scheduling Large Jobs by Abstraction Refinement.
ACM, 2011, pp. 329–42, doi:10.1145/1966445.1966476.
short: T.A. Henzinger, V. Singh, T. Wies, D. Zufferey, in:, ACM, 2011, pp. 329–342.
conference:
end_date: 2011-04-13
location: Salzburg, Austria
name: EuroSys
start_date: 2011-04-10
corr_author: '1'
date_created: 2018-12-11T12:02:53Z
date_published: 2011-04-10T00:00:00Z
date_updated: 2024-10-09T20:54:26Z
day: '10'
department:
- _id: ToHe
doi: 10.1145/1966445.1966476
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://cs.nyu.edu/wies/publ/scheduling_large_jobs_by_abstraction_refinement.pdf
month: '04'
oa: 1
oa_version: Published Version
page: 329 - 342
publication_status: published
publisher: ACM
publist_id: '3257'
quality_controlled: '1'
scopus_import: 1
status: public
title: Scheduling large jobs by abstraction refinement
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3359'
abstract:
- lang: eng
text: "Motivated by improvements in constraint-solving technology and by the increase
of routinely available computational power, partial-program synthesis is emerging
as an effective approach for increasing programmer productivity. The goal of the
approach is to allow the programmer to specify a part of her intent imperatively
(that is, give a partial program) and a part of her intent declaratively, by specifying
which conditions need to be achieved or maintained. The task of the synthesizer
is to construct a program that satisfies the specification. As an example, consider
a partial program where threads access shared data without using any synchronization
mechanism, and a declarative specification that excludes data races and deadlocks.
The task of the synthesizer is then to place locks into the program code in order
for the program to meet the specification.\r\n\r\nIn this paper, we argue that
quantitative objectives are needed in partial-program synthesis in order to produce
higher-quality programs, while enabling simpler specifications. Returning to the
example, the synthesizer could construct a naive solution that uses one global
lock for shared data. This can be prevented either by constraining the solution
space further (which is error-prone and partly defeats the point of synthesis),
or by optimizing a quantitative objective that models performance. Other quantitative
notions useful in synthesis include fault tolerance, robustness, resource (memory,
power) consumption, and information flow."
acknowledgement: This work was partially supported by the ERC Advanced Grant QUAREM,
the FWF NFN Grant S11402-N23 (RiSE), and the EU NOE Grant ArtistDesign.
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- 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: 'Cerny P, Henzinger TA. From boolean to quantitative synthesis. In: ACM; 2011:149-154.
doi:10.1145/2038642.2038666'
apa: 'Cerny, P., & Henzinger, T. A. (2011). From boolean to quantitative synthesis
(pp. 149–154). Presented at the EMSOFT: Embedded Software , Taipei; Taiwan: ACM.
https://doi.org/10.1145/2038642.2038666'
chicago: Cerny, Pavol, and Thomas A Henzinger. “From Boolean to Quantitative Synthesis,”
149–54. ACM, 2011. https://doi.org/10.1145/2038642.2038666.
ieee: 'P. Cerny and T. A. Henzinger, “From boolean to quantitative synthesis,” presented
at the EMSOFT: Embedded Software , Taipei; Taiwan, 2011, pp. 149–154.'
ista: 'Cerny P, Henzinger TA. 2011. From boolean to quantitative synthesis. EMSOFT:
Embedded Software , 149–154.'
mla: Cerny, Pavol, and Thomas A. Henzinger. From Boolean to Quantitative Synthesis.
ACM, 2011, pp. 149–54, doi:10.1145/2038642.2038666.
short: P. Cerny, T.A. Henzinger, in:, ACM, 2011, pp. 149–154.
conference:
end_date: 2011-10-14
location: Taipei; Taiwan
name: 'EMSOFT: Embedded Software '
start_date: 2011-10-09
corr_author: '1'
date_created: 2018-12-11T12:02:53Z
date_published: 2011-10-09T00:00:00Z
date_updated: 2024-10-21T06:03:04Z
day: '09'
department:
- _id: ToHe
doi: 10.1145/2038642.2038666
ec_funded: 1
language:
- iso: eng
month: '10'
oa_version: None
page: 149 - 154
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: ACM
publist_id: '3256'
quality_controlled: '1'
scopus_import: '1'
status: public
title: From boolean to quantitative synthesis
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3360'
abstract:
- lang: eng
text: 'A discounted-sum automaton (NDA) is a nondeterministic finite automaton with
edge weights, which values a run by the discounted sum of visited edge weights.
More precisely, the weight in the i-th position of the run is divided by lambda^i,
where the discount factor lambda is a fixed rational number greater than 1. Discounted
summation is a common and useful measuring scheme, especially for infinite sequences,
which reflects the assumption that earlier weights are more important than later
weights. Determinizing automata is often essential, for example, in formal verification,
where there are polynomial algorithms for comparing two deterministic NDAs, while
the equivalence problem for NDAs is not known to be decidable. Unfortunately,
however, discounted-sum automata are, in general, not determinizable: it is currently
known that for every rational discount factor 1 < lambda < 2, there is an
NDA with lambda (denoted lambda-NDA) that cannot be determinized. We provide positive
news, showing that every NDA with an integral factor is determinizable. We also
complete the picture by proving that the integers characterize exactly the discount
factors that guarantee determinizability: we show that for every non-integral
rational factor lambda, there is a nondeterminizable lambda-NDA. Finally, we prove
that the class of NDAs with integral discount factors enjoys closure under the
algebraic operations min, max, addition, and subtraction, which is not the case
for general NDAs nor for deterministic NDAs. This shows that for integral discount
factors, the class of NDAs forms an attractive specification formalism in quantitative
formal verification. All our results hold equally for automata over finite words
and for automata over infinite words. '
alternative_title:
- LIPIcs
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- 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: 'Boker U, Henzinger TA. Determinizing discounted-sum automata. In: Vol 12.
Springer; 2011:82-96. doi:10.4230/LIPIcs.CSL.2011.82'
apa: 'Boker, U., & Henzinger, T. A. (2011). Determinizing discounted-sum automata
(Vol. 12, pp. 82–96). Presented at the CSL: Computer Science Logic, Bergen, Norway:
Springer. https://doi.org/10.4230/LIPIcs.CSL.2011.82'
chicago: Boker, Udi, and Thomas A Henzinger. “Determinizing Discounted-Sum Automata,”
12:82–96. Springer, 2011. https://doi.org/10.4230/LIPIcs.CSL.2011.82.
ieee: 'U. Boker and T. A. Henzinger, “Determinizing discounted-sum automata,” presented
at the CSL: Computer Science Logic, Bergen, Norway, 2011, vol. 12, pp. 82–96.'
ista: 'Boker U, Henzinger TA. 2011. Determinizing discounted-sum automata. CSL:
Computer Science Logic, LIPIcs, vol. 12, 82–96.'
mla: Boker, Udi, and Thomas A. Henzinger. Determinizing Discounted-Sum Automata.
Vol. 12, Springer, 2011, pp. 82–96, doi:10.4230/LIPIcs.CSL.2011.82.
short: U. Boker, T.A. Henzinger, in:, Springer, 2011, pp. 82–96.
conference:
end_date: 2011-09-15
location: Bergen, Norway
name: 'CSL: Computer Science Logic'
start_date: 2011-09-12
date_created: 2018-12-11T12:02:53Z
date_published: 2011-08-31T00:00:00Z
date_updated: 2021-01-12T07:42:56Z
day: '31'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CSL.2011.82
ec_funded: 1
file:
- access_level: open_access
checksum: 250603c6be8ccad4fbd4d7b24221f0ee
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:17Z
date_updated: 2020-07-14T12:46:10Z
file_id: '4803'
file_name: IST-2012-82-v1+1_Determinizing_discounted-sum_automata.pdf
file_size: 504270
relation: main_file
file_date_updated: 2020-07-14T12:46:10Z
has_accepted_license: '1'
intvolume: ' 12'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '08'
oa: 1
oa_version: Published Version
page: 82 - 96
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '3255'
pubrep_id: '82'
quality_controlled: '1'
scopus_import: 1
status: public
title: Determinizing discounted-sum automata
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2011'
...
---
_id: '3361'
abstract:
- lang: eng
text: In this paper, we investigate the computational complexity of quantitative
information flow (QIF) problems. Information-theoretic quantitative relaxations
of noninterference (based on Shannon entropy)have been introduced to enable more
fine-grained reasoning about programs in situations where limited information
flow is acceptable. The QIF bounding problem asks whether the information flow
in a given program is bounded by a constant $d$. Our first result is that the
QIF bounding problem is PSPACE-complete. The QIF memoryless synthesis problem
asks whether it is possible to resolve nondeterministic choices in a given partial
program in such a way that in the resulting deterministic program, the quantitative
information flow is bounded by a given constant $d$. Our second result is that
the QIF memoryless synthesis problem is also EXPTIME-complete. The QIF memoryless
synthesis problem generalizes to QIF general synthesis problem which does not
impose the memoryless requirement (that is, by allowing the synthesized program
to have more variables then the original partial program). Our third result is
that the QIF general synthesis problem is EXPTIME-hard.
article_processing_charge: No
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- 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
citation:
ama: 'Cerny P, Chatterjee K, Henzinger TA. The complexity of quantitative information
flow problems. In: IEEE; 2011:205-217. doi:10.1109/CSF.2011.21'
apa: 'Cerny, P., Chatterjee, K., & Henzinger, T. A. (2011). The complexity of
quantitative information flow problems (pp. 205–217). Presented at the CSF: Computer
Security Foundations, Cernay-la-Ville, France: IEEE. https://doi.org/10.1109/CSF.2011.21'
chicago: Cerny, Pavol, Krishnendu Chatterjee, and Thomas A Henzinger. “The Complexity
of Quantitative Information Flow Problems,” 205–17. IEEE, 2011. https://doi.org/10.1109/CSF.2011.21.
ieee: 'P. Cerny, K. Chatterjee, and T. A. Henzinger, “The complexity of quantitative
information flow problems,” presented at the CSF: Computer Security Foundations,
Cernay-la-Ville, France, 2011, pp. 205–217.'
ista: 'Cerny P, Chatterjee K, Henzinger TA. 2011. The complexity of quantitative
information flow problems. CSF: Computer Security Foundations, 205–217.'
mla: Cerny, Pavol, et al. The Complexity of Quantitative Information Flow Problems.
IEEE, 2011, pp. 205–17, doi:10.1109/CSF.2011.21.
short: P. Cerny, K. Chatterjee, T.A. Henzinger, in:, IEEE, 2011, pp. 205–217.
conference:
end_date: 2011-06-29
location: Cernay-la-Ville, France
name: 'CSF: Computer Security Foundations'
start_date: 2011-06-27
corr_author: '1'
date_created: 2018-12-11T12:02:54Z
date_published: 2011-06-27T00:00:00Z
date_updated: 2025-09-30T09:04:15Z
day: '27'
ddc:
- '000'
- '005'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1109/CSF.2011.21
ec_funded: 1
external_id:
isi:
- '000300766400014'
file:
- access_level: open_access
checksum: 1a25be0c62459fc7640db88af08ff63a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:07Z
date_updated: 2020-07-14T12:46:10Z
file_id: '4792'
file_name: IST-2012-81-v1+1_The_complexity_of_quantitative_information_flow_problems.pdf
file_size: 299069
relation: main_file
file_date_updated: 2020-07-14T12:46:10Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 205 - 217
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: IEEE
publist_id: '3254'
pubrep_id: '81'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of quantitative information flow problems
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2011'
...
---
_id: '3362'
abstract:
- lang: eng
text: State-transition systems communicating by shared variables have been the underlying
model of choice for applications of model checking. Such formalisms, however,
have difficulty with modeling process creation or death and communication reconfigurability.
Here, we introduce “dynamic reactive modules” (DRM), a state-transition modeling
formalism that supports dynamic reconfiguration and creation/death of processes.
The resulting formalism supports two types of variables, data variables and reference
variables. Reference variables enable changing the connectivity between processes
and referring to instances of processes. We show how this new formalism supports
parallel composition and refinement through trace containment. DRM provide a natural
language for modeling (and ultimately reasoning about) biological systems and
multiple threads communicating through shared variables.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jasmin
full_name: Fisher, Jasmin
last_name: Fisher
- 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: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
- first_name: Nir
full_name: Piterman, Nir
last_name: Piterman
- first_name: Anmol
full_name: Singh, Anmol
last_name: Singh
- first_name: Moshe
full_name: Vardi, Moshe
last_name: Vardi
citation:
ama: 'Fisher J, Henzinger TA, Nickovic D, Piterman N, Singh A, Vardi M. Dynamic
reactive modules. In: Vol 6901. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2011:404-418. doi:10.1007/978-3-642-23217-6_27'
apa: 'Fisher, J., Henzinger, T. A., Nickovic, D., Piterman, N., Singh, A., &
Vardi, M. (2011). Dynamic reactive modules (Vol. 6901, pp. 404–418). Presented
at the CONCUR: Concurrency Theory, Aachen, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.1007/978-3-642-23217-6_27'
chicago: Fisher, Jasmin, Thomas A Henzinger, Dejan Nickovic, Nir Piterman, Anmol
Singh, and Moshe Vardi. “Dynamic Reactive Modules,” 6901:404–18. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2011. https://doi.org/10.1007/978-3-642-23217-6_27.
ieee: 'J. Fisher, T. A. Henzinger, D. Nickovic, N. Piterman, A. Singh, and M. Vardi,
“Dynamic reactive modules,” presented at the CONCUR: Concurrency Theory, Aachen,
Germany, 2011, vol. 6901, pp. 404–418.'
ista: 'Fisher J, Henzinger TA, Nickovic D, Piterman N, Singh A, Vardi M. 2011. Dynamic
reactive modules. CONCUR: Concurrency Theory, LNCS, vol. 6901, 404–418.'
mla: Fisher, Jasmin, et al. Dynamic Reactive Modules. Vol. 6901, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2011, pp. 404–18, doi:10.1007/978-3-642-23217-6_27.
short: J. Fisher, T.A. Henzinger, D. Nickovic, N. Piterman, A. Singh, M. Vardi,
in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011, pp. 404–418.
conference:
end_date: 2011-09-09
location: Aachen, Germany
name: 'CONCUR: Concurrency Theory'
start_date: 2011-09-06
date_created: 2018-12-11T12:02:54Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:57Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-23217-6_27
ec_funded: 1
file:
- access_level: open_access
checksum: 6bf2453d8e52e979ddb58d17325bad26
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:17:48Z
date_updated: 2020-07-14T12:46:10Z
file_id: '7870'
file_name: 2011_CONCUR_Fisher.pdf
file_size: 337125
relation: main_file
file_date_updated: 2020-07-14T12:46:10Z
has_accepted_license: '1'
intvolume: ' 6901'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 404 - 418
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '3253'
quality_controlled: '1'
scopus_import: 1
status: public
title: Dynamic reactive modules
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6901
year: '2011'
...
---
_id: '3363'
abstract:
- lang: eng
text: We consider probabilistic automata on infinite words with acceptance defined
by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider
quantitative and qualitative decision problems. We present extensions and adaptations
of proofs for probabilistic finite automata and present a complete characterization
of the decidability and undecidability frontier of the quantitative and qualitative
decision problems for probabilistic automata on infinite words.
article_number: '1104.0127'
article_processing_charge: No
arxiv: 1
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: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: Chatterjee K, Henzinger TA, Tracol M. The decidability frontier for probabilistic
automata on infinite words. doi:10.48550/arXiv.1104.0127
apa: Chatterjee, K., Henzinger, T. A., & Tracol, M. (n.d.). The decidability
frontier for probabilistic automata on infinite words. ArXiv. https://doi.org/10.48550/arXiv.1104.0127
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Mathieu Tracol. “The Decidability
Frontier for Probabilistic Automata on Infinite Words.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1104.0127.
ieee: K. Chatterjee, T. A. Henzinger, and M. Tracol, “The decidability frontier
for probabilistic automata on infinite words.” ArXiv.
ista: Chatterjee K, Henzinger TA, Tracol M. The decidability frontier for probabilistic
automata on infinite words. 1104.0127.
mla: Chatterjee, Krishnendu, et al. The Decidability Frontier for Probabilistic
Automata on Infinite Words. 1104.0127, ArXiv, doi:10.48550/arXiv.1104.0127.
short: K. Chatterjee, T.A. Henzinger, M. Tracol, (n.d.).
corr_author: '1'
date_created: 2018-12-11T12:02:54Z
date_published: 2011-04-01T00:00:00Z
date_updated: 2025-06-26T09:19:59Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.48550/arXiv.1104.0127
ec_funded: 1
external_id:
arxiv:
- '1104.0127'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1104.0127
month: '04'
oa: 1
oa_version: Preprint
page: '19'
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: submitted
publisher: ArXiv
publist_id: '3251'
status: public
title: The decidability frontier for probabilistic automata on infinite words
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3364'
abstract:
- lang: eng
text: Molecular noise, which arises from the randomness of the discrete events in
the cell, significantly influences fundamental biological processes. Discrete-state
continuous-time stochastic models (CTMC) can be used to describe such effects,
but the calculation of the probabilities of certain events is computationally
expensive. We present a comparison of two analysis approaches for CTMC. On one
hand, we estimate the probabilities of interest using repeated Gillespie simulation
and determine the statistical accuracy that we obtain. On the other hand, we apply
a numerical reachability analysis that approximates the probability distributions
of the system at several time instances. We use examples of cellular processes
to demonstrate the superiority of the reachability analysis if accurate results
are required.
article_processing_charge: No
author:
- first_name: Frédéric
full_name: Didier, Frédéric
last_name: Didier
- 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: Maria
full_name: Mateescu, Maria
last_name: Mateescu
- first_name: Verena
full_name: Wolf, Verena
last_name: Wolf
citation:
ama: Didier F, Henzinger TA, Mateescu M, Wolf V. Approximation of event probabilities
in noisy cellular processes. Theoretical Computer Science. 2011;412(21):2128-2141.
doi:10.1016/j.tcs.2010.10.022
apa: Didier, F., Henzinger, T. A., Mateescu, M., & Wolf, V. (2011). Approximation
of event probabilities in noisy cellular processes. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2010.10.022
chicago: Didier, Frédéric, Thomas A Henzinger, Maria Mateescu, and Verena Wolf.
“Approximation of Event Probabilities in Noisy Cellular Processes.” Theoretical
Computer Science. Elsevier, 2011. https://doi.org/10.1016/j.tcs.2010.10.022.
ieee: F. Didier, T. A. Henzinger, M. Mateescu, and V. Wolf, “Approximation of event
probabilities in noisy cellular processes,” Theoretical Computer Science,
vol. 412, no. 21. Elsevier, pp. 2128–2141, 2011.
ista: Didier F, Henzinger TA, Mateescu M, Wolf V. 2011. Approximation of event probabilities
in noisy cellular processes. Theoretical Computer Science. 412(21), 2128–2141.
mla: Didier, Frédéric, et al. “Approximation of Event Probabilities in Noisy Cellular
Processes.” Theoretical Computer Science, vol. 412, no. 21, Elsevier, 2011,
pp. 2128–41, doi:10.1016/j.tcs.2010.10.022.
short: F. Didier, T.A. Henzinger, M. Mateescu, V. Wolf, Theoretical Computer Science
412 (2011) 2128–2141.
date_created: 2018-12-11T12:02:55Z
date_published: 2011-05-06T00:00:00Z
date_updated: 2025-09-30T09:03:30Z
day: '06'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1016/j.tcs.2010.10.022
external_id:
isi:
- '000290078000005'
file:
- access_level: open_access
checksum: e5503e25ce020d753e06b3431e16841e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:09Z
date_updated: 2020-07-14T12:46:10Z
file_id: '4862'
file_name: IST-2012-79-v1+1_Approximation_of_event_probabilities_in_noisy_cellular_processes.pdf
file_size: 230503
relation: main_file
file_date_updated: 2020-07-14T12:46:10Z
has_accepted_license: '1'
intvolume: ' 412'
isi: 1
issue: '21'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 2128 - 2141
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '3249'
pubrep_id: '79'
quality_controlled: '1'
related_material:
record:
- id: '4535'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Approximation of event probabilities in noisy cellular processes
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 412
year: '2011'
...