---
_id: '1116'
abstract:
- lang: eng
text: "Time-triggered switched networks are a deterministic communication infrastructure
used by real-time distributed embedded systems. Due to the criticality of the
applications running over them, developers need to ensure that end-to-end communication
is dependable and predictable. Traditional approaches assume static networks that
are not flexible to changes caused by reconfigurations or, more importantly, faults,
which are dealt with in the application using redundancy. We adopt the concept
of handling faults in the switches from non-real-time networks while maintaining
the required predictability. \r\n\r\nWe study a class of forwarding schemes that
can handle various types of failures. We consider probabilistic failures. We study
a class of forwarding schemes that can handle various types of failures. We consider
probabilistic failures. For a given network with a forwarding scheme and a constant
ℓ, we compute the {\\em score} of the scheme, namely the probability (induced
by faults) that at least ℓ messages arrive on time. We reduce the scoring problem
to a reachability problem on a Markov chain with a "product-like" structure.
Its special structure allows us to reason about it symbolically, and reduce the
scoring problem to #SAT. Our solution is generic and can be adapted to different
networks and other contexts. Also, we show the computational complexity of the
scoring problem is #P-complete, and we study methods to estimate the score. We
evaluate the effectiveness of our techniques with an implementation. "
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: Shubham
full_name: Goel, Shubham
last_name: Goel
- 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: Guillermo
full_name: Rodríguez Navas, Guillermo
last_name: Rodríguez Navas
citation:
ama: 'Avni G, Goel S, Henzinger TA, Rodríguez Navas G. Computing scores of forwarding
schemes in switched networks with probabilistic faults. In: Vol 10206. Springer;
2017:169-187. doi:10.1007/978-3-662-54580-5_10'
apa: 'Avni, G., Goel, S., Henzinger, T. A., & Rodríguez Navas, G. (2017). Computing
scores of forwarding schemes in switched networks with probabilistic faults (Vol.
10206, pp. 169–187). 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-54580-5_10'
chicago: Avni, Guy, Shubham Goel, Thomas A Henzinger, and Guillermo Rodríguez Navas.
“Computing Scores of Forwarding Schemes in Switched Networks with Probabilistic
Faults,” 10206:169–87. Springer, 2017. https://doi.org/10.1007/978-3-662-54580-5_10.
ieee: 'G. Avni, S. Goel, T. A. Henzinger, and G. Rodríguez Navas, “Computing scores
of forwarding schemes in switched networks with probabilistic faults,” presented
at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems,
Uppsala, Sweden, 2017, vol. 10206, pp. 169–187.'
ista: 'Avni G, Goel S, Henzinger TA, Rodríguez Navas G. 2017. Computing scores of
forwarding schemes in switched networks with probabilistic faults. TACAS: Tools
and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10206,
169–187.'
mla: Avni, Guy, et al. Computing Scores of Forwarding Schemes in Switched Networks
with Probabilistic Faults. Vol. 10206, Springer, 2017, pp. 169–87, doi:10.1007/978-3-662-54580-5_10.
short: G. Avni, S. Goel, T.A. Henzinger, G. Rodríguez Navas, in:, Springer, 2017,
pp. 169–187.
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
corr_author: '1'
date_created: 2018-12-11T11:50:14Z
date_published: 2017-03-31T00:00:00Z
date_updated: 2026-04-16T09:56:24Z
day: '31'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-662-54580-5_10
external_id:
isi:
- '000440733400010'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:37Z
date_updated: 2018-12-12T10:08:37Z
file_id: '4698'
file_name: IST-2017-758-v1+1_tacas-cr.pdf
file_size: 321800
relation: main_file
file_date_updated: 2018-12-12T10:08:37Z
has_accepted_license: '1'
intvolume: ' 10206'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 169 - 187
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: Formal methods for the design and analysis of complex systems
publication_identifier:
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '6246'
pubrep_id: '758'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing scores of forwarding schemes in switched networks with probabilistic
faults
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 10206
year: '2017'
...
---
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
license: https://creativecommons.org/licenses/by/4.0/
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'
...
---
_id: '549'
abstract:
- lang: eng
text: Model checking is usually based on a comprehensive traversal of the state
space. Causality-based model checking is a radically different approach that instead
analyzes the cause-effect relationships in a program. We give an overview on a
new class of model checking algorithms that capture the causal relationships in
a special data structure called concurrent traces. Concurrent traces identify
key events in an execution history and link them through their cause-effect relationships.
The model checker builds a tableau of concurrent traces, where the case splits
represent different causal explanations of a hypothetical error. Causality-based
model checking has been implemented in the ARCTOR tool, and applied to previously
intractable multi-threaded benchmarks.
alternative_title:
- EPTCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Bernd
full_name: Finkbeiner, Bernd
last_name: Finkbeiner
- first_name: Andrey
full_name: Kupriyanov, Andrey
id: 2C311BF8-F248-11E8-B48F-1D18A9856A87
last_name: Kupriyanov
citation:
ama: 'Finkbeiner B, Kupriyanov A. Causality-based model checking. In: Electronic
Proceedings in Theoretical Computer Science. Vol 259. Open Publishing Association;
2017:31-38. doi:10.4204/EPTCS.259.3'
apa: 'Finkbeiner, B., & Kupriyanov, A. (2017). Causality-based model checking.
In Electronic Proceedings in Theoretical Computer Science (Vol. 259, pp.
31–38). Uppsala, Sweden: Open Publishing Association. https://doi.org/10.4204/EPTCS.259.3'
chicago: Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.”
In Electronic Proceedings in Theoretical Computer Science, 259:31–38. Open
Publishing Association, 2017. https://doi.org/10.4204/EPTCS.259.3.
ieee: B. Finkbeiner and A. Kupriyanov, “Causality-based model checking,” in Electronic
Proceedings in Theoretical Computer Science, Uppsala, Sweden, 2017, vol. 259,
pp. 31–38.
ista: 'Finkbeiner B, Kupriyanov A. 2017. Causality-based model checking. Electronic
Proceedings in Theoretical Computer Science. CREST: Causal Reasoning for Embedded
and Safety-Critical Systems Technologies, EPTCS, vol. 259, 31–38.'
mla: Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.”
Electronic Proceedings in Theoretical Computer Science, vol. 259, Open
Publishing Association, 2017, pp. 31–38, doi:10.4204/EPTCS.259.3.
short: B. Finkbeiner, A. Kupriyanov, in:, Electronic Proceedings in Theoretical
Computer Science, Open Publishing Association, 2017, pp. 31–38.
conference:
end_date: 2017-04-29
location: Uppsala, Sweden
name: 'CREST: Causal Reasoning for Embedded and Safety-Critical Systems Technologies'
start_date: 2017-04-29
corr_author: '1'
date_created: 2018-12-11T11:47:07Z
date_published: 2017-10-10T00:00:00Z
date_updated: 2025-09-18T09:38:35Z
day: '10'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4204/EPTCS.259.3
external_id:
arxiv:
- '1710.03391'
isi:
- '000439358700004'
file:
- access_level: open_access
checksum: 6274f6c0da3376a7b079180d81568518
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:21Z
date_updated: 2020-07-14T12:47:00Z
file_id: '4939'
file_name: IST-2018-925-v1+1_1710.03391v1.pdf
file_size: 209294
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
intvolume: ' 259'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1710.03391
month: '10'
oa: 1
oa_version: Submitted Version
page: 31 - 38
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: Formal methods for the design and analysis of complex systems
publication: Electronic Proceedings in Theoretical Computer Science
publication_identifier:
issn:
- 2075-2180
publication_status: published
publisher: Open Publishing Association
publist_id: '7264'
pubrep_id: '925'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Causality-based model checking
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 259
year: '2017'
...
---
_id: '625'
abstract:
- lang: eng
text: In the analysis of reactive systems a quantitative objective assigns a real
value to every trace of the system. The value decision problem for a quantitative
objective requires a trace whose value is at least a given threshold, and the
exact value decision problem requires a trace whose value is exactly the threshold.
We compare the computational complexity of the value and exact value decision
problems for classical quantitative objectives, such as sum, discounted sum, energy,
and mean-payoff for two standard models of reactive systems, namely, graphs and
graph games.
acknowledgement: 'This research was supported in part by the Austrian Science Fund
(FWF) under grants S11402-N23 and S11407-N23 (RiSE/SHiNE), and Z211-N23 (Wittgenstein
Award), ERC Start grant (279307: Graph Games), Vienna Science and Technology Fund
(WWTF) through project ICT15-003.'
alternative_title:
- LNCS
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA. The cost of exactness in quantitative
reachability. In: Aceto L, Bacci G, Ingólfsdóttir A, Legay A, Mardare R, eds.
Models, Algorithms, Logics and Tools. Vol 10460. Theoretical Computer Science
and General Issues. Springer; 2017:367-381. doi:10.1007/978-3-319-63121-9_18'
apa: Chatterjee, K., Doyen, L., & Henzinger, T. A. (2017). The cost of exactness
in quantitative reachability. In L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay,
& R. Mardare (Eds.), Models, Algorithms, Logics and Tools (Vol. 10460,
pp. 367–381). Springer. https://doi.org/10.1007/978-3-319-63121-9_18
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “The Cost
of Exactness in Quantitative Reachability.” In Models, Algorithms, Logics and
Tools, edited by Luca Aceto, Giorgio Bacci, Anna Ingólfsdóttir, Axel Legay,
and Radu Mardare, 10460:367–81. Theoretical Computer Science and General Issues.
Springer, 2017. https://doi.org/10.1007/978-3-319-63121-9_18.
ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, “The cost of exactness in quantitative
reachability,” in Models, Algorithms, Logics and Tools, vol. 10460, L.
Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, and R. Mardare, Eds. Springer, 2017,
pp. 367–381.
ista: 'Chatterjee K, Doyen L, Henzinger TA. 2017.The cost of exactness in quantitative
reachability. In: Models, Algorithms, Logics and Tools. LNCS, vol. 10460, 367–381.'
mla: Chatterjee, Krishnendu, et al. “The Cost of Exactness in Quantitative Reachability.”
Models, Algorithms, Logics and Tools, edited by Luca Aceto et al., vol.
10460, Springer, 2017, pp. 367–81, doi:10.1007/978-3-319-63121-9_18.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir,
A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017,
pp. 367–381.
date_created: 2018-12-11T11:47:34Z
date_published: 2017-07-25T00:00:00Z
date_updated: 2025-04-15T06:26:15Z
day: '25'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-319-63121-9_18
ec_funded: 1
editor:
- first_name: Luca
full_name: Aceto, Luca
last_name: Aceto
- first_name: Giorgio
full_name: Bacci, Giorgio
last_name: Bacci
- first_name: Anna
full_name: Ingólfsdóttir, Anna
last_name: Ingólfsdóttir
- first_name: Axel
full_name: Legay, Axel
last_name: Legay
- first_name: Radu
full_name: Mardare, Radu
last_name: Mardare
file:
- access_level: open_access
checksum: b2402766ec02c79801aac634bd8f9f6c
content_type: application/pdf
creator: dernst
date_created: 2019-11-19T08:06:50Z
date_updated: 2020-07-14T12:47:25Z
file_id: '7048'
file_name: 2017_ModelsAlgorithms_Chatterjee.pdf
file_size: 192826
relation: main_file
file_date_updated: 2020-07-14T12:47:25Z
has_accepted_license: '1'
intvolume: ' 10460'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 367 - 381
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: Models, Algorithms, Logics and Tools
publication_identifier:
isbn:
- 978-3-319-63120-2
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '7170'
quality_controlled: '1'
scopus_import: '1'
series_title: Theoretical Computer Science and General Issues
status: public
title: The cost of exactness in quantitative reachability
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10460
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
article_processing_charge: No
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
corr_author: '1'
date_created: 2018-12-11T11:47:36Z
date_published: 2017-03-31T00:00:00Z
date_updated: 2026-04-08T07:47:13Z
day: '31'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-662-54577-5_34
external_id:
isi:
- '000440734900034'
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'
isi: 1
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: Formal methods for the design and analysis of complex systems
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10205
year: '2017'
...
---
_id: '633'
abstract:
- lang: eng
text: A Rapidly-exploring Random Tree (RRT) is an algorithm which can search a non-convex
region of space by incrementally building a space-filling tree. The tree is constructed
from random points drawn from system’s state space and is biased to grow towards
large unexplored areas in the system. RRT can provide better coverage of a system’s
possible behaviors compared with random simulations, but is more lightweight than
full reachability analysis. In this paper, we explore some of the design decisions
encountered while implementing a hybrid extension of the RRT algorithm, which
have not been elaborated on before. In particular, we focus on handling non-determinism,
which arises due to discrete transitions. We introduce the notion of important
points to account for this phenomena. We showcase our ideas using heater and navigation
benchmarks.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Stanley
full_name: Bak, Stanley
last_name: Bak
- 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: Aviral
full_name: Kumar, Aviral
last_name: Kumar
citation:
ama: 'Bak S, Bogomolov S, Henzinger TA, Kumar A. Challenges and tool implementation
of hybrid rapidly exploring random trees. In: Abate A, Bodo S, eds. Vol 10381.
Springer; 2017:83-89. doi:10.1007/978-3-319-63501-9_6'
apa: 'Bak, S., Bogomolov, S., Henzinger, T. A., & Kumar, A. (2017). Challenges
and tool implementation of hybrid rapidly exploring random trees. In A. Abate
& S. Bodo (Eds.) (Vol. 10381, pp. 83–89). Presented at the NSV: Numerical
Software Verification, Heidelberg, Germany: Springer. https://doi.org/10.1007/978-3-319-63501-9_6'
chicago: Bak, Stanley, Sergiy Bogomolov, Thomas A Henzinger, and Aviral Kumar. “Challenges
and Tool Implementation of Hybrid Rapidly Exploring Random Trees.” edited by Alessandro
Abate and Sylvie Bodo, 10381:83–89. Springer, 2017. https://doi.org/10.1007/978-3-319-63501-9_6.
ieee: 'S. Bak, S. Bogomolov, T. A. Henzinger, and A. Kumar, “Challenges and tool
implementation of hybrid rapidly exploring random trees,” presented at the NSV:
Numerical Software Verification, Heidelberg, Germany, 2017, vol. 10381, pp. 83–89.'
ista: 'Bak S, Bogomolov S, Henzinger TA, Kumar A. 2017. Challenges and tool implementation
of hybrid rapidly exploring random trees. NSV: Numerical Software Verification,
LNCS, vol. 10381, 83–89.'
mla: Bak, Stanley, et al. Challenges and Tool Implementation of Hybrid Rapidly
Exploring Random Trees. Edited by Alessandro Abate and Sylvie Bodo, vol. 10381,
Springer, 2017, pp. 83–89, doi:10.1007/978-3-319-63501-9_6.
short: S. Bak, S. Bogomolov, T.A. Henzinger, A. Kumar, in:, A. Abate, S. Bodo (Eds.),
Springer, 2017, pp. 83–89.
conference:
end_date: 2017-07-23
location: Heidelberg, Germany
name: 'NSV: Numerical Software Verification'
start_date: 2017-07-22
date_created: 2018-12-11T11:47:37Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-09-11T07:25:57Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-319-63501-9_6
editor:
- first_name: Alessandro
full_name: Abate, Alessandro
last_name: Abate
- first_name: Sylvie
full_name: Bodo, Sylvie
last_name: Bodo
external_id:
isi:
- '000440724800006'
intvolume: ' 10381'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 83 - 89
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: Formal methods for the design and analysis of complex systems
publication_identifier:
isbn:
- 978-331963500-2
publication_status: published
publisher: Springer
publist_id: '7159'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Challenges and tool implementation of hybrid rapidly exploring random trees
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10381
year: '2017'
...
---
_id: '636'
abstract:
- lang: eng
text: Signal regular expressions can specify sequential properties of real-valued
signals based on threshold conditions, regular operations, and duration constraints.
In this paper we endow them with a quantitative semantics which indicates how
robustly a signal matches or does not match a given expression. First, we show
that this semantics is a safe approximation of a distance between the signal and
the language defined by the expression. Then, we consider the robust matching
problem, that is, computing the quantitative semantics of every segment of a given
signal relative to an expression. We present an algorithm that solves this problem
for piecewise-constant and piecewise-linear signals and show that for such signals
the robustness map is a piecewise-linear function. The availability of an indicator
describing how robustly a signal segment matches some regular pattern provides
a general framework for quantitative monitoring of cyber-physical systems.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alexey
full_name: Bakhirkin, Alexey
last_name: Bakhirkin
- first_name: Thomas
full_name: Ferrere, Thomas
id: 40960E6E-F248-11E8-B48F-1D18A9856A87
last_name: Ferrere
orcid: 0000-0001-5199-3143
- first_name: Oded
full_name: Maler, Oded
last_name: Maler
- first_name: Dogan
full_name: Ulus, Dogan
last_name: Ulus
citation:
ama: 'Bakhirkin A, Ferrere T, Maler O, Ulus D. On the quantitative semantics of
regular expressions over real-valued signals. In: Abate A, Geeraerts G, eds. Vol
10419. Springer; 2017:189-206. doi:10.1007/978-3-319-65765-3_11'
apa: 'Bakhirkin, A., Ferrere, T., Maler, O., & Ulus, D. (2017). On the quantitative
semantics of regular expressions over real-valued signals. In A. Abate & G.
Geeraerts (Eds.) (Vol. 10419, pp. 189–206). Presented at the FORMATS: Formal Modelling
and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_11'
chicago: Bakhirkin, Alexey, Thomas Ferrere, Oded Maler, and Dogan Ulus. “On the
Quantitative Semantics of Regular Expressions over Real-Valued Signals.” edited
by Alessandro Abate and Gilles Geeraerts, 10419:189–206. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_11.
ieee: 'A. Bakhirkin, T. Ferrere, O. Maler, and D. Ulus, “On the quantitative semantics
of regular expressions over real-valued signals,” presented at the FORMATS: Formal
Modelling and Analysis of Timed Systems, Berlin, Germany, 2017, vol. 10419, pp.
189–206.'
ista: 'Bakhirkin A, Ferrere T, Maler O, Ulus D. 2017. On the quantitative semantics
of regular expressions over real-valued signals. FORMATS: Formal Modelling and
Analysis of Timed Systems, LNCS, vol. 10419, 189–206.'
mla: Bakhirkin, Alexey, et al. On the Quantitative Semantics of Regular Expressions
over Real-Valued Signals. Edited by Alessandro Abate and Gilles Geeraerts,
vol. 10419, Springer, 2017, pp. 189–206, doi:10.1007/978-3-319-65765-3_11.
short: A. Bakhirkin, T. Ferrere, O. Maler, D. Ulus, in:, A. Abate, G. Geeraerts
(Eds.), Springer, 2017, pp. 189–206.
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:38Z
date_published: 2017-08-03T00:00:00Z
date_updated: 2025-09-11T07:24:11Z
day: '03'
department:
- _id: ToHe
doi: 10.1007/978-3-319-65765-3_11
editor:
- first_name: Alessandro
full_name: Abate, Alessandro
last_name: Abate
- first_name: Gilles
full_name: Geeraerts, Gilles
last_name: Geeraerts
external_id:
isi:
- '000611678300011'
intvolume: ' 10419'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.archives-ouvertes.fr/hal-01552132
month: '08'
oa: 1
oa_version: Submitted Version
page: 189 - 206
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: Formal methods for the design and analysis of complex systems
publication_identifier:
isbn:
- 978-331965764-6
publication_status: published
publisher: Springer
publist_id: '7152'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the quantitative semantics of regular expressions over real-valued signals
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10419
year: '2017'
...
---
_id: '638'
abstract:
- lang: eng
text: "This book constitutes the refereed proceedings of the 9th InternationalWorkshop
on Numerical Software Verification, NSV 2016, held in Toronto, ON, Canada in July
2011 - colocated with CAV 2016, the 28th International Conference on Computer
Aided Verification.\r\nThe NSV workshop is dedicated to the development of logical
and mathematical techniques for the reasoning about programmability and reliability."
alternative_title:
- LNCS
article_processing_charge: No
citation:
ama: Bogomolov S, Martel M, Prabhakar P, eds. Numerical Software Verification.
Vol 10152. Springer; 2017. doi:10.1007/978-3-319-54292-8
apa: 'Bogomolov, S., Martel, M., & Prabhakar, P. (Eds.). (2017). Numerical
Software Verification (Vol. 10152). Presented at the NSV: Numerical Software
Verification, Toronto, ON, Canada: Springer. https://doi.org/10.1007/978-3-319-54292-8'
chicago: Bogomolov, Sergiy, Matthieu Martel, and Pavithra Prabhakar, eds. Numerical
Software Verification. Vol. 10152. Springer, 2017. https://doi.org/10.1007/978-3-319-54292-8.
ieee: S. Bogomolov, M. Martel, and P. Prabhakar, Eds., Numerical Software Verification,
vol. 10152. Springer, 2017.
ista: Bogomolov S, Martel M, Prabhakar P eds. 2017. Numerical Software Verification,
Springer,p.
mla: Bogomolov, Sergiy, et al., editors. Numerical Software Verification.
Vol. 10152, Springer, 2017, doi:10.1007/978-3-319-54292-8.
short: S. Bogomolov, M. Martel, P. Prabhakar, eds., Numerical Software Verification,
Springer, 2017.
conference:
end_date: 2016-07-18
location: Toronto, ON, Canada
name: 'NSV: Numerical Software Verification'
start_date: 2016-07-17
date_created: 2018-12-11T11:47:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2026-03-31T12:28:01Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-319-54292-8
editor:
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Matthieu
full_name: Martel, Matthieu
last_name: Martel
- first_name: Pavithra
full_name: Prabhakar, Pavithra
last_name: Prabhakar
intvolume: ' 10152'
language:
- iso: eng
month: '01'
oa_version: None
publication_identifier:
eisbn:
- 978-3-319-54292-8
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '7150'
quality_controlled: '1'
status: public
title: Numerical Software Verification
type: conference_editor
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10152
year: '2017'
...
---
_id: '1003'
abstract:
- lang: eng
text: Network games (NGs) are played on directed graphs and are extensively used
in network design and analysis. Search problems for NGs include finding special
strategy profiles such as a Nash equilibrium and a globally optimal solution.
The networks modeled by NGs may be huge. In formal verification, abstraction has
proven to be an extremely effective technique for reasoning about systems with
big and even infinite state spaces. We describe an abstraction-refinement methodology
for reasoning about NGs. Our methodology is based on an abstraction function that
maps the state space of an NG to a much smaller state space. We search for a global
optimum and a Nash equilibrium by reasoning on an under- and an overapproximation
defined on top of this smaller state space. When the approximations are too coarse
to find such profiles, we refine the abstraction function. Our experimental results
demonstrate the efficiency of the methodology.
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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: 'Avni G, Guha S, Kupferman O. An abstraction-refinement methodology for reasoning
about network games. In: AAAI Press; 2017:70-76. doi:10.24963/ijcai.2017/11'
apa: 'Avni, G., Guha, S., & Kupferman, O. (2017). An abstraction-refinement
methodology for reasoning about network games (pp. 70–76). Presented at the IJCAI:
International Joint Conference on Artificial Intelligence , Melbourne, Australia:
AAAI Press. https://doi.org/10.24963/ijcai.2017/11'
chicago: Avni, Guy, Shibashis Guha, and Orna Kupferman. “An Abstraction-Refinement
Methodology for Reasoning about Network Games,” 70–76. AAAI Press, 2017. https://doi.org/10.24963/ijcai.2017/11.
ieee: 'G. Avni, S. Guha, and O. Kupferman, “An abstraction-refinement methodology
for reasoning about network games,” presented at the IJCAI: International Joint
Conference on Artificial Intelligence , Melbourne, Australia, 2017, pp. 70–76.'
ista: 'Avni G, Guha S, Kupferman O. 2017. An abstraction-refinement methodology
for reasoning about network games. IJCAI: International Joint Conference on Artificial
Intelligence , 70–76.'
mla: Avni, Guy, et al. An Abstraction-Refinement Methodology for Reasoning about
Network Games. AAAI Press, 2017, pp. 70–76, doi:10.24963/ijcai.2017/11.
short: G. Avni, S. Guha, O. Kupferman, in:, AAAI Press, 2017, pp. 70–76.
conference:
end_date: 2017-08-25
location: Melbourne, Australia
name: 'IJCAI: International Joint Conference on Artificial Intelligence '
start_date: 2017-08-19
date_created: 2018-12-11T11:49:38Z
date_published: 2017-05-30T00:00:00Z
date_updated: 2025-07-10T11:49:38Z
day: '30'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.24963/ijcai.2017/11
external_id:
isi:
- '000764137500011'
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:58Z
date_updated: 2018-12-12T10:16:58Z
file_id: '5249'
file_name: IST-2017-818-v1+1_allIJCAI_CR.pdf
file_size: 365172
relation: main_file
file_date_updated: 2018-12-12T10:16:58Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 70 - 76
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: Formal methods for the design and analysis of complex systems
publication_identifier:
issn:
- 1045-0823
publication_status: published
publisher: AAAI Press
publist_id: '6395'
pubrep_id: '818'
quality_controlled: '1'
related_material:
record:
- id: '6006'
relation: later_version
status: public
scopus_import: '1'
status: public
title: An abstraction-refinement methodology for reasoning about network games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '1011'
abstract:
- lang: eng
text: Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly
equivalent, are standard models for interprocedural analysis. Yet RSMs are more
convenient as they (a) explicitly model function calls and returns, and (b) specify
many natural parameters for algorithmic analysis, e.g., the number of entries
and exits. We consider a general framework where RSM transitions are labeled from
a semiring and path properties are algebraic with semiring operations, which can
model, e.g., interprocedural reachability and dataflow analysis problems. Our
main contributions are new algorithms for several fundamental problems. As compared
to a direct translation of RSMs to PDSs and the best-known existing bounds of
PDSs, our analysis algorithm improves the complexity for finite-height semirings
(that subsumes reachability and standard dataflow properties). We further consider
the problem of extracting distance values from the representation structures computed
by our algorithm, and give efficient algorithms that distinguish the complexity
of a one-time preprocessing from the complexity of each individual query. Another
advantage of our algorithm is that our improvements carry over to the concurrent
setting, where we improve the bestknown complexity for the context-bounded analysis
of concurrent RSMs. Finally, we provide a prototype implementation that gives
a significant speed-up on several benchmarks from the SLAM/SDV project.
alternative_title:
- LNCS
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: Bernhard
full_name: Kragl, Bernhard
id: 320FC952-F248-11E8-B48F-1D18A9856A87
last_name: Kragl
orcid: 0000-0001-7745-9117
- first_name: Samarth
full_name: Mishra, Samarth
last_name: Mishra
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. Faster algorithms for weighted
recursive state machines. In: Yang H, ed. Vol 10201. Springer; 2017:287-313. doi:10.1007/978-3-662-54434-1_11'
apa: 'Chatterjee, K., Kragl, B., Mishra, S., & Pavlogiannis, A. (2017). Faster
algorithms for weighted recursive state machines. In H. Yang (Ed.) (Vol. 10201,
pp. 287–313). Presented at the ESOP: European Symposium on Programming, Uppsala,
Sweden: Springer. https://doi.org/10.1007/978-3-662-54434-1_11'
chicago: Chatterjee, Krishnendu, Bernhard Kragl, Samarth Mishra, and Andreas Pavlogiannis.
“Faster Algorithms for Weighted Recursive State Machines.” edited by Hongseok
Yang, 10201:287–313. Springer, 2017. https://doi.org/10.1007/978-3-662-54434-1_11.
ieee: 'K. Chatterjee, B. Kragl, S. Mishra, and A. Pavlogiannis, “Faster algorithms
for weighted recursive state machines,” presented at the ESOP: European Symposium
on Programming, Uppsala, Sweden, 2017, vol. 10201, pp. 287–313.'
ista: 'Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. 2017. Faster algorithms
for weighted recursive state machines. ESOP: European Symposium on Programming,
LNCS, vol. 10201, 287–313.'
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Weighted Recursive
State Machines. Edited by Hongseok Yang, vol. 10201, Springer, 2017, pp. 287–313,
doi:10.1007/978-3-662-54434-1_11.
short: K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.),
Springer, 2017, pp. 287–313.
conference:
end_date: 2017-04-29
location: Uppsala, Sweden
name: 'ESOP: European Symposium on Programming'
start_date: 2017-04-22
date_created: 2018-12-11T11:49:41Z
date_published: 2017-03-19T00:00:00Z
date_updated: 2025-06-04T08:09:18Z
day: '19'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-662-54434-1_11
ec_funded: 1
editor:
- first_name: Hongseok
full_name: Yang, Hongseok
last_name: Yang
external_id:
arxiv:
- '1701.04914'
isi:
- '000681702400011'
intvolume: ' 10201'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1701.04914
month: '03'
oa: 1
oa_version: Submitted Version
page: 287 - 313
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _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: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_identifier:
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '6384'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for weighted recursive state machines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10201
year: '2017'
...
---
_id: '10418'
abstract:
- lang: eng
text: We present a new proof rule for proving almost-sure termination of probabilistic
programs, including those that contain demonic non-determinism. An important question
for a probabilistic program is whether the probability mass of all its diverging
runs is zero, that is that it terminates "almost surely". Proving that can be
hard, and this paper presents a new method for doing so. It applies directly to
the program's source code, even if the program contains demonic choice. Like others,
we use variant functions (a.k.a. "super-martingales") that are real-valued and
decrease randomly on each loop iteration; but our key innovation is that the amount
as well as the probability of the decrease are parametric. We prove the soundness
of the new rule, indicate where its applicability goes beyond existing rules,
and explain its connection to classical results on denumerable (non-demonic) Markov
chains.
acknowledgement: "McIver and Morgan are grateful to David Basin and the Information
Security Group at ETH Zürich for hosting a six-month stay in Switzerland, during
part of which this work began. And thanks particularly to Andreas Lochbihler, who
shared with us the probabilistic termination problem that led to it. They acknowledge
the support of ARC grant DP140101119. Part of this work was carried out during the
Workshop on Probabilistic Programming Semantics\r\nat McGill University’s Bellairs
Research Institute on Barbados organised by Alexandra Silva and\r\nPrakash Panangaden.
Kaminski and Katoen are grateful to Sebastian Junges for spotting a flaw in §5.4."
article_number: '33'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Annabelle
full_name: Mciver, Annabelle
last_name: Mciver
- first_name: Carroll
full_name: Morgan, Carroll
last_name: Morgan
- first_name: Benjamin Lucien
full_name: Kaminski, Benjamin Lucien
last_name: Kaminski
- first_name: Joost P
full_name: Katoen, Joost P
id: 4524F760-F248-11E8-B48F-1D18A9856A87
last_name: Katoen
orcid: 0000-0002-6143-1926
citation:
ama: Mciver A, Morgan C, Kaminski BL, Katoen JP. A new proof rule for almost-sure
termination. Proceedings of the ACM on Programming Languages. 2017;2(POPL).
doi:10.1145/3158121
apa: 'Mciver, A., Morgan, C., Kaminski, B. L., & Katoen, J. P. (2017). A new
proof rule for almost-sure termination. Proceedings of the ACM on Programming
Languages. Los Angeles, CA, United States: Association for Computing Machinery.
https://doi.org/10.1145/3158121'
chicago: Mciver, Annabelle, Carroll Morgan, Benjamin Lucien Kaminski, and Joost
P Katoen. “A New Proof Rule for Almost-Sure Termination.” Proceedings of the
ACM on Programming Languages. Association for Computing Machinery, 2017. https://doi.org/10.1145/3158121.
ieee: A. Mciver, C. Morgan, B. L. Kaminski, and J. P. Katoen, “A new proof rule
for almost-sure termination,” Proceedings of the ACM on Programming Languages,
vol. 2, no. POPL. Association for Computing Machinery, 2017.
ista: Mciver A, Morgan C, Kaminski BL, Katoen JP. 2017. A new proof rule for almost-sure
termination. Proceedings of the ACM on Programming Languages. 2(POPL), 33.
mla: Mciver, Annabelle, et al. “A New Proof Rule for Almost-Sure Termination.” Proceedings
of the ACM on Programming Languages, vol. 2, no. POPL, 33, Association for
Computing Machinery, 2017, doi:10.1145/3158121.
short: A. Mciver, C. Morgan, B.L. Kaminski, J.P. Katoen, Proceedings of the ACM
on Programming Languages 2 (2017).
conference:
end_date: 2018-01-13
location: Los Angeles, CA, United States
name: 'POPL: Programming Languages'
start_date: 2018-01-07
corr_author: '1'
date_created: 2021-12-05T23:01:49Z
date_published: 2017-12-07T00:00:00Z
date_updated: 2026-06-18T08:40:04Z
day: '07'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1145/3158121
external_id:
arxiv:
- '1711.03588'
intvolume: ' 2'
issue: POPL
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.1145/3158121
month: '12'
oa: 1
oa_version: Published Version
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new proof rule for almost-sure termination
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2
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: '941'
abstract:
- lang: eng
text: 'Recently there has been a proliferation of automated program repair (APR)
techniques, targeting various programming languages. Such techniques can be generally
classified into two families: syntactic- and semantics-based. Semantics-based
APR, on which we focus, typically uses symbolic execution to infer semantic constraints
and then program synthesis to construct repairs conforming to them. While syntactic-based
APR techniques have been shown successful on bugs in real-world programs written
in both C and Java, semantics-based APR techniques mostly target C programs. This
leaves empirical comparisons of the APR families not fully explored, and developers
without a Java-based semantics APR technique. We present JFix, a semantics-based
APR framework that targets Java, and an associated Eclipse plugin. JFix is implemented
atop Symbolic PathFinder, a well-known symbolic execution engine for Java programs.
It extends one particular APR technique (Angelix), and is designed to be sufficiently
generic to support a variety of such techniques. We demonstrate that semantics-based
APR can indeed efficiently and effectively repair a variety of classes of bugs
in large real-world Java programs. This supports our claim that the framework
can both support developers seeking semantics-based repair of bugs in Java programs,
as well as enable larger scale empirical studies comparing syntactic- and semantics-based
APR targeting Java. The demonstration of our tool is available via the project
website at: https://xuanbachle.github.io/semanticsrepair/ '
acknowledgement: We thank Vu Le (Microsoft Research, Redmond), and anonymous reviewers
for their comments. Duc-Hiep Chu was supported in part by the Austrian Science Fund
(FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award).
article_processing_charge: No
author:
- first_name: Xuan
full_name: Le, Xuan
last_name: Le
- first_name: Duc Hiep
full_name: Chu, Duc Hiep
id: 3598E630-F248-11E8-B48F-1D18A9856A87
last_name: Chu
- first_name: David
full_name: Lo, David
last_name: Lo
- first_name: Claire
full_name: Le Goues, Claire
last_name: Le Goues
- first_name: Willem
full_name: Visser, Willem
last_name: Visser
citation:
ama: 'Le X, Chu DH, Lo D, Le Goues C, Visser W. JFIX: Semantics-based repair of
Java programs via symbolic PathFinder. In: Proceedings of the 26th ACM SIGSOFT
International Symposium on Software Testing and Analysis. ACM; 2017:376-379.
doi:10.1145/3092703.3098225'
apa: 'Le, X., Chu, D. H., Lo, D., Le Goues, C., & Visser, W. (2017). JFIX: Semantics-based
repair of Java programs via symbolic PathFinder. In Proceedings of the 26th
ACM SIGSOFT International Symposium on Software Testing and Analysis (pp.
376–379). Santa Barbara, CA, United States: ACM. https://doi.org/10.1145/3092703.3098225'
chicago: 'Le, Xuan, Duc Hiep Chu, David Lo, Claire Le Goues, and Willem Visser.
“JFIX: Semantics-Based Repair of Java Programs via Symbolic PathFinder.” In Proceedings
of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis,
376–79. ACM, 2017. https://doi.org/10.1145/3092703.3098225.'
ieee: 'X. Le, D. H. Chu, D. Lo, C. Le Goues, and W. Visser, “JFIX: Semantics-based
repair of Java programs via symbolic PathFinder,” in Proceedings of the 26th
ACM SIGSOFT International Symposium on Software Testing and Analysis, Santa
Barbara, CA, United States, 2017, pp. 376–379.'
ista: 'Le X, Chu DH, Lo D, Le Goues C, Visser W. 2017. JFIX: Semantics-based repair
of Java programs via symbolic PathFinder. Proceedings of the 26th ACM SIGSOFT
International Symposium on Software Testing and Analysis. ISSTA: International
Symposium on Software Testing and Analysis, 376–379.'
mla: 'Le, Xuan, et al. “JFIX: Semantics-Based Repair of Java Programs via Symbolic
PathFinder.” Proceedings of the 26th ACM SIGSOFT International Symposium on
Software Testing and Analysis, ACM, 2017, pp. 376–79, doi:10.1145/3092703.3098225.'
short: X. Le, D.H. Chu, D. Lo, C. Le Goues, W. Visser, in:, Proceedings of the 26th
ACM SIGSOFT International Symposium on Software Testing and Analysis, ACM, 2017,
pp. 376–379.
conference:
end_date: 2017-07-14
location: Santa Barbara, CA, United States
name: 'ISSTA: International Symposium on Software Testing and Analysis'
start_date: 2017-07-10
corr_author: '1'
date_created: 2018-12-11T11:49:19Z
date_published: 2017-07-10T00:00:00Z
date_updated: 2026-06-18T19:51:19Z
day: '10'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1145/3092703.3098225
external_id:
isi:
- '000462903600038'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://core.ac.uk/download/pdf/111759662.pdf
month: '07'
oa: 1
oa_version: Published Version
page: '376 - 379 '
project:
- _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 26th ACM SIGSOFT International Symposium on Software
Testing and Analysis
publication_status: published
publisher: ACM
publist_id: '6478'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'JFIX: Semantics-based repair of Java programs via symbolic PathFinder'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '942'
abstract:
- lang: eng
text: 'A notable class of techniques for automatic program repair is known as semantics-based.
Such techniques, e.g., Angelix, infer semantic specifications via symbolic execution,
and then use program synthesis to construct new code that satisfies those inferred
specifications. However, the obtained specifications are naturally incomplete,
leaving the synthesis engine with a difficult task of synthesizing a general solution
from a sparse space of many possible solutions that are consistent with the provided
specifications but that do not necessarily generalize. We present S3, a new repair
synthesis engine that leverages programming-by-examples methodology to synthesize
high-quality bug repairs. The novelty in S3 that allows it to tackle the sparse
search space to create more general repairs is three-fold: (1) A systematic way
to customize and constrain the syntactic search space via a domain-specific language,
(2) An efficient enumeration-based search strategy over the constrained search
space, and (3) A number of ranking features based on measures of the syntactic
and semantic distances between candidate solutions and the original buggy program.
We compare S3’s repair effectiveness with state-of-the-art synthesis engines Angelix,
Enumerative, and CVC4. S3 can successfully and correctly fix at least three times
more bugs than the best baseline on datasets of 52 bugs in small programs, and
100 bugs in real-world large programs. '
article_processing_charge: No
author:
- first_name: Xuan
full_name: Le, Xuan
last_name: Le
- first_name: Duc Hiep
full_name: Chu, Duc Hiep
id: 3598E630-F248-11E8-B48F-1D18A9856A87
last_name: Chu
- first_name: David
full_name: Lo, David
last_name: Lo
- first_name: Claire
full_name: Le Goues, Claire
last_name: Le Goues
- first_name: Willem
full_name: Visser, Willem
last_name: Visser
citation:
ama: 'Le X, Chu DH, Lo D, Le Goues C, Visser W. S3: Syntax- and semantic-guided
repair synthesis via programming by examples. In: Vol F130154. ACM; 2017:593-604.
doi:10.1145/3106237.3106309'
apa: 'Le, X., Chu, D. H., Lo, D., Le Goues, C., & Visser, W. (2017). S3: Syntax-
and semantic-guided repair synthesis via programming by examples (Vol. F130154,
pp. 593–604). Presented at the FSE: Foundations of Software Engineering, Paderborn,
Germany: ACM. https://doi.org/10.1145/3106237.3106309'
chicago: 'Le, Xuan, Duc Hiep Chu, David Lo, Claire Le Goues, and Willem Visser.
“S3: Syntax- and Semantic-Guided Repair Synthesis via Programming by Examples,”
F130154:593–604. ACM, 2017. https://doi.org/10.1145/3106237.3106309.'
ieee: 'X. Le, D. H. Chu, D. Lo, C. Le Goues, and W. Visser, “S3: Syntax- and semantic-guided
repair synthesis via programming by examples,” presented at the FSE: Foundations
of Software Engineering, Paderborn, Germany, 2017, vol. F130154, pp. 593–604.'
ista: 'Le X, Chu DH, Lo D, Le Goues C, Visser W. 2017. S3: Syntax- and semantic-guided
repair synthesis via programming by examples. FSE: Foundations of Software Engineering
vol. F130154, 593–604.'
mla: 'Le, Xuan, et al. S3: Syntax- and Semantic-Guided Repair Synthesis via Programming
by Examples. Vol. F130154, ACM, 2017, pp. 593–604, doi:10.1145/3106237.3106309.'
short: X. Le, D.H. Chu, D. Lo, C. Le Goues, W. Visser, in:, ACM, 2017, pp. 593–604.
conference:
end_date: 2017-09-08
location: Paderborn, Germany
name: 'FSE: Foundations of Software Engineering'
start_date: 2017-09-04
date_created: 2018-12-11T11:49:19Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2025-04-15T06:25:57Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/3106237.3106309
external_id:
isi:
- '000414279300055'
isi: 1
language:
- iso: eng
month: '09'
oa_version: None
page: 593 - 604
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: Formal methods for the design and analysis of complex systems
publication_identifier:
isbn:
- 978-145035105-8
publication_status: published
publisher: ACM
publist_id: '6477'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'S3: Syntax- and semantic-guided repair synthesis via programming by examples'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: F130154
year: '2017'
...
---
_id: '950'
abstract:
- lang: eng
text: "Two-player games on graphs are widely studied in formal methods as they model
the interaction between a system and its environment. The game is played by moving
a token throughout a graph to produce an infinite path. There are several common
modes to determine how the players move the token through the graph; e.g., in
turn-based games the players alternate turns in moving the token. We study the
bidding mode of moving the token, which, to the best of our knowledge, has never
been studied in infinite-duration games. Both players have separate budgets, which
sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously,
and a bid is legal if it does not exceed the available budget. The winner of the
bidding pays his bid to the other player and moves the token. For reachability
objectives, repeated bidding games have been studied and are called Richman games.
There, a central question is the existence and computation of threshold budgets;
namely, a value t\\in [0,1] such that if\\PO's budget exceeds $t$, he can win
the game, and if\\PT's budget exceeds 1-t, he can win the game. We focus on parity
games and mean-payoff games. We show the existence of threshold budgets in these
games, and reduce the problem of finding them to Richman games. We also determine
the strategy-complexity of an optimal strategy. Our most interesting result shows
that memoryless strategies suffice for mean-payoff bidding games. \r\n"
alternative_title:
- LIPIcs
article_number: '17'
arxiv: 1
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: Ventsislav K
full_name: Chonev, Ventsislav K
id: 36CBE2E6-F248-11E8-B48F-1D18A9856A87
last_name: Chonev
citation:
ama: 'Avni G, Henzinger TA, Chonev VK. Infinite-duration bidding games. In: Vol
85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.21'
apa: 'Avni, G., Henzinger, T. A., & Chonev, V. K. (2017). Infinite-duration
bidding games (Vol. 85). Presented at the CONCUR: Concurrency Theory, Berlin,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.21'
chicago: Avni, Guy, Thomas A Henzinger, and Ventsislav K Chonev. “Infinite-Duration
Bidding Games,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
https://doi.org/10.4230/LIPIcs.CONCUR.2017.21.
ieee: 'G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,”
presented at the CONCUR: Concurrency Theory, Berlin, Germany, 2017, vol. 85.'
ista: 'Avni G, Henzinger TA, Chonev VK. 2017. Infinite-duration bidding games. CONCUR:
Concurrency Theory, LIPIcs, vol. 85, 17.'
mla: Avni, Guy, et al. Infinite-Duration Bidding Games. Vol. 85, 17, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.21.
short: G. Avni, T.A. Henzinger, V.K. Chonev, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-09-07
location: Berlin, Germany
name: 'CONCUR: Concurrency Theory'
start_date: 2017-09-05
date_created: 2018-12-11T11:49:22Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2025-07-10T11:53:48Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2017.21
external_id:
arxiv:
- '1705.01433'
file:
- access_level: open_access
checksum: 6d5cccf755207b91ccbef95d8275b013
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:00Z
date_updated: 2020-07-14T12:48:16Z
file_id: '5318'
file_name: IST-2017-844-v1+1_concur-cr.pdf
file_size: 335170
relation: main_file
file_date_updated: 2020-07-14T12:48:16Z
has_accepted_license: '1'
intvolume: ' 85'
language:
- iso: eng
month: '09'
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: 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:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6466'
pubrep_id: '844'
quality_controlled: '1'
related_material:
record:
- id: '6752'
relation: later_version
status: public
scopus_import: 1
status: public
title: Infinite-duration bidding games
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2017'
...