---
_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.
date_created: 2018-12-11T11:50:27Z
date_published: 2017-01-02T00:00:00Z
date_updated: 2023-09-07T11:58:34Z
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: The Wittgenstein Prize
- _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: '1093'
relation: part_of_dissertation
status: public
- id: '1230'
relation: part_of_dissertation
status: public
- id: '1234'
relation: part_of_dissertation
status: public
- id: '1391'
relation: part_of_dissertation
status: public
- id: '1501'
relation: part_of_dissertation
status: public
- id: '1502'
relation: part_of_dissertation
status: public
- id: '2063'
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '647'
abstract:
- lang: eng
text: Despite researchers’ efforts in the last couple of decades, reachability analysis
is still a challenging problem even for linear hybrid systems. Among the existing
approaches, the most practical ones are mainly based on bounded-time reachable
set over-approximations. For the purpose of unbounded-time analysis, one important
strategy is to abstract the original system and find an invariant for the abstraction.
In this paper, we propose an approach to constructing a new kind of abstraction
called conic abstraction for affine hybrid systems, and to computing reachable
sets based on this abstraction. The essential feature of a conic abstraction is
that it partitions the state space of a system into a set of convex polyhedral
cones which is derived from a uniform conic partition of the derivative space.
Such a set of polyhedral cones is able to cut all trajectories of the system into
almost straight segments so that every segment of a reach pipe in a polyhedral
cone tends to be straight as well, and hence can be over-approximated tightly
by polyhedra using similar techniques as HyTech or PHAVer. In particular, for
diagonalizable affine systems, our approach can guarantee to find an invariant
for unbounded reachable sets, which is beyond the capability of bounded-time reachability
analysis tools. We implemented the approach in a tool and experiments on benchmarks
show that our approach is more powerful than SpaceEx and PHAVer in dealing with
diagonalizable systems.
alternative_title:
- LNCS
author:
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- 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: Hui
full_name: Kong, Hui
id: 3BDE25AA-F248-11E8-B48F-1D18A9856A87
last_name: Kong
orcid: 0000-0002-3066-6941
citation:
ama: 'Bogomolov S, Giacobbe M, Henzinger TA, Kong H. Conic abstractions for hybrid
systems. In: Vol 10419. Springer; 2017:116-132. doi:10.1007/978-3-319-65765-3_7'
apa: 'Bogomolov, S., Giacobbe, M., Henzinger, T. A., & Kong, H. (2017). Conic
abstractions for hybrid systems (Vol. 10419, pp. 116–132). Presented at the FORMATS:
Formal Modelling and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_7'
chicago: Bogomolov, Sergiy, Mirco Giacobbe, Thomas A Henzinger, and Hui Kong. “Conic
Abstractions for Hybrid Systems,” 10419:116–32. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_7.
ieee: 'S. Bogomolov, M. Giacobbe, T. A. Henzinger, and H. Kong, “Conic abstractions
for hybrid systems,” presented at the FORMATS: Formal Modelling and Analysis of
Timed Systems, Berlin, Germany, 2017, vol. 10419, pp. 116–132.'
ista: 'Bogomolov S, Giacobbe M, Henzinger TA, Kong H. 2017. Conic abstractions for
hybrid systems. FORMATS: Formal Modelling and Analysis of Timed Systems, LNCS,
vol. 10419, 116–132.'
mla: Bogomolov, Sergiy, et al. Conic Abstractions for Hybrid Systems. Vol.
10419, Springer, 2017, pp. 116–32, doi:10.1007/978-3-319-65765-3_7.
short: S. Bogomolov, M. Giacobbe, T.A. Henzinger, H. Kong, in:, Springer, 2017,
pp. 116–132.
conference:
end_date: 2017-09-07
location: Berlin, Germany
name: 'FORMATS: Formal Modelling and Analysis of Timed Systems'
start_date: 2017-09-05
date_created: 2018-12-11T11:47:41Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-09-07T12:53:00Z
day: '01'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-319-65765-3_7
file:
- access_level: open_access
checksum: faf546914ba29bcf9974ee36b6b16750
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:38Z
date_updated: 2020-07-14T12:47:31Z
file_id: '4956'
file_name: IST-2017-831-v1+1_main.pdf
file_size: 3806864
relation: main_file
file_date_updated: 2020-07-14T12:47:31Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 116 - 132
project:
- _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: The Wittgenstein Prize
publication_identifier:
isbn:
- 978-331965764-6
publication_status: published
publisher: Springer
publist_id: '7129'
pubrep_id: '831'
quality_controlled: '1'
related_material:
record:
- id: '6894'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Conic abstractions for hybrid systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '10419 '
year: '2017'
...
---
_id: '631'
abstract:
- lang: eng
text: Template polyhedra generalize intervals and octagons to polyhedra whose facets
are orthogonal to a given set of arbitrary directions. They have been employed
in the abstract interpretation of programs and, with particular success, in the
reachability analysis of hybrid automata. While previously, the choice of directions
has been left to the user or a heuristic, we present a method for the automatic
discovery of directions that generalize and eliminate spurious counterexamples.
We show that for the class of convex hybrid automata, i.e., hybrid automata with
(possibly nonlinear) convex constraints on derivatives, such directions always
exist and can be found using convex optimization. We embed our method inside a
CEGAR loop, thus enabling the time-unbounded reachability analysis of an important
and richer class of hybrid automata than was previously possible. We evaluate
our method on several benchmarks, demonstrating also its superior efficiency for
the special case of linear hybrid automata.
acknowledgement: This research was supported in part by the Austrian Science Fund
(FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), by
the European Commission under grant 643921 (UnCoVerCPS), and by the ARC project
DP140104219 (Robust AI Planning for Hybrid Systems).
alternative_title:
- LNCS
author:
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Goran
full_name: Frehse, Goran
last_name: Frehse
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- 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: 'Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. Counterexample guided refinement
of template polyhedra. In: Vol 10205. Springer; 2017:589-606. doi:10.1007/978-3-662-54577-5_34'
apa: 'Bogomolov, S., Frehse, G., Giacobbe, M., & Henzinger, T. A. (2017). Counterexample
guided refinement of template polyhedra (Vol. 10205, pp. 589–606). Presented at
the TACAS: Tools and Algorithms for the Construction and Analysis of Systems,
Uppsala, Sweden: Springer. https://doi.org/10.1007/978-3-662-54577-5_34'
chicago: Bogomolov, Sergiy, Goran Frehse, Mirco Giacobbe, and Thomas A Henzinger.
“Counterexample Guided Refinement of Template Polyhedra,” 10205:589–606. Springer,
2017. https://doi.org/10.1007/978-3-662-54577-5_34.
ieee: 'S. Bogomolov, G. Frehse, M. Giacobbe, and T. A. Henzinger, “Counterexample
guided refinement of template polyhedra,” presented at the TACAS: Tools and Algorithms
for the Construction and Analysis of Systems, Uppsala, Sweden, 2017, vol. 10205,
pp. 589–606.'
ista: 'Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. 2017. Counterexample guided
refinement of template polyhedra. TACAS: Tools and Algorithms for the Construction
and Analysis of Systems, LNCS, vol. 10205, 589–606.'
mla: Bogomolov, Sergiy, et al. Counterexample Guided Refinement of Template Polyhedra.
Vol. 10205, Springer, 2017, pp. 589–606, doi:10.1007/978-3-662-54577-5_34.
short: S. Bogomolov, G. Frehse, M. Giacobbe, T.A. Henzinger, in:, Springer, 2017,
pp. 589–606.
conference:
end_date: 2017-04-29
location: Uppsala, Sweden
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2017-04-22
date_created: 2018-12-11T11:47:36Z
date_published: 2017-03-31T00:00:00Z
date_updated: 2023-09-07T12:53:00Z
day: '31'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-662-54577-5_34
file:
- access_level: open_access
checksum: f395d0d20102b89aeaad8b4ef4f18f4f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:41Z
date_updated: 2020-07-14T12:47:27Z
file_id: '4897'
file_name: IST-2017-741-v1+1_main.pdf
file_size: 569863
relation: main_file
- access_level: open_access
checksum: f416ee1ae4497b23ecdf28b1f18bb8df
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:42Z
date_updated: 2020-07-14T12:47:27Z
file_id: '4898'
file_name: IST-2018-741-v2+2_main.pdf
file_size: 563276
relation: main_file
file_date_updated: 2020-07-14T12:47:27Z
has_accepted_license: '1'
intvolume: ' 10205'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 589 - 606
project:
- _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: The Wittgenstein Prize
publication_identifier:
isbn:
- 978-366254576-8
publication_status: published
publisher: Springer
publist_id: '7162'
pubrep_id: '966'
quality_controlled: '1'
related_material:
record:
- id: '6894'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Counterexample guided refinement of template polyhedra
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10205
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
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: 2023-09-20T09:43:09Z
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: '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.
date_created: 2018-12-11T11:51:27Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T11:13:51Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s10703-016-0256-5
ec_funded: 1
external_id:
isi:
- '000399888900001'
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
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 97 - 139
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: The Wittgenstein Prize
- _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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 50
year: '2017'
...