---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '21413'
abstract:
- lang: eng
text: "We present a general framework for applying learning algorithms and heuristical
guidance to the verification of Markov decision processes (MDPs).\r\nThe primary
goal of our techniques is to improve performance by avoiding an exhaustive exploration
of the state space, instead focussing on particularly relevant areas of the system,
guided by heuristics. Our work builds on the previous results of Br{á}zdil et
al., significantly extending it as well as refining several details and fixing
errors.\r\nThe presented framework focuses on probabilistic reachability, which
is a core problem in verification, and is instantiated in two distinct scenarios.\r\nThe
first assumes that full knowledge of the MDP is available, in particular precise
transition probabilities. It performs a heuristic-driven partial exploration of
the model, yielding precise lower and upper bounds on the required probability.
The second tackles the case where we may only sample the MDP without knowing the
exact transition dynamics. Here, we obtain probabilistic guarantees, again in
terms of both the lower and upper bounds, which provides efficient stopping criteria
for the approximation. In particular, the latter is an extension of statistical
model-checking (SMC) for unbounded properties in MDPs. In contrast to other related
approaches, we do not restrict our attention to time-bounded (finite-horizon)
or discounted properties, nor assume any particular structural properties of the
MDP."
acknowledgement: "This research was funded in part by the European Research Council
(ERC) under grant agreement AdG-267989 (QUAREM)*, AdG-246967 (VERIWARE)*, StG-279307
(Graph Games)*\r\n, CoG-863818 (ForM-SMArt), and AdG-834115 (FUN2MODEL), by the
EU FP7 project HIERATIC*, by the German Research Foundation (DFG) project 427755713
(GOPro), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE)* , S11407-N23
(RiSE)*\r\n, and P23499-N23* , by the Czech Science Foundation grant No P202/12/P612*
and GA23-06963S, by the MUNI Award in Science and Humanities (MUNI/I/1757/2021)
of the Grant\r\nAgency of Masaryk University, by EPSRC project EP/K038575/1*, and
by the Microsoft faculty fellows award*. A preliminary version of this article appeared
at ATVA 2014 [33]. The * indicates funding that supported that version."
article_number: '10'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Vojtěch
full_name: Forejt, Vojtěch
last_name: Forejt
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Marta
full_name: Kwiatkowska, Marta
last_name: Kwiatkowska
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: David
full_name: Parker, David
last_name: Parker
- first_name: Mateusz
full_name: Ujma, Mateusz
last_name: Ujma
citation:
ama: Brázdil T, Chatterjee K, Chmelik M, et al. Learning algorithms for verification
of Markov decision processes. TheoretiCS. 2025;4. doi:10.46298/theoretics.25.10
apa: Brázdil, T., Chatterjee, K., Chmelik, M., Forejt, V., Kretinsky, J., Kwiatkowska,
M., … Ujma, M. (2025). Learning algorithms for verification of Markov decision
processes. TheoretiCS. TheoretiCS Foundation. https://doi.org/10.46298/theoretics.25.10
chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Vojtěch Forejt,
Jan Kretinsky, Marta Kwiatkowska, Tobias Meggendorfer, David Parker, and Mateusz
Ujma. “Learning Algorithms for Verification of Markov Decision Processes.” TheoretiCS.
TheoretiCS Foundation, 2025. https://doi.org/10.46298/theoretics.25.10.
ieee: T. Brázdil et al., “Learning algorithms for verification of Markov
decision processes,” TheoretiCS, vol. 4. TheoretiCS Foundation, 2025.
ista: Brázdil T, Chatterjee K, Chmelik M, Forejt V, Kretinsky J, Kwiatkowska M,
Meggendorfer T, Parker D, Ujma M. 2025. Learning algorithms for verification of
Markov decision processes. TheoretiCS. 4, 10.
mla: Brázdil, Tomáš, et al. “Learning Algorithms for Verification of Markov Decision
Processes.” TheoretiCS, vol. 4, 10, TheoretiCS Foundation, 2025, doi:10.46298/theoretics.25.10.
short: T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska,
T. Meggendorfer, D. Parker, M. Ujma, TheoretiCS 4 (2025).
date_created: 2026-03-08T23:01:46Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2026-03-09T11:43:38Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.46298/theoretics.25.10
ec_funded: 1
external_id:
arxiv:
- '2403.09184'
file:
- access_level: open_access
checksum: 2ccf563ae577ee08d82baf752292ca7b
content_type: application/pdf
creator: dernst
date_created: 2026-03-09T11:39:59Z
date_updated: 2026-03-09T11:39:59Z
file_id: '21417'
file_name: 2026_TheoretiCS_Brazdil.pdf
file_size: 861607
relation: main_file
success: 1
file_date_updated: 2026-03-09T11:39:59Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
publication: TheoretiCS
publication_identifier:
eissn:
- 2751-4838
publication_status: published
publisher: TheoretiCS Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Learning algorithms for verification of Markov decision processes
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2025'
...
---
_id: '608'
abstract:
- lang: eng
text: Synthesis is the automated construction of a system from its specification.
In real life, hardware and software systems are rarely constructed from scratch.
Rather, a system is typically constructed from a library of components. Lustig
and Vardi formalized this intuition and studied LTL synthesis from component libraries.
In real life, designers seek optimal systems. In this paper we add optimality
considerations to the setting. We distinguish between quality considerations (for
example, size - the smaller a system is, the better it is), and pricing (for example,
the payment to the company who manufactured the component). We study the problem
of designing systems with minimal quality-cost and price. A key point is that
while the quality cost is individual - the choices of a designer are independent
of choices made by other designers that use the same library, pricing gives rise
to a resource-allocation game - designers that use the same component share its
price, with the share being proportional to the number of uses (a component can
be used several times in a design). We study both closed and open settings, and
in both we solve the problem of finding an optimal design. In a setting with multiple
designers, we also study the game-theoretic problems of the induced resource-allocation
game.
article_processing_charge: No
article_type: original
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Avni G, Kupferman O. Synthesis from component libraries with costs. Theoretical
Computer Science. 2018;712:50-72. doi:10.1016/j.tcs.2017.11.001
apa: Avni, G., & Kupferman, O. (2018). Synthesis from component libraries with
costs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2017.11.001
chicago: Avni, Guy, and Orna Kupferman. “Synthesis from Component Libraries with
Costs.” Theoretical Computer Science. Elsevier, 2018. https://doi.org/10.1016/j.tcs.2017.11.001.
ieee: G. Avni and O. Kupferman, “Synthesis from component libraries with costs,”
Theoretical Computer Science, vol. 712. Elsevier, pp. 50–72, 2018.
ista: Avni G, Kupferman O. 2018. Synthesis from component libraries with costs.
Theoretical Computer Science. 712, 50–72.
mla: Avni, Guy, and Orna Kupferman. “Synthesis from Component Libraries with Costs.”
Theoretical Computer Science, vol. 712, Elsevier, 2018, pp. 50–72, doi:10.1016/j.tcs.2017.11.001.
short: G. Avni, O. Kupferman, Theoretical Computer Science 712 (2018) 50–72.
corr_author: '1'
date_created: 2018-12-11T11:47:28Z
date_published: 2018-02-15T00:00:00Z
date_updated: 2026-06-18T18:58:53Z
day: '15'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1016/j.tcs.2017.11.001
ec_funded: 1
external_id:
isi:
- '000424959200003'
intvolume: ' 712'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.636.4529
month: '02'
oa: 1
oa_version: Published Version
page: 50 - 72
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '7197'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Synthesis from component libraries with costs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 712
year: '2018'
...
---
OA_place: publisher
_id: '1155'
abstract:
- lang: eng
text: This dissertation concerns the automatic verification of probabilistic systems
and programs with arrays by statistical and logical methods. Although statistical
and logical methods are different in nature, we show that they can be successfully
combined for system analysis. In the first part of the dissertation we present
a new statistical algorithm for the verification of probabilistic systems with
respect to unbounded properties, including linear temporal logic. Our algorithm
often performs faster than the previous approaches, and at the same time requires
less information about the system. In addition, our method can be generalized
to unbounded quantitative properties such as mean-payoff bounds. In the second
part, we introduce two techniques for comparing probabilistic systems. Probabilistic
systems are typically compared using the notion of equivalence, which requires
the systems to have the equal probability of all behaviors. However, this notion
is often too strict, since probabilities are typically only empirically estimated,
and any imprecision may break the relation between processes. On the one hand,
we propose to replace the Boolean notion of equivalence by a quantitative distance
of similarity. For this purpose, we introduce a statistical framework for estimating
distances between Markov chains based on their simulation runs, and we investigate
which distances can be approximated in our framework. On the other hand, we propose
to compare systems with respect to a new qualitative logic, which expresses that
behaviors occur with probability one or a positive probability. This qualitative
analysis is robust with respect to modeling errors and applicable to many domains.
In the last part, we present a new quantifier-free logic for integer arrays, which
allows us to express counting. Counting properties are prevalent in array-manipulating
programs, however they cannot be expressed in the quantified fragments of the
theory of arrays. We present a decision procedure for our logic, and provide several
complexity results.
acknowledgement: ' First of all, I want to thank my advisor, prof. Thomas A. Henzinger,
for his guidance during my PhD program. I am grateful for the freedom I was given
to pursue my research interests, and his continuous support. Working with prof.
Henzinger was a truly inspiring experience and taught me what it means to be a scientist.
I want to express my gratitude to my collaborators: Nikola Beneš, Krishnendu Chatterjee,
Martin Chmelík, Ashutosh Gupta, Willibald Krenn, Jan Kˇretínský, Dejan Nickovic,
Andrey Kupriyanov, and Tatjana Petrov. I have learned a great deal from my collaborators,
and without their help this thesis would not be possible. In addition, I want to
thank the members of my thesis committee: Dirk Beyer, Dejan Nickovic, and Georg
Weissenbacher for their advice and reviewing this dissertation. I would especially
like to acknowledge the late Helmut Veith, who was a member of my committee. I will
remember Helmut for his kindness, enthusiasm, and wit, as well as for being an inspiring
scientist. Finally, I would like to thank my colleagues for making my stay at IST
such a pleasant experience: Guy Avni, Sergiy Bogomolov, Ventsislav Chonev, Rasmus
Ibsen-Jensen, Mirco Giacobbe, Bernhard Kragl, Hui Kong, Petr Novotný, Jan Otop,
Andreas Pavlogiannis, Tantjana Petrov, Arjun Radhakrishna, Jakob Ruess, Thorsten
Tarrach, as well as other members of groups Henzinger and Chatterjee. '
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
citation:
ama: Daca P. Statistical and logical methods for property checking. 2017. doi:10.15479/AT:ISTA:TH_730
apa: Daca, P. (2017). Statistical and logical methods for property checking.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:TH_730
chicago: Daca, Przemyslaw. “Statistical and Logical Methods for Property Checking.”
Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:TH_730.
ieee: P. Daca, “Statistical and logical methods for property checking,” Institute
of Science and Technology Austria, 2017.
ista: Daca P. 2017. Statistical and logical methods for property checking. Institute
of Science and Technology Austria.
mla: Daca, Przemyslaw. Statistical and Logical Methods for Property Checking.
Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:TH_730.
short: P. Daca, Statistical and Logical Methods for Property Checking, Institute
of Science and Technology Austria, 2017.
corr_author: '1'
date_created: 2018-12-11T11:50:27Z
date_published: 2017-01-02T00:00:00Z
date_updated: 2026-04-15T10:02:13Z
day: '02'
ddc:
- '004'
- '005'
degree_awarded: PhD
department:
- _id: ToHe
doi: 10.15479/AT:ISTA:TH_730
ec_funded: 1
file:
- access_level: open_access
checksum: 1406a681cb737508234fde34766be2c2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:26Z
date_updated: 2020-07-14T12:44:34Z
file_id: '4880'
file_name: IST-2017-730-v1+1_Statistical_and_Logical_Methods_for_Property_Checking.pdf
file_size: 1028586
relation: main_file
file_date_updated: 2020-07-14T12:44:34Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '163'
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6203'
pubrep_id: '730'
related_material:
record:
- id: '2063'
relation: part_of_dissertation
status: public
- id: '1093'
relation: part_of_dissertation
status: public
- id: '1391'
relation: part_of_dissertation
status: public
- id: '1234'
relation: part_of_dissertation
status: public
- id: '1230'
relation: part_of_dissertation
status: public
- id: '1501'
relation: part_of_dissertation
status: public
- id: '1502'
relation: part_of_dissertation
status: public
- id: '2167'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
title: Statistical and logical methods for property checking
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '1196'
abstract:
- lang: eng
text: 'We define the . model-measuring problem: given a model . M and specification
. ϕ, what is the maximal distance . ρ such that all models . M'' within distance
. ρ from . M satisfy (or violate) . ϕ. The model-measuring problem presupposes
a distance function on models. We concentrate on . automatic distance functions,
which are defined by weighted automata. The model-measuring problem subsumes several
generalizations of the classical model-checking problem, in particular, quantitative
model-checking problems that measure the degree of satisfaction of a specification;
robustness problems that measure how much a model can be perturbed without violating
the specification; and parameter synthesis for hybrid systems. We show that for
automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular
branching-time, and (c) hybrid specifications, the model-measuring problem can
be solved.We use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for word, tree, and hybrid automata by the .
optimal-value question for the weighted versions of these automata. For automata
over words and trees, we consider weighted automata that accumulate weights by
maximizing, summing, discounting, and limit averaging. For hybrid automata, we
consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete)
weighted automata.We give several examples of using the model-measuring problem
to compute various notions of robustness and quantitative satisfaction for temporal
specifications. Further, we propose the modeling framework for model measuring
to ease the specification and reduce the likelihood of errors in modeling.Finally,
we present a variant of the model-measuring problem, called the . model-repair
problem. The model-repair problem applies to models that do not satisfy the specification;
it can be used to derive restrictions, under which the model satisfies the specification,
i.e., to repair the model.'
acknowledgement: "This research was supported in part by the European Research Council
(ERC) under grant 267989 (QUAREM), by the Austrian Science Fund1 (FWF) under grants
S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), and by the National Science
Centre (NCN), Poland under grant 2014/15/D/ST6/04543.\r\nA Technical Report of this
article is available via: https://repository.ist.ac.at/171/"
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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: 'Henzinger TA, Otop J. Model measuring for discrete and hybrid systems. Nonlinear
Analysis: Hybrid Systems. 2017;23:166-190. doi:10.1016/j.nahs.2016.09.001'
apa: 'Henzinger, T. A., & Otop, J. (2017). Model measuring for discrete and
hybrid systems. Nonlinear Analysis: Hybrid Systems. Elsevier. https://doi.org/10.1016/j.nahs.2016.09.001'
chicago: 'Henzinger, Thomas A, and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems. Elsevier, 2017. https://doi.org/10.1016/j.nahs.2016.09.001.'
ieee: 'T. A. Henzinger and J. Otop, “Model measuring for discrete and hybrid systems,”
Nonlinear Analysis: Hybrid Systems, vol. 23. Elsevier, pp. 166–190, 2017.'
ista: 'Henzinger TA, Otop J. 2017. Model measuring for discrete and hybrid systems.
Nonlinear Analysis: Hybrid Systems. 23, 166–190.'
mla: 'Henzinger, Thomas A., and Jan Otop. “Model Measuring for Discrete and Hybrid
Systems.” Nonlinear Analysis: Hybrid Systems, vol. 23, Elsevier, 2017,
pp. 166–90, doi:10.1016/j.nahs.2016.09.001.'
short: 'T.A. Henzinger, J. Otop, Nonlinear Analysis: Hybrid Systems 23 (2017) 166–190.'
date_created: 2018-12-11T11:50:39Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2025-04-15T06:25:59Z
day: '01'
department:
- _id: ToHe
doi: 10.1016/j.nahs.2016.09.001
ec_funded: 1
external_id:
isi:
- '000390637000011'
intvolume: ' 23'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 166 - 190
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: 'Nonlinear Analysis: Hybrid Systems'
publication_status: published
publisher: Elsevier
publist_id: '6154'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Model measuring for discrete and hybrid systems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2017'
...
---
_id: '1338'
abstract:
- lang: eng
text: We present a computer-aided programming approach to concurrency. The approach
allows programmers to program assuming a friendly, non-preemptive scheduler, and
our synthesis procedure inserts synchronization to ensure that the final program
works even with a preemptive scheduler. The correctness specification is implicit,
inferred from the non-preemptive behavior. Let us consider sequences of calls
that the program makes to an external interface. The specification requires that
any such sequence produced under a preemptive scheduler should be included in
the set of sequences produced under a non-preemptive scheduler. We guarantee that
our synthesis does not introduce deadlocks and that the synchronization inserted
is optimal w.r.t. a given objective function. The solution is based on a finitary
abstraction, an algorithm for bounded language inclusion modulo an independence
relation, and generation of a set of global constraints over synchronization placements.
Each model of the global constraints set corresponds to a correctness-ensuring
synchronization placement. The placement that is optimal w.r.t. the given objective
function is chosen as the synchronization solution. We apply the approach to device-driver
programming, where the driver threads call the software interface of the device
and the API provided by the operating system. Our experiments demonstrate that
our synthesis method is precise and efficient. The implicit specification helped
us find one concurrency bug previously missed when model-checking using an explicit,
user-provided specification. We implemented objective functions for coarse-grained
and fine-grained locking and observed that different synchronization placements
are produced for our experiments, favoring a minimal number of synchronization
operations or maximum concurrency, respectively.
article_processing_charge: No
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Edmund
full_name: Clarke, Edmund
last_name: Clarke
- 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: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
- first_name: Leonid
full_name: Ryzhyk, Leonid
last_name: Ryzhyk
- first_name: Roopsha
full_name: Samanta, Roopsha
id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87
last_name: Samanta
- first_name: Thorsten
full_name: Tarrach, Thorsten
id: 3D6E8F2C-F248-11E8-B48F-1D18A9856A87
last_name: Tarrach
orcid: 0000-0003-4409-8487
citation:
ama: Cerny P, Clarke E, Henzinger TA, et al. From non-preemptive to preemptive scheduling
using synchronization synthesis. Formal Methods in System Design. 2017;50(2-3):97-139.
doi:10.1007/s10703-016-0256-5
apa: Cerny, P., Clarke, E., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., Samanta,
R., & Tarrach, T. (2017). From non-preemptive to preemptive scheduling using
synchronization synthesis. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-016-0256-5
chicago: Cerny, Pavol, Edmund Clarke, Thomas A Henzinger, Arjun Radhakrishna, Leonid
Ryzhyk, Roopsha Samanta, and Thorsten Tarrach. “From Non-Preemptive to Preemptive
Scheduling Using Synchronization Synthesis.” Formal Methods in System Design.
Springer, 2017. https://doi.org/10.1007/s10703-016-0256-5.
ieee: P. Cerny et al., “From non-preemptive to preemptive scheduling using
synchronization synthesis,” Formal Methods in System Design, vol. 50, no.
2–3. Springer, pp. 97–139, 2017.
ista: Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach
T. 2017. From non-preemptive to preemptive scheduling using synchronization synthesis.
Formal Methods in System Design. 50(2–3), 97–139.
mla: Cerny, Pavol, et al. “From Non-Preemptive to Preemptive Scheduling Using Synchronization
Synthesis.” Formal Methods in System Design, vol. 50, no. 2–3, Springer,
2017, pp. 97–139, doi:10.1007/s10703-016-0256-5.
short: P. Cerny, E. Clarke, T.A. Henzinger, A. Radhakrishna, L. Ryzhyk, R. Samanta,
T. Tarrach, Formal Methods in System Design 50 (2017) 97–139.
corr_author: '1'
date_created: 2018-12-11T11:51:27Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2025-09-23T08:54:01Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s10703-016-0256-5
ec_funded: 1
external_id:
isi:
- '000399888900001'
pmid:
- '28490835'
file:
- access_level: open_access
checksum: 1163dfd997e8212c789525d4178b1653
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:05Z
date_updated: 2020-07-14T12:44:44Z
file_id: '4985'
file_name: IST-2016-656-v1+1_s10703-016-0256-5.pdf
file_size: 1416170
relation: main_file
file_date_updated: 2020-07-14T12:44:44Z
has_accepted_license: '1'
intvolume: ' 50'
isi: 1
issue: 2-3
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 97 - 139
pmid: 1
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '5929'
pubrep_id: '656'
quality_controlled: '1'
related_material:
record:
- id: '1729'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: From non-preemptive to preemptive scheduling using synchronization synthesis
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2017'
...
---
_id: '1351'
abstract:
- lang: eng
text: The behaviour of gene regulatory networks (GRNs) is typically analysed using
simulation-based statistical testing-like methods. In this paper, we demonstrate
that we can replace this approach by a formal verification-like method that gives
higher assurance and scalability. We focus on Wagner’s weighted GRN model with
varying weights, which is used in evolutionary biology. In the model, weight parameters
represent the gene interaction strength that may change due to genetic mutations.
For a property of interest, we synthesise the constraints over the parameter space
that represent the set of GRNs satisfying the property. We experimentally show
that our parameter synthesis procedure computes the mutational robustness of GRNs—an
important problem of interest in evolutionary biology—more efficiently than the
classical simulation method. We specify the property in linear temporal logic.
We employ symbolic bounded model checking and SMT solving to compute the space
of GRNs that satisfy the property, which amounts to synthesizing a set of linear
constraints on the weights.
article_processing_charge: No
author:
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- 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: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking
the evolution of gene regulatory networks. Acta Informatica. 2017;54(8):765-787.
doi:10.1007/s00236-016-0278-x
apa: Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., & Petrov,
T. (2017). Model checking the evolution of gene regulatory networks. Acta Informatica.
Springer. https://doi.org/10.1007/s00236-016-0278-x
chicago: Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago
Paixao, and Tatjana Petrov. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica. Springer, 2017. https://doi.org/10.1007/s00236-016-0278-x.
ieee: M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov,
“Model checking the evolution of gene regulatory networks,” Acta Informatica,
vol. 54, no. 8. Springer, pp. 765–787, 2017.
ista: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2017. Model
checking the evolution of gene regulatory networks. Acta Informatica. 54(8), 765–787.
mla: Giacobbe, Mirco, et al. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica, vol. 54, no. 8, Springer, 2017, pp. 765–87, doi:10.1007/s00236-016-0278-x.
short: M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, Acta
Informatica 54 (2017) 765–787.
corr_author: '1'
date_created: 2018-12-11T11:51:32Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2025-07-10T11:50:42Z
day: '01'
ddc:
- '006'
- '576'
department:
- _id: ToHe
- _id: CaGu
- _id: NiBa
doi: 10.1007/s00236-016-0278-x
ec_funded: 1
external_id:
isi:
- '000414343200003'
file:
- access_level: open_access
checksum: 4e661d9135d7f8c342e8e258dee76f3e
content_type: application/pdf
creator: dernst
date_created: 2019-01-17T15:57:29Z
date_updated: 2020-07-14T12:44:46Z
file_id: '5841'
file_name: 2017_ActaInformatica_Giacobbe.pdf
file_size: 755241
relation: main_file
file_date_updated: 2020-07-14T12:44:46Z
has_accepted_license: '1'
intvolume: ' 54'
isi: 1
issue: '8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 765 - 787
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Acta Informatica
publication_identifier:
issn:
- 0001-5903
publication_status: published
publisher: Springer
publist_id: '5898'
pubrep_id: '649'
quality_controlled: '1'
related_material:
record:
- id: '1835'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Model checking the evolution of gene regulatory networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 54
year: '2017'
...
---
_id: '1407'
abstract:
- lang: eng
text: We consider the problem of computing the set of initial states of a dynamical
system such that there exists a control strategy to ensure that the trajectories
satisfy a temporal logic specification with probability 1 (almost-surely). We
focus on discrete-time, stochastic linear dynamics and specifications given as
formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over
linear predicates in the states of the system. We propose a solution based on
iterative abstraction-refinement, and turn-based 2-player probabilistic games.
While the theoretical guarantee of our algorithm after any finite number of iterations
is only a partial solution, we show that if our algorithm terminates, then the
result is the set of all satisfying initial states. Moreover, for any (partial)
solution our algorithm synthesizes witness control strategies to ensure almost-sure
satisfaction of the temporal logic specification. While the proposed algorithm
guarantees progress and soundness in every iteration, it is computationally demanding.
We offer an alternative, more efficient solution for the reachability properties
that decomposes the problem into a series of smaller problems of the same type.
All algorithms are demonstrated on an illustrative case study.
article_processing_charge: No
arxiv: 1
author:
- first_name: Mária
full_name: Svoreňová, Mária
last_name: Svoreňová
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ivana
full_name: Cěrná, Ivana
last_name: Cěrná
- first_name: Cǎlin
full_name: Belta, Cǎlin
last_name: Belta
citation:
ama: 'Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. Temporal
logic control for stochastic linear systems using abstraction refinement of probabilistic
games. Nonlinear Analysis: Hybrid Systems. 2017;23(2):230-253. doi:10.1016/j.nahs.2016.04.006'
apa: 'Svoreňová, M., Kretinsky, J., Chmelik, M., Chatterjee, K., Cěrná, I., &
Belta, C. (2017). Temporal logic control for stochastic linear systems using abstraction
refinement of probabilistic games. Nonlinear Analysis: Hybrid Systems.
Elsevier. https://doi.org/10.1016/j.nahs.2016.04.006'
chicago: 'Svoreňová, Mária, Jan Kretinsky, Martin Chmelik, Krishnendu Chatterjee,
Ivana Cěrná, and Cǎlin Belta. “Temporal Logic Control for Stochastic Linear Systems
Using Abstraction Refinement of Probabilistic Games.” Nonlinear Analysis: Hybrid
Systems. Elsevier, 2017. https://doi.org/10.1016/j.nahs.2016.04.006.'
ieee: 'M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, and C. Belta,
“Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games,” Nonlinear Analysis: Hybrid Systems, vol. 23, no.
2. Elsevier, pp. 230–253, 2017.'
ista: 'Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. 2017.
Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games. Nonlinear Analysis: Hybrid Systems. 23(2), 230–253.'
mla: 'Svoreňová, Mária, et al. “Temporal Logic Control for Stochastic Linear Systems
Using Abstraction Refinement of Probabilistic Games.” Nonlinear Analysis: Hybrid
Systems, vol. 23, no. 2, Elsevier, 2017, pp. 230–53, doi:10.1016/j.nahs.2016.04.006.'
short: 'M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta,
Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.'
date_created: 2018-12-11T11:51:50Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2025-06-11T06:33:00Z
day: '01'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1016/j.nahs.2016.04.006
ec_funded: 1
external_id:
arxiv:
- '1410.5387'
isi:
- '000390637000014'
intvolume: ' 23'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1410.5387
month: '02'
oa: 1
oa_version: Preprint
page: 230 - 253
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: 'Nonlinear Analysis: Hybrid Systems'
publication_status: published
publisher: Elsevier
publist_id: '5800'
quality_controlled: '1'
related_material:
record:
- id: '1689'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Temporal logic control for stochastic linear systems using abstraction refinement
of probabilistic games
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2017'
...
---
_id: '471'
abstract:
- lang: eng
text: 'We present a new algorithm for the statistical model checking of Markov chains
with respect to unbounded temporal properties, including full linear temporal
logic. The main idea is that we monitor each simulation run on the fly, in order
to detect quickly if a bottom strongly connected component is entered with high
probability, in which case the simulation run can be terminated early. As a result,
our simulation runs are often much shorter than required by termination bounds
that are computed a priori for a desired level of confidence on a large state
space. In comparison to previous algorithms for statistical model checking our
method is not only faster in many cases but also requires less information about
the system, namely, only the minimum transition probability that occurs in the
Markov chain. In addition, our method can be generalised to unbounded quantitative
properties such as mean-payoff bounds. '
article_number: '12'
article_processing_charge: No
arxiv: 1
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: Daca P, Henzinger TA, Kretinsky J, Petrov T. Faster statistical model checking
for unbounded temporal properties. ACM Transactions on Computational Logic.
2017;18(2). doi:10.1145/3060139
apa: Daca, P., Henzinger, T. A., Kretinsky, J., & Petrov, T. (2017). Faster
statistical model checking for unbounded temporal properties. ACM Transactions
on Computational Logic. ACM. https://doi.org/10.1145/3060139
chicago: Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov.
“Faster Statistical Model Checking for Unbounded Temporal Properties.” ACM
Transactions on Computational Logic. ACM, 2017. https://doi.org/10.1145/3060139.
ieee: P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Faster statistical
model checking for unbounded temporal properties,” ACM Transactions on Computational
Logic, vol. 18, no. 2. ACM, 2017.
ista: Daca P, Henzinger TA, Kretinsky J, Petrov T. 2017. Faster statistical model
checking for unbounded temporal properties. ACM Transactions on Computational
Logic. 18(2), 12.
mla: Daca, Przemyslaw, et al. “Faster Statistical Model Checking for Unbounded Temporal
Properties.” ACM Transactions on Computational Logic, vol. 18, no. 2, 12,
ACM, 2017, doi:10.1145/3060139.
short: P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, ACM Transactions on Computational
Logic 18 (2017).
corr_author: '1'
date_created: 2018-12-11T11:46:39Z
date_published: 2017-05-01T00:00:00Z
date_updated: 2025-09-22T09:21:16Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/3060139
ec_funded: 1
external_id:
arxiv:
- '1504.05739'
isi:
- '000405208400005'
intvolume: ' 18'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.05739
month: '05'
oa: 1
oa_version: Submitted Version
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: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: ACM Transactions on Computational Logic
publication_identifier:
issn:
- 1529-3785
publication_status: published
publisher: ACM
publist_id: '7349'
quality_controlled: '1'
related_material:
record:
- id: '1234'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Faster statistical model checking for unbounded temporal properties
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 18
year: '2017'
...
---
OA_place: publisher
OA_type: free access
_id: '1066'
abstract:
- lang: eng
text: "Simulation is an attractive alternative to language inclusion for automata
as it is an under-approximation of language inclusion, but usually has much lower
complexity. Simulation has also been extended in two orthogonal directions, namely,
(1) fair simulation, for simulation over specified set of infinite runs; and (2)
quantitative simulation, for simulation between weighted automata. While fair
trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial
time. For weighted automata, the (quantitative) language inclusion problem is
undecidable in general, whereas the (quantitative) simulation reduces to quantitative
games, which admit pseudo-polynomial time algorithms.\r\n\r\nIn this work, we
study (quantitative) simulation for weighted automata with Büchi acceptance conditions,
i.e., we generalize fair simulation from non-weighted automata to weighted automata.
We show that imposing Büchi acceptance conditions on weighted automata changes
many fundamental properties of the simulation games, yet they still admit pseudo-polynomial
time algorithms."
acknowledgement: This research was funded in part by the European Research Council
(ERC) under grant agreements 267989 (QUAREM), 279307 (Graph Games), by the Austrian
Science Fund (FWF) projects S11402-N23 (RiSE), S11407-N23 (RiSE), P23499-N23, and
Microsoft faculty fellows award.
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: Chatterjee K, Henzinger TA, Otop J, Velner Y. Quantitative fair simulation
games. Information and Computation. 2017;254(2):143-166. doi:10.1016/j.ic.2016.10.006
apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Velner, Y. (2017). Quantitative
fair simulation games. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2016.10.006
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner.
“Quantitative Fair Simulation Games.” Information and Computation. Elsevier,
2017. https://doi.org/10.1016/j.ic.2016.10.006.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, “Quantitative fair
simulation games,” Information and Computation, vol. 254, no. 2. Elsevier,
pp. 143–166, 2017.
ista: Chatterjee K, Henzinger TA, Otop J, Velner Y. 2017. Quantitative fair simulation
games. Information and Computation. 254(2), 143–166.
mla: Chatterjee, Krishnendu, et al. “Quantitative Fair Simulation Games.” Information
and Computation, vol. 254, no. 2, Elsevier, 2017, pp. 143–66, doi:10.1016/j.ic.2016.10.006.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Information and Computation
254 (2017) 143–166.
corr_author: '1'
date_created: 2018-12-11T11:49:58Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2026-06-18T08:47:01Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.ic.2016.10.006
ec_funded: 1
external_id:
isi:
- '000402025600002'
intvolume: ' 254'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.ic.2016.10.006
month: '06'
oa: 1
oa_version: Published Version
page: 143 - 166
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _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: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '6322'
quality_controlled: '1'
related_material:
record:
- id: '5428'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Quantitative fair simulation games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 254
year: '2017'
...
---
_id: '465'
abstract:
- lang: eng
text: 'The edit distance between two words w 1 , w 2 is the minimal number of word
operations (letter insertions, deletions, and substitutions) necessary to transform
w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the
edit distance from L 1 to L 2 is the minimal number k such that for every word
from L 1 there exists a word in L 2 with edit distance at most k . We study the
edit distance computation problem between pushdown automata and their subclasses.
The problem of computing edit distance to a pushdown automaton is undecidable,
and in practice, the interesting question is to compute the edit distance from
a pushdown automaton (the implementation, a standard model for programs with recursion)
to a regular language (the specification). In this work, we present a complete
picture of decidability and complexity for the following problems: (1) deciding
whether, for a given threshold k , the edit distance from a pushdown automaton
to a finite automaton is at most k , and (2) deciding whether the edit distance
from a pushdown automaton to a finite automaton is finite. '
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: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Jan
full_name: Otop, Jan
last_name: Otop
citation:
ama: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown
automata. Logical Methods in Computer Science. 2017;13(3). doi:10.23638/LMCS-13(3:23)2017
apa: Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2017).
Edit distance for pushdown automata. Logical Methods in Computer Science.
International Federation for Computational Logic. https://doi.org/10.23638/LMCS-13(3:23)2017
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan
Otop. “Edit Distance for Pushdown Automata.” Logical Methods in Computer Science.
International Federation for Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:23)2017.
ieee: K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance
for pushdown automata,” Logical Methods in Computer Science, vol. 13, no.
3. International Federation for Computational Logic, 2017.
ista: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2017. Edit distance for
pushdown automata. Logical Methods in Computer Science. 13(3).
mla: Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” Logical
Methods in Computer Science, vol. 13, no. 3, International Federation for
Computational Logic, 2017, doi:10.23638/LMCS-13(3:23)2017.
short: K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Logical Methods
in Computer Science 13 (2017).
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T11:46:37Z
date_published: 2017-09-13T00:00:00Z
date_updated: 2026-07-06T13:27:53Z
day: '13'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.23638/LMCS-13(3:23)2017
ec_funded: 1
external_id:
isi:
- '000419163000005'
file:
- access_level: open_access
checksum: 08041379ba408d40664f449eb5907a8f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:37Z
date_updated: 2020-07-14T12:46:33Z
file_id: '5090'
file_name: IST-2015-321-v1+1_main.pdf
file_size: 279071
relation: main_file
- access_level: open_access
checksum: 08041379ba408d40664f449eb5907a8f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:38Z
date_updated: 2020-07-14T12:46:33Z
file_id: '5091'
file_name: IST-2018-955-v1+1_2017_Chatterjee_Edit_distance.pdf
file_size: 279071
relation: main_file
file_date_updated: 2020-07-14T12:46:33Z
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Logical Methods in Computer Science
publication_identifier:
issn:
- 1860-5974
publication_status: published
publisher: International Federation for Computational Logic
publist_id: '7356'
pubrep_id: '955'
quality_controlled: '1'
related_material:
record:
- id: '5438'
relation: earlier_version
status: public
- id: '1610'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Edit distance for pushdown automata
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2017'
...
---
_id: '1093'
abstract:
- lang: eng
text: 'We introduce a general class of distances (metrics) between Markov chains,
which are based on linear behaviour. This class encompasses distances given topologically
(such as the total variation distance or trace distance) as well as by temporal
logics or automata. We investigate which of the distances can be approximated
by observing the systems, i.e. by black-box testing or simulation, and we provide
both negative and positive results. '
acknowledgement: "This research was funded in part by the European Research Council
(ERC) under grant agreement 267989\r\n(QUAREM), the Austrian Science Fund (FWF)
under grants project S11402-N23 (RiSE and SHiNE)\r\nand Z211-N23 (Wittgenstein Award),
by the Czech Science Foundation Grant No. P202/12/G061, and\r\nby the SNSF Advanced
Postdoc. Mobility Fellowship – grant number P300P2_161067."
alternative_title:
- LIPIcs
article_number: '20'
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: 'Daca P, Henzinger TA, Kretinsky J, Petrov T. Linear distances between Markov
chains. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.CONCUR.2016.20'
apa: 'Daca, P., Henzinger, T. A., Kretinsky, J., & Petrov, T. (2016). Linear
distances between Markov chains (Vol. 59). Presented at the CONCUR: Concurrency
Theory, Quebec City; Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CONCUR.2016.20'
chicago: Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov.
“Linear Distances between Markov Chains,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2016. https://doi.org/10.4230/LIPIcs.CONCUR.2016.20.
ieee: 'P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Linear distances
between Markov chains,” presented at the CONCUR: Concurrency Theory, Quebec City;
Canada, 2016, vol. 59.'
ista: 'Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Linear distances between
Markov chains. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 20.'
mla: Daca, Przemyslaw, et al. Linear Distances between Markov Chains. Vol.
59, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.20.
short: P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2016.
conference:
end_date: 2016-08-26
location: Quebec City; Canada
name: 'CONCUR: Concurrency Theory'
start_date: 2016-08-23
date_created: 2018-12-11T11:50:06Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2026-04-15T10:02:12Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
- _id: KrCh
- _id: CaGu
doi: 10.4230/LIPIcs.CONCUR.2016.20
ec_funded: 1
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:39Z
date_updated: 2018-12-12T10:11:39Z
file_id: '4895'
file_name: IST-2017-794-v1+1_LIPIcs-CONCUR-2016-20.pdf
file_size: 501827
relation: main_file
file_date_updated: 2018-12-12T10:11:39Z
has_accepted_license: '1'
intvolume: ' 59'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6283'
pubrep_id: '794'
quality_controlled: '1'
related_material:
record:
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Linear distances between Markov chains
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '2016'
...
---
_id: '1095'
abstract:
- lang: eng
text: ' The semantics of concurrent data structures is usually given by a sequential
specification and a consistency condition. Linearizability is the most popular
consistency condition due to its simplicity and general applicability. Nevertheless,
for applications that do not require all guarantees offered by linearizability,
recent research has focused on improving performance and scalability of concurrent
data structures by relaxing their semantics. In this paper, we present local linearizability,
a relaxed consistency condition that is applicable to container-type concurrent
data structures like pools, queues, and stacks. While linearizability requires
that the effect of each operation is observed by all threads at the same time,
local linearizability only requires that for each thread T, the effects of its
local insertion operations and the effects of those removal operations that remove
values inserted by T are observed by all threads at the same time. We investigate
theoretical and practical properties of local linearizability and its relationship
to many existing consistency conditions. We present a generic implementation method
for locally linearizable data structures that uses existing linearizable data
structures as building blocks. Our implementations show performance and scalability
improvements over the original building blocks and outperform the fastest existing
container-type implementations. '
acknowledgement: "This work has been supported by the National Research Network RiSE
on Rigorous Systems Engineering\r\n(Austrian Science Fund (FWF): S11402-N23, S11403-N23,
S11404-N23, S11411-N23), a Google\r\nPhD Fellowship, an Erwin Schrödinger Fellowship
(Austrian Science Fund (FWF): J3696-N26), EPSRC\r\ngrants EP/H005633/1 and EP/K008528/1,
the Vienna Science and Technology Fund (WWTF) trough\r\ngrant PROSEED, the European
Research Council (ERC) under grant 267989 (QUAREM) and by the\r\nAustrian Science
Fund (FWF) under grant Z211-N23 (Wittgenstein Award)."
alternative_title:
- LIPIcs
article_number: '6'
author:
- first_name: Andreas
full_name: Haas, Andreas
last_name: Haas
- 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: Andreas
full_name: Holzer, Andreas
last_name: Holzer
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Michael
full_name: Lippautz, Michael
last_name: Lippautz
- first_name: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
- first_name: Helmut
full_name: Veith, Helmut
last_name: Veith
citation:
ama: 'Haas A, Henzinger TA, Holzer A, et al. Local linearizability for concurrent
container-type data structures. In: Leibniz International Proceedings in Informatics.
Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.CONCUR.2016.6'
apa: 'Haas, A., Henzinger, T. A., Holzer, A., Kirsch, C., Lippautz, M., Payer, H.,
… Veith, H. (2016). Local linearizability for concurrent container-type data structures.
In Leibniz International Proceedings in Informatics (Vol. 59). Quebec City;
Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2016.6'
chicago: Haas, Andreas, Thomas A Henzinger, Andreas Holzer, Christoph Kirsch, Michael
Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. “Local Linearizability
for Concurrent Container-Type Data Structures.” In Leibniz International Proceedings
in Informatics, Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2016. https://doi.org/10.4230/LIPIcs.CONCUR.2016.6.
ieee: A. Haas et al., “Local linearizability for concurrent container-type
data structures,” in Leibniz International Proceedings in Informatics,
Quebec City; Canada, 2016, vol. 59.
ista: 'Haas A, Henzinger TA, Holzer A, Kirsch C, Lippautz M, Payer H, Sezgin A,
Sokolova A, Veith H. 2016. Local linearizability for concurrent container-type
data structures. Leibniz International Proceedings in Informatics. CONCUR: Concurrency
Theory, LIPIcs, vol. 59, 6.'
mla: Haas, Andreas, et al. “Local Linearizability for Concurrent Container-Type
Data Structures.” Leibniz International Proceedings in Informatics, vol.
59, 6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.6.
short: A. Haas, T.A. Henzinger, A. Holzer, C. Kirsch, M. Lippautz, H. Payer, A.
Sezgin, A. Sokolova, H. Veith, in:, Leibniz International Proceedings in Informatics,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
end_date: 2016-08-26
location: Quebec City; Canada
name: 'CONCUR: Concurrency Theory'
start_date: 2016-08-23
date_created: 2018-12-11T11:50:07Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2025-04-15T06:25:58Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2016.6
ec_funded: 1
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:10Z
date_updated: 2018-12-12T10:10:10Z
file_id: '4795'
file_name: IST-2017-793-v1+1_LIPIcs-CONCUR-2016-6.pdf
file_size: 589747
relation: main_file
file_date_updated: 2018-12-12T10:10:10Z
has_accepted_license: '1'
intvolume: ' 59'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: Leibniz International Proceedings in Informatics
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6280'
pubrep_id: '793'
quality_controlled: '1'
scopus_import: 1
status: public
title: Local linearizability for concurrent container-type data structures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 59
year: '2016'
...
---
_id: '1103'
abstract:
- lang: eng
text: We propose two parallel state-space-exploration algorithms for hybrid automaton
(HA), with the goal of enhancing performance on multi-core shared-memory systems.
The first uses the parallel, breadth-first-search algorithm (PBFS) of the SPIN
model checker, when traversing the discrete modes of the HA, and enhances it with
a parallel exploration of the continuous states within each mode. We show that
this simple-minded extension of PBFS does not provide the desired load balancing
in many HA benchmarks. The second algorithm is a task-parallel BFS algorithm (TP-BFS),
which uses a cheap precomputation of the cost associated with the post operations
(both continuous and discrete) in order to improve load balancing. We illustrate
the TP-BFS and the cost precomputation of the post operators on a support-function-based
algorithm for state-space exploration. The performance comparison of the two algorithms
shows that, in general, TP-BFS provides a better utilization/load-balancing of
the CPU. Both algorithms are implemented in the model checker XSpeed. Our experiments
show a maximum speed-up of more than 2000 χ on a navigation benchmark, with respect
to SpaceEx LGG scenario. In order to make the comparison fair, we employed an
equal number of post operations in both tools. To the best of our knowledge, this
paper represents the first attempt to provide parallel, reachability-analysis
algorithms for HA.
acknowledgement: This work was supported in part by DST-SERB, GoI under Project No.
YSS/2014/000623 and by the European Research Council (ERC) under grant 267989 (QUAREM)
and by the Austrian Science Fund (FWF) under grants S11402-N23, S11405-N23 and S11412-N23
(RiSE/SHiNE) and Z211-N23 (Wittgenstein Award).
article_number: '7797741'
article_processing_charge: No
arxiv: 1
author:
- first_name: Amit
full_name: Gurung, Amit
last_name: Gurung
- first_name: Arup
full_name: Deka, Arup
last_name: Deka
- first_name: Ezio
full_name: Bartocci, Ezio
last_name: Bartocci
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Radu
full_name: Grosu, Radu
last_name: Grosu
- first_name: Rajarshi
full_name: Ray, Rajarshi
last_name: Ray
citation:
ama: 'Gurung A, Deka A, Bartocci E, Bogomolov S, Grosu R, Ray R. Parallel reachability
analysis for hybrid systems. In: IEEE; 2016. doi:10.1109/MEMCOD.2016.7797741'
apa: 'Gurung, A., Deka, A., Bartocci, E., Bogomolov, S., Grosu, R., & Ray, R.
(2016). Parallel reachability analysis for hybrid systems. Presented at the MEMOCODE:
Conference on Formal Methods and Models for System Design, Kanpur, India : IEEE.
https://doi.org/10.1109/MEMCOD.2016.7797741'
chicago: Gurung, Amit, Arup Deka, Ezio Bartocci, Sergiy Bogomolov, Radu Grosu, and
Rajarshi Ray. “Parallel Reachability Analysis for Hybrid Systems.” IEEE, 2016.
https://doi.org/10.1109/MEMCOD.2016.7797741.
ieee: 'A. Gurung, A. Deka, E. Bartocci, S. Bogomolov, R. Grosu, and R. Ray, “Parallel
reachability analysis for hybrid systems,” presented at the MEMOCODE: Conference
on Formal Methods and Models for System Design, Kanpur, India , 2016.'
ista: 'Gurung A, Deka A, Bartocci E, Bogomolov S, Grosu R, Ray R. 2016. Parallel
reachability analysis for hybrid systems. MEMOCODE: Conference on Formal Methods
and Models for System Design, 7797741.'
mla: Gurung, Amit, et al. Parallel Reachability Analysis for Hybrid Systems.
7797741, IEEE, 2016, doi:10.1109/MEMCOD.2016.7797741.
short: A. Gurung, A. Deka, E. Bartocci, S. Bogomolov, R. Grosu, R. Ray, in:, IEEE,
2016.
conference:
end_date: 2016-11-20
location: 'Kanpur, India '
name: 'MEMOCODE: Conference on Formal Methods and Models for System Design'
start_date: 2016-11-18
date_created: 2018-12-11T11:50:09Z
date_published: 2016-12-27T00:00:00Z
date_updated: 2025-06-04T11:52:29Z
day: '27'
department:
- _id: ToHe
doi: 10.1109/MEMCOD.2016.7797741
ec_funded: 1
external_id:
arxiv:
- '1606.05473'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1606.05473
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: IEEE
publist_id: '6272'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parallel reachability analysis for hybrid systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
OA_place: publisher
_id: '1130'
abstract:
- lang: eng
text: "In this thesis we present a computer-aided programming approach to concurrency.
Our approach helps the programmer by automatically fixing concurrency-related
bugs, i.e. bugs that occur when the program is executed using an aggressive preemptive
scheduler, but not when using a non-preemptive (cooperative) scheduler. Bugs are
program behaviours that are incorrect w.r.t. a specification. We consider both
user-provided explicit specifications in the form of assertion\r\nstatements in
the code as well as an implicit specification. The implicit specification is inferred
from the non-preemptive behaviour. Let us consider sequences of calls that the
program makes to an external interface. The implicit specification requires that
any such sequence produced under a preemptive scheduler should be included in
the set of sequences produced under a non-preemptive scheduler. We consider several
semantics-preserving fixes that go beyond atomic sections typically explored in
the synchronisation synthesis literature. Our synthesis is able to place locks,
barriers and wait-signal statements and last, but not least reorder independent
statements. The latter may be useful if a thread is released to early, e.g., before
some initialisation is completed. We guarantee that our synthesis does not introduce
deadlocks and that the synchronisation inserted is optimal w.r.t. a given objective
function. We dub our solution trace-based synchronisation synthesis and it is
loosely based on counterexample-guided inductive synthesis (CEGIS). The synthesis
works by discovering a trace that is incorrect w.r.t. the specification and identifying
ordering constraints crucial to trigger the specification violation. Synchronisation
may be placed immediately (greedy approach) or delayed until all incorrect traces
are found (non-greedy approach). For the non-greedy approach we construct a set
of global constraints over synchronisation placements. Each model of the global
constraints set corresponds to a correctness-ensuring synchronisation placement.
The placement that is optimal w.r.t. the given objective function is chosen as
the synchronisation solution. We evaluate our approach on a number of realistic
(albeit simplified) Linux device-driver\r\nbenchmarks. The benchmarks are versions
of the drivers with known concurrency-related bugs. For the experiments with an
explicit specification we added assertions that would detect the bugs in the experiments.
Device drivers lend themselves to implicit specification, where the device and
the operating system are the external interfaces. Our experiments demonstrate
that our synthesis method is precise and efficient. We implemented objective functions
for coarse-grained and fine-grained locking and observed that different synchronisation
placements are produced for our experiments, favouring e.g. a minimal number of
synchronisation operations or maximum concurrency."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Thorsten
full_name: Tarrach, Thorsten
id: 3D6E8F2C-F248-11E8-B48F-1D18A9856A87
last_name: Tarrach
orcid: 0000-0003-4409-8487
citation:
ama: Tarrach T. Automatic synthesis of synchronisation primitives for concurrent
programs. 2016. doi:10.15479/at:ista:1130
apa: Tarrach, T. (2016). Automatic synthesis of synchronisation primitives for
concurrent programs. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:1130
chicago: Tarrach, Thorsten. “Automatic Synthesis of Synchronisation Primitives for
Concurrent Programs.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/at:ista:1130.
ieee: T. Tarrach, “Automatic synthesis of synchronisation primitives for concurrent
programs,” Institute of Science and Technology Austria, 2016.
ista: Tarrach T. 2016. Automatic synthesis of synchronisation primitives for concurrent
programs. Institute of Science and Technology Austria.
mla: Tarrach, Thorsten. Automatic Synthesis of Synchronisation Primitives for
Concurrent Programs. Institute of Science and Technology Austria, 2016, doi:10.15479/at:ista:1130.
short: T. Tarrach, Automatic Synthesis of Synchronisation Primitives for Concurrent
Programs, Institute of Science and Technology Austria, 2016.
corr_author: '1'
date_created: 2018-12-11T11:50:19Z
date_published: 2016-07-07T00:00:00Z
date_updated: 2026-04-09T10:54:01Z
day: '07'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: ToHe
- _id: GradSch
doi: 10.15479/at:ista:1130
ec_funded: 1
file:
- access_level: open_access
checksum: 319a506831650327e85376db41fc1094
content_type: application/pdf
creator: dernst
date_created: 2021-02-22T11:39:32Z
date_updated: 2021-02-22T11:39:32Z
file_id: '9179'
file_name: 2016_Tarrach_Thesis.pdf
file_size: 1523935
relation: main_file
success: 1
- access_level: closed
checksum: 39efcd789f0ad859ff15652cb7afc412
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-16T14:14:38Z
date_updated: 2021-11-17T13:46:55Z
file_id: '10296'
file_name: 2016_Tarrach_Thesispdfa.pdf
file_size: 1306068
relation: main_file
file_date_updated: 2021-11-17T13:46:55Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://thorstent.github.io/theses/phd_thorsten_tarrach.pdf
month: '07'
oa: 1
oa_version: Published Version
page: '151'
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6230'
related_material:
record:
- id: '2218'
relation: part_of_dissertation
status: public
- id: '2445'
relation: part_of_dissertation
status: public
- id: '1729'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
title: Automatic synthesis of synchronisation primitives for concurrent programs
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2016'
...
---
_id: '1135'
abstract:
- lang: eng
text: 'Time-triggered (TT) switched networks are a deterministic communication infrastructure
used by real-time distributed embedded systems. These networks rely on the notion
of globally discretized time (i.e. time slots) and a static TT schedule that prescribes
which message is sent through which link at every time slot, such that all messages
reach their destination before a global timeout. These schedules are generated
offline, assuming a static network with fault-free links, and entrusting all error-handling
functions to the end user. Assuming the network is static is an over-optimistic
view, and indeed links tend to fail in practice. We study synthesis of TT schedules
on a network in which links fail over time and we assume the switches run a very
simple error-recovery protocol once they detect a crashed link. We address the
problem of finding a pk; qresistant schedule; namely, one that, assuming the switches
run a fixed error-recovery protocol, guarantees that the number of messages that
arrive at their destination by the timeout is at least no matter what sequence
of at most k links fail. Thus, we maintain the simplicity of the switches while
giving a guarantee on the number of messages that meet the timeout. We show how
a pk; q-resistant schedule can be obtained using a CEGAR-like approach: find a
schedule, decide whether it is pk; q-resistant, and if it is not, use the witnessing
fault sequence to generate a constraint that is added to the program. The newly
added constraint disallows the schedule to be regenerated in a future iteration
while also eliminating several other schedules that are not pk; q-resistant. We
illustrate the applicability of our approach using an SMT-based implementation.
© 2016 ACM.'
article_number: '26'
article_processing_charge: No
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- first_name: Shibashis
full_name: Guha, Shibashis
last_name: Guha
- first_name: Guillermo
full_name: Rodríguez Navas, Guillermo
last_name: Rodríguez Navas
citation:
ama: 'Avni G, Guha S, Rodríguez Navas G. Synthesizing time triggered schedules for
switched networks with faulty links. In: Proceedings of the 13th International
Conference on Embedded Software . ACM; 2016. doi:10.1145/2968478.2968499'
apa: 'Avni, G., Guha, S., & Rodríguez Navas, G. (2016). Synthesizing time triggered
schedules for switched networks with faulty links. In Proceedings of the 13th
International Conference on Embedded Software . Pittsburgh, PA, USA: ACM.
https://doi.org/10.1145/2968478.2968499'
chicago: Avni, Guy, Shibashis Guha, and Guillermo Rodríguez Navas. “Synthesizing
Time Triggered Schedules for Switched Networks with Faulty Links.” In Proceedings
of the 13th International Conference on Embedded Software . ACM, 2016. https://doi.org/10.1145/2968478.2968499.
ieee: G. Avni, S. Guha, and G. Rodríguez Navas, “Synthesizing time triggered schedules
for switched networks with faulty links,” in Proceedings of the 13th International
Conference on Embedded Software , Pittsburgh, PA, USA, 2016.
ista: 'Avni G, Guha S, Rodríguez Navas G. 2016. Synthesizing time triggered schedules
for switched networks with faulty links. Proceedings of the 13th International
Conference on Embedded Software . EMSOFT: Embedded Software , 26.'
mla: Avni, Guy, et al. “Synthesizing Time Triggered Schedules for Switched Networks
with Faulty Links.” Proceedings of the 13th International Conference on Embedded
Software , 26, ACM, 2016, doi:10.1145/2968478.2968499.
short: G. Avni, S. Guha, G. Rodríguez Navas, in:, Proceedings of the 13th International
Conference on Embedded Software , ACM, 2016.
conference:
end_date: 2016-10-07
location: Pittsburgh, PA, USA
name: 'EMSOFT: Embedded Software '
start_date: 2016-10-01
date_created: 2018-12-11T11:50:20Z
date_published: 2016-10-01T00:00:00Z
date_updated: 2025-09-22T14:14:05Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1145/2968478.2968499
ec_funded: 1
external_id:
isi:
- '000414220100026'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:31Z
date_updated: 2018-12-12T10:09:31Z
file_id: '4755'
file_name: IST-2016-644-v1+1_emsoft-no-format.pdf
file_size: 279240
relation: main_file
file_date_updated: 2018-12-12T10:09:31Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication: 'Proceedings of the 13th International Conference on Embedded Software '
publication_status: published
publisher: ACM
publist_id: '6223'
pubrep_id: '644'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Synthesizing time triggered schedules for switched networks with faulty links
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2016'
...
---
_id: '1148'
abstract:
- lang: eng
text: Continuous-time Markov chain (CTMC) models have become a central tool for
understanding the dynamics of complex reaction networks and the importance of
stochasticity in the underlying biochemical processes. When such models are employed
to answer questions in applications, in order to ensure that the model provides
a sufficiently accurate representation of the real system, it is of vital importance
that the model parameters are inferred from real measured data. This, however,
is often a formidable task and all of the existing methods fail in one case or
the other, usually because the underlying CTMC model is high-dimensional and computationally
difficult to analyze. The parameter inference methods that tend to scale best
in the dimension of the CTMC are based on so-called moment closure approximations.
However, there exists a large number of different moment closure approximations
and it is typically hard to say a priori which of the approximations is the most
suitable for the inference procedure. Here, we propose a moment-based parameter
inference method that automatically chooses the most appropriate moment closure
method. Accordingly, contrary to existing methods, the user is not required to
be experienced in moment closure techniques. In addition to that, our method adaptively
changes the approximation during the parameter inference to ensure that always
the best approximation is used, even in cases where different approximations are
best in different regions of the parameter space. © 2016 Elsevier Ireland Ltd
acknowledgement: This work is based on the CMSB 2015 paper “Adaptive moment closure
for parameter inference of biochemical reaction networks” (Bogomolov et al., 2015).
The work was partly supported by the German Research Foundation (DFG) as part of
the Transregional Collaborative Research Center “Automatic Verification and Analysis
of Complex Systems” (SFB/TR 14 AVACS1), by the European Research Council (ERC) under
grant 267989 (QUAREM) and by the Austrian Science Fund (FWF) under grants S11402-N23
(RiSE) and Z211-N23 (Wittgenstein Award). J.R. acknowledges support from the People
Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme
(FP7/2007-2013) under REA grant agreement no. 291734.
article_processing_charge: No
author:
- first_name: Christian
full_name: Schilling, Christian
last_name: Schilling
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- 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: Andreas
full_name: Podelski, Andreas
last_name: Podelski
- first_name: Jakob
full_name: Ruess, Jakob
id: 4A245D00-F248-11E8-B48F-1D18A9856A87
last_name: Ruess
orcid: 0000-0003-1615-3282
citation:
ama: Schilling C, Bogomolov S, Henzinger TA, Podelski A, Ruess J. Adaptive moment
closure for parameter inference of biochemical reaction networks. Biosystems.
2016;149:15-25. doi:10.1016/j.biosystems.2016.07.005
apa: Schilling, C., Bogomolov, S., Henzinger, T. A., Podelski, A., & Ruess,
J. (2016). Adaptive moment closure for parameter inference of biochemical reaction
networks. Biosystems. Elsevier. https://doi.org/10.1016/j.biosystems.2016.07.005
chicago: Schilling, Christian, Sergiy Bogomolov, Thomas A Henzinger, Andreas Podelski,
and Jakob Ruess. “Adaptive Moment Closure for Parameter Inference of Biochemical
Reaction Networks.” Biosystems. Elsevier, 2016. https://doi.org/10.1016/j.biosystems.2016.07.005.
ieee: C. Schilling, S. Bogomolov, T. A. Henzinger, A. Podelski, and J. Ruess, “Adaptive
moment closure for parameter inference of biochemical reaction networks,” Biosystems,
vol. 149. Elsevier, pp. 15–25, 2016.
ista: Schilling C, Bogomolov S, Henzinger TA, Podelski A, Ruess J. 2016. Adaptive
moment closure for parameter inference of biochemical reaction networks. Biosystems.
149, 15–25.
mla: Schilling, Christian, et al. “Adaptive Moment Closure for Parameter Inference
of Biochemical Reaction Networks.” Biosystems, vol. 149, Elsevier, 2016,
pp. 15–25, doi:10.1016/j.biosystems.2016.07.005.
short: C. Schilling, S. Bogomolov, T.A. Henzinger, A. Podelski, J. Ruess, Biosystems
149 (2016) 15–25.
date_created: 2018-12-11T11:50:24Z
date_published: 2016-11-01T00:00:00Z
date_updated: 2025-09-23T07:44:57Z
day: '01'
department:
- _id: ToHe
- _id: GaTk
doi: 10.1016/j.biosystems.2016.07.005
ec_funded: 1
external_id:
isi:
- '000390743600003'
intvolume: ' 149'
isi: 1
language:
- iso: eng
month: '11'
oa_version: None
page: 15 - 25
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Biosystems
publication_status: published
publisher: Elsevier
publist_id: '6210'
quality_controlled: '1'
related_material:
record:
- id: '1658'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Adaptive moment closure for parameter inference of biochemical reaction networks
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 149
year: '2016'
...
---
_id: '1182'
abstract:
- lang: eng
text: 'Balanced knockout tournaments are ubiquitous in sports competitions and are
also used in decisionmaking and elections. The traditional computational question,
that asks to compute a draw (optimal draw) that maximizes the winning probability
for a distinguished player, has received a lot of attention. Previous works consider
the problem where the pairwise winning probabilities are known precisely, while
we study how robust is the winning probability with respect to small errors in
the pairwise winning probabilities. First, we present several illuminating examples
to establish: (a) there exist deterministic tournaments (where the pairwise winning
probabilities are 0 or 1) where one optimal draw is much more robust than the
other; and (b) in general, there exist tournaments with slightly suboptimal draws
that are more robust than all the optimal draws. The above examples motivate the
study of the computational problem of robust draws that guarantee a specified
winning probability. Second, we present a polynomial-time algorithm for approximating
the robustness of a draw for sufficiently small errors in pairwise winning probabilities,
and obtain that the stated computational problem is NP-complete. We also show
that two natural cases of deterministic tournaments where the optimal draw could
be computed in polynomial time also admit polynomial-time algorithms to compute
robust optimal draws.'
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Tkadlec J. Robust draws in balanced knockout
tournaments. In: Vol 2016-January. AAAI Press; 2016:172-179.'
apa: 'Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in
balanced knockout tournaments (Vol. 2016–January, pp. 172–179). Presented at the
IJCAI: International Joint Conference on Artificial Intelligence, New York, NY,
USA: AAAI Press.'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Josef Tkadlec. “Robust
Draws in Balanced Knockout Tournaments,” 2016–January:172–79. AAAI Press, 2016.
ieee: 'K. Chatterjee, R. Ibsen-Jensen, and J. Tkadlec, “Robust draws in balanced
knockout tournaments,” presented at the IJCAI: International Joint Conference
on Artificial Intelligence, New York, NY, USA, 2016, vol. 2016–January, pp. 172–179.'
ista: 'Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout
tournaments. IJCAI: International Joint Conference on Artificial Intelligence
vol. 2016–January, 172–179.'
mla: Chatterjee, Krishnendu, et al. Robust Draws in Balanced Knockout Tournaments.
Vol. 2016–January, AAAI Press, 2016, pp. 172–79.
short: K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.
conference:
end_date: 2016-07-15
location: New York, NY, USA
name: 'IJCAI: International Joint Conference on Artificial Intelligence'
start_date: 2016-07-09
corr_author: '1'
date_created: 2018-12-11T11:50:35Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2025-04-22T13:42:22Z
day: '01'
department:
- _id: KrCh
ec_funded: 1
external_id:
arxiv:
- '1604.05090'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05090
month: '01'
oa: 1
oa_version: Preprint
page: 172 - 179
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: AAAI Press
publist_id: '6171'
quality_controlled: '1'
related_material:
link:
- relation: table_of_contents
url: https://www.ijcai.org/proceedings/2016
scopus_import: '1'
status: public
title: Robust draws in balanced knockout tournaments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2016-January
year: '2016'
...
---
_id: '1230'
abstract:
- lang: eng
text: Concolic testing is a promising method for generating test suites for large
programs. However, it suffers from the path-explosion problem and often fails
to find tests that cover difficult-to-reach parts of programs. In contrast, model
checkers based on counterexample-guided abstraction refinement explore programs
exhaustively, while failing to scale on large programs with precision. In this
paper, we present a novel method that iteratively combines concolic testing and
model checking to find a test suite for a given coverage criterion. If concolic
testing fails to cover some test goals, then the model checker refines its program
abstraction to prove more paths infeasible, which reduces the search space for
concolic testing. We have implemented our method on top of the concolictesting
tool Crest and the model checker CpaChecker. We evaluated our tool on a collection
of programs and a category of SvComp benchmarks. In our experiments, we observed
an improvement in branch coverage compared to Crest from 48% to 63% in the best
case, and from 66% to 71% on average.
acknowledgement: "We thank Andrey Kupriyanov for feedback on the manuscript,\r\nand
Michael Tautschnig for help with preparing the experiments. This research was supported
in part by the European Research Council (ERC) under grant 267989 (QUAREM) and by
the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE) and Z211-N23 (Wittgenstein
Award)."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- 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: 'Daca P, Gupta A, Henzinger TA. Abstraction-driven concolic testing. In: Vol
9583. Springer; 2016:328-347. doi:10.1007/978-3-662-49122-5_16'
apa: 'Daca, P., Gupta, A., & Henzinger, T. A. (2016). Abstraction-driven concolic
testing (Vol. 9583, pp. 328–347). Presented at the VMCAI: Verification, Model
Checking and Abstract Interpretation, St. Petersburg, FL, USA: Springer. https://doi.org/10.1007/978-3-662-49122-5_16'
chicago: Daca, Przemyslaw, Ashutosh Gupta, and Thomas A Henzinger. “Abstraction-Driven
Concolic Testing,” 9583:328–47. Springer, 2016. https://doi.org/10.1007/978-3-662-49122-5_16.
ieee: 'P. Daca, A. Gupta, and T. A. Henzinger, “Abstraction-driven concolic testing,”
presented at the VMCAI: Verification, Model Checking and Abstract Interpretation,
St. Petersburg, FL, USA, 2016, vol. 9583, pp. 328–347.'
ista: 'Daca P, Gupta A, Henzinger TA. 2016. Abstraction-driven concolic testing.
VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 9583,
328–347.'
mla: Daca, Przemyslaw, et al. Abstraction-Driven Concolic Testing. Vol. 9583,
Springer, 2016, pp. 328–47, doi:10.1007/978-3-662-49122-5_16.
short: P. Daca, A. Gupta, T.A. Henzinger, in:, Springer, 2016, pp. 328–347.
conference:
end_date: 2016-01-19
location: St. Petersburg, FL, USA
name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
start_date: 2016-01-17
date_created: 2018-12-11T11:50:50Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2026-04-15T10:02:12Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-662-49122-5_16
ec_funded: 1
external_id:
arxiv:
- '1511.02615'
isi:
- '000375148800016'
intvolume: ' 9583'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1511.02615
month: '01'
oa: 1
oa_version: Preprint
page: 328 - 347
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '6104'
quality_controlled: '1'
related_material:
record:
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Abstraction-driven concolic testing
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9583
year: '2016'
...
---
_id: '1234'
abstract:
- lang: eng
text: We present a new algorithm for the statistical model checking of Markov chains
with respect to unbounded temporal properties, including full linear temporal
logic. The main idea is that we monitor each simulation run on the fly, in order
to detect quickly if a bottom strongly connected component is entered with high
probability, in which case the simulation run can be terminated early. As a result,
our simulation runs are often much shorter than required by termination bounds
that are computed a priori for a desired level of confidence on a large state
space. In comparison to previous algorithms for statistical model checking our
method is not only faster in many cases but also requires less information about
the system, namely, only the minimum transition probability that occurs in the
Markov chain. In addition, our method can be generalised to unbounded quantitative
properties such as mean-payoff bounds.
acknowledgement: "This research was funded in part by the European Research Council
(ERC) under\r\ngrant agreement 267989 (QUAREM), the Austrian Science Fund
\ (FWF) under\r\ngrants project S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award),
the Peo-\r\nple Programme (Marie Curie Actions) of the European Union’s Seventh
Framework\r\nProgramme (FP7/2007-2013) REA Grant No 291734, the SNSF Advanced Postdoc.\r\nMobility
Fellowship – grant number P300P2\r\n161067, and the Czech Science Foun-\r\ndation
under grant agreement P202/12/G061."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: 'Daca P, Henzinger TA, Kretinsky J, Petrov T. Faster statistical model checking
for unbounded temporal properties. In: Vol 9636. Springer; 2016:112-129. doi:10.1007/978-3-662-49674-9_7'
apa: 'Daca, P., Henzinger, T. A., Kretinsky, J., & Petrov, T. (2016). Faster
statistical model checking for unbounded temporal properties (Vol. 9636, pp. 112–129).
Presented at the TACAS: Tools and Algorithms for the Construction and Analysis
of Systems, Eindhoven, The Netherlands: Springer. https://doi.org/10.1007/978-3-662-49674-9_7'
chicago: Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov.
“Faster Statistical Model Checking for Unbounded Temporal Properties,” 9636:112–29.
Springer, 2016. https://doi.org/10.1007/978-3-662-49674-9_7.
ieee: 'P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Faster statistical
model checking for unbounded temporal properties,” presented at the TACAS: Tools
and Algorithms for the Construction and Analysis of Systems, Eindhoven, The Netherlands,
2016, vol. 9636, pp. 112–129.'
ista: 'Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Faster statistical model
checking for unbounded temporal properties. TACAS: Tools and Algorithms for the
Construction and Analysis of Systems, LNCS, vol. 9636, 112–129.'
mla: Daca, Przemyslaw, et al. Faster Statistical Model Checking for Unbounded
Temporal Properties. Vol. 9636, Springer, 2016, pp. 112–29, doi:10.1007/978-3-662-49674-9_7.
short: P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Springer, 2016, pp.
112–129.
conference:
end_date: 2016-04-08
location: Eindhoven, The Netherlands
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2016-04-02
date_created: 2018-12-11T11:50:51Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2026-04-15T10:02:12Z
day: '01'
department:
- _id: ToHe
- _id: CaGu
doi: 10.1007/978-3-662-49674-9_7
ec_funded: 1
external_id:
arxiv:
- '1504.05739'
isi:
- '000406428000007'
intvolume: ' 9636'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.05739
month: '01'
oa: 1
oa_version: Preprint
page: 112 - 129
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6099'
quality_controlled: '1'
related_material:
record:
- id: '471'
relation: later_version
status: public
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Faster statistical model checking for unbounded temporal properties
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9636
year: '2016'
...
---
_id: '1341'
abstract:
- lang: eng
text: In resource allocation games, selfish players share resources that are needed
in order to fulfill their objectives. The cost of using a resource depends on
the load on it. In the traditional setting, the players make their choices concurrently
and in one-shot. That is, a strategy for a player is a subset of the resources.
We introduce and study dynamic resource allocation games. In this setting, the
game proceeds in phases. In each phase each player chooses one resource. A scheduler
dictates the order in which the players proceed in a phase, possibly scheduling
several players to proceed concurrently. The game ends when each player has collected
a set of resources that fulfills his objective. The cost for each player then
depends on this set as well as on the load on the resources in it – we consider
both congestion and cost-sharing games. We argue that the dynamic setting is the
suitable setting for many applications in practice. We study the stability of
dynamic resource allocation games, where the appropriate notion of stability is
that of subgame perfect equilibrium, study the inefficiency incurred due to selfish
behavior, and also study problems that are particular to the dynamic setting,
like constraints on the order in which resources can be chosen or the problem
of finding a scheduler that achieves stability.
acknowledgement: This research was supported in part by the European Research Council
(ERC) under grants 267989 (QUAREM) and 278410 (QUALITY), and by the Austrian Science
Fund (FWF) under grants S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- 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: 'Avni G, Henzinger TA, Kupferman O. Dynamic resource allocation games. In:
Vol 9928. Springer; 2016:153-166. doi:10.1007/978-3-662-53354-3_13'
apa: 'Avni, G., Henzinger, T. A., & Kupferman, O. (2016). Dynamic resource allocation
games (Vol. 9928, pp. 153–166). Presented at the SAGT: Symposium on Algorithmic
Game Theory, Liverpool, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53354-3_13'
chicago: Avni, Guy, Thomas A Henzinger, and Orna Kupferman. “Dynamic Resource Allocation
Games,” 9928:153–66. Springer, 2016. https://doi.org/10.1007/978-3-662-53354-3_13.
ieee: 'G. Avni, T. A. Henzinger, and O. Kupferman, “Dynamic resource allocation
games,” presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool,
United Kingdom, 2016, vol. 9928, pp. 153–166.'
ista: 'Avni G, Henzinger TA, Kupferman O. 2016. Dynamic resource allocation games.
SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 153–166.'
mla: Avni, Guy, et al. Dynamic Resource Allocation Games. Vol. 9928, Springer,
2016, pp. 153–66, doi:10.1007/978-3-662-53354-3_13.
short: G. Avni, T.A. Henzinger, O. Kupferman, in:, Springer, 2016, pp. 153–166.
conference:
end_date: 2016-09-21
location: Liverpool, United Kingdom
name: 'SAGT: Symposium on Algorithmic Game Theory'
start_date: 2016-09-19
corr_author: '1'
date_created: 2018-12-11T11:51:28Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2026-04-16T09:35:14Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-662-53354-3_13
ec_funded: 1
external_id:
isi:
- '000389020400013'
file:
- access_level: open_access
checksum: 0825eefd4e22774f6f62cb7d7389b05a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:22Z
date_updated: 2020-07-14T12:44:45Z
file_id: '5073'
file_name: IST-2016-645-v1+1_sagt-cr.pdf
file_size: 243458
relation: main_file
file_date_updated: 2020-07-14T12:44:45Z
has_accepted_license: '1'
intvolume: ' 9928'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Preprint
page: 153 - 166
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
publication_status: published
publisher: Springer
publist_id: '5926'
pubrep_id: '645'
quality_controlled: '1'
related_material:
record:
- id: '6761'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Dynamic resource allocation games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9928
year: '2016'
...