---
_id: '1392'
abstract:
- lang: eng
text: Fault-tolerant distributed algorithms play an important role in ensuring the
reliability of many software applications. In this paper we consider distributed
algorithms whose computations are organized in rounds. To verify the correctness
of such algorithms, we reason about (i) properties (such as invariants) of the
state, (ii) the transitions controlled by the algorithm, and (iii) the communication
graph. We introduce a logic that addresses these points, and contains set comprehensions
with cardinality constraints, function symbols to describe the local states of
each process, and a limited form of quantifier alternation to express the verification
conditions. We show its use in automating the verification of consensus algorithms.
In particular, we give a semi-decision procedure for the unsatisfiability problem
of the logic and identify a decidable fragment. We successfully applied our framework
to verify the correctness of a variety of consensus algorithms tolerant to both
benign faults (message loss, process crashes) and value faults (message corruption).
acknowledgement: Supported by the Vienna Science and Technology Fund (WWTF) through
grant PROSEED.
alternative_title:
- LNCS
author:
- first_name: Cezara
full_name: Dragoi, Cezara
id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87
last_name: Dragoi
- 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: Helmut
full_name: Veith, Helmut
last_name: Veith
- first_name: Josef
full_name: Widder, Josef
last_name: Widder
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: 'Dragoi C, Henzinger TA, Veith H, Widder J, Zufferey D. A logic-based framework
for verifying consensus algorithms. In: Vol 8318. Springer; 2014:161-181. doi:10.1007/978-3-642-54013-4_10'
apa: 'Dragoi, C., Henzinger, T. A., Veith, H., Widder, J., & Zufferey, D. (2014).
A logic-based framework for verifying consensus algorithms (Vol. 8318, pp. 161–181).
Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation,
San Diego, USA: Springer. https://doi.org/10.1007/978-3-642-54013-4_10'
chicago: Dragoi, Cezara, Thomas A Henzinger, Helmut Veith, Josef Widder, and Damien
Zufferey. “A Logic-Based Framework for Verifying Consensus Algorithms,” 8318:161–81.
Springer, 2014. https://doi.org/10.1007/978-3-642-54013-4_10.
ieee: 'C. Dragoi, T. A. Henzinger, H. Veith, J. Widder, and D. Zufferey, “A logic-based
framework for verifying consensus algorithms,” presented at the VMCAI: Verification,
Model Checking and Abstract Interpretation, San Diego, USA, 2014, vol. 8318, pp.
161–181.'
ista: 'Dragoi C, Henzinger TA, Veith H, Widder J, Zufferey D. 2014. A logic-based
framework for verifying consensus algorithms. VMCAI: Verification, Model Checking
and Abstract Interpretation, LNCS, vol. 8318, 161–181.'
mla: Dragoi, Cezara, et al. A Logic-Based Framework for Verifying Consensus Algorithms.
Vol. 8318, Springer, 2014, pp. 161–81, doi:10.1007/978-3-642-54013-4_10.
short: C. Dragoi, T.A. Henzinger, H. Veith, J. Widder, D. Zufferey, in:, Springer,
2014, pp. 161–181.
conference:
end_date: 2014-01-21
location: San Diego, USA
name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
start_date: 2014-01-19
date_created: 2018-12-11T11:51:45Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:50:22Z
day: '01'
ddc:
- '000'
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-642-54013-4_10
ec_funded: 1
file:
- access_level: open_access
checksum: bffa33d39be77df0da39defe97eabf84
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:06Z
date_updated: 2020-07-14T12:44:48Z
file_id: '4859'
file_name: IST-2014-179-v1+1_vmcai14.pdf
file_size: 444138
relation: main_file
file_date_updated: 2020-07-14T12:44:48Z
has_accepted_license: '1'
intvolume: ' 8318'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 161 - 181
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '5817'
pubrep_id: '179'
quality_controlled: '1'
scopus_import: 1
status: public
title: A logic-based framework for verifying consensus algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8318
year: '2014'
...
---
_id: '1393'
abstract:
- lang: eng
text: 'Probabilistic programs are usual functional or imperative programs with two
added constructs: (1) the ability to draw values at random from distributions,
and (2) the ability to condition values of variables in a program via observations.
Models from diverse application areas such as computer vision, coding theory,
cryptographic protocols, biology and reliability analysis can be written as probabilistic
programs. Probabilistic inference is the problem of computing an explicit representation
of the probability distribution implicitly specified by a probabilistic program.
Depending on the application, the desired output from inference may vary-we may
want to estimate the expected value of some function f with respect to the distribution,
or the mode of the distribution, or simply a set of samples drawn from the distribution.
In this paper, we describe connections this research area called \Probabilistic
Programming" has with programming languages and software engineering, and
this includes language design, and the static and dynamic analysis of programs.
We survey current state of the art and speculate on promising directions for future
research.'
article_processing_charge: No
author:
- first_name: Andrew
full_name: Gordon, Andrew
last_name: Gordon
- 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: Aditya
full_name: Nori, Aditya
last_name: Nori
- first_name: Sriram
full_name: Rajamani, Sriram
last_name: Rajamani
citation:
ama: 'Gordon A, Henzinger TA, Nori A, Rajamani S. Probabilistic programming. In:
Proceedings of the on Future of Software Engineering. ACM; 2014:167-181.
doi:10.1145/2593882.2593900'
apa: 'Gordon, A., Henzinger, T. A., Nori, A., & Rajamani, S. (2014). Probabilistic
programming. In Proceedings of the on Future of Software Engineering (pp.
167–181). Hyderabad, India: ACM. https://doi.org/10.1145/2593882.2593900'
chicago: Gordon, Andrew, Thomas A Henzinger, Aditya Nori, and Sriram Rajamani. “Probabilistic
Programming.” In Proceedings of the on Future of Software Engineering,
167–81. ACM, 2014. https://doi.org/10.1145/2593882.2593900.
ieee: A. Gordon, T. A. Henzinger, A. Nori, and S. Rajamani, “Probabilistic programming,”
in Proceedings of the on Future of Software Engineering, Hyderabad, India,
2014, pp. 167–181.
ista: 'Gordon A, Henzinger TA, Nori A, Rajamani S. 2014. Probabilistic programming.
Proceedings of the on Future of Software Engineering. FOSE: Future of Software
Engineering, 167–181.'
mla: Gordon, Andrew, et al. “Probabilistic Programming.” Proceedings of the on
Future of Software Engineering, ACM, 2014, pp. 167–81, doi:10.1145/2593882.2593900.
short: A. Gordon, T.A. Henzinger, A. Nori, S. Rajamani, in:, Proceedings of the
on Future of Software Engineering, ACM, 2014, pp. 167–181.
conference:
end_date: 2014-06-07
location: Hyderabad, India
name: 'FOSE: Future of Software Engineering'
start_date: 2014-05-31
date_created: 2018-12-11T11:51:45Z
date_published: 2014-05-31T00:00:00Z
date_updated: 2021-01-12T06:50:22Z
day: '31'
department:
- _id: ToHe
doi: 10.1145/2593882.2593900
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/2593882.2593900
month: '05'
oa: 1
oa_version: Published Version
page: 167 - 181
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
publication: Proceedings of the on Future of Software Engineering
publication_status: published
publisher: ACM
publist_id: '5816'
quality_controlled: '1'
scopus_import: 1
status: public
title: Probabilistic programming
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '1702'
abstract:
- lang: eng
text: In this paper we present INTERHORN, a solver for recursion-free Horn clauses.
The main application domain of INTERHORN lies in solving interpolation problems
arising in software verification. We show how a range of interpolation problems,
including path, transition, nested, state/transition and well-founded interpolation
can be handled directly by INTERHORN. By detailing these interpolation problems
and their Horn clause representations, we hope to encourage the emergence of a
common back-end interpolation interface useful for diverse verification tools.
alternative_title:
- EPTCS
author:
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Corneliu
full_name: Popeea, Corneliu
last_name: Popeea
- first_name: Andrey
full_name: Rybalchenko, Andrey
last_name: Rybalchenko
citation:
ama: 'Gupta A, Popeea C, Rybalchenko A. Generalised interpolation by solving recursion
free-horn clauses. In: Electronic Proceedings in Theoretical Computer Science,
EPTCS. Vol 169. Open Publishing; 2014:31-38. doi:10.4204/EPTCS.169.5'
apa: 'Gupta, A., Popeea, C., & Rybalchenko, A. (2014). Generalised interpolation
by solving recursion free-horn clauses. In Electronic Proceedings in Theoretical
Computer Science, EPTCS (Vol. 169, pp. 31–38). Vienna, Austria: Open Publishing.
https://doi.org/10.4204/EPTCS.169.5'
chicago: Gupta, Ashutosh, Corneliu Popeea, and Andrey Rybalchenko. “Generalised
Interpolation by Solving Recursion Free-Horn Clauses.” In Electronic Proceedings
in Theoretical Computer Science, EPTCS, 169:31–38. Open Publishing, 2014.
https://doi.org/10.4204/EPTCS.169.5.
ieee: A. Gupta, C. Popeea, and A. Rybalchenko, “Generalised interpolation by solving
recursion free-horn clauses,” in Electronic Proceedings in Theoretical Computer
Science, EPTCS, Vienna, Austria, 2014, vol. 169, pp. 31–38.
ista: 'Gupta A, Popeea C, Rybalchenko A. 2014. Generalised interpolation by solving
recursion free-horn clauses. Electronic Proceedings in Theoretical Computer Science,
EPTCS. HCVS: Horn Clauses for Verification and Synthesis, EPTCS, vol. 169, 31–38.'
mla: Gupta, Ashutosh, et al. “Generalised Interpolation by Solving Recursion Free-Horn
Clauses.” Electronic Proceedings in Theoretical Computer Science, EPTCS,
vol. 169, Open Publishing, 2014, pp. 31–38, doi:10.4204/EPTCS.169.5.
short: A. Gupta, C. Popeea, A. Rybalchenko, in:, Electronic Proceedings in Theoretical
Computer Science, EPTCS, Open Publishing, 2014, pp. 31–38.
conference:
end_date: 2014-07-17
location: Vienna, Austria
name: 'HCVS: Horn Clauses for Verification and Synthesis'
start_date: 2014-07-17
date_created: 2018-12-11T11:53:33Z
date_published: 2014-12-02T00:00:00Z
date_updated: 2021-01-12T06:52:38Z
day: '02'
department:
- _id: ToHe
doi: 10.4204/EPTCS.169.5
intvolume: ' 169'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1303.7378v2
month: '12'
oa: 1
oa_version: Submitted Version
page: 31 - 38
publication: Electronic Proceedings in Theoretical Computer Science, EPTCS
publication_status: published
publisher: Open Publishing
publist_id: '5435'
quality_controlled: '1'
status: public
title: Generalised interpolation by solving recursion free-horn clauses
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 169
year: '2014'
...
---
_id: '1869'
abstract:
- lang: eng
text: Boolean controllers for systems with complex datapaths are often very difficult
to implement correctly, in particular when concurrency is involved. Yet, in many
instances it is easy to formally specify correctness. For example, the specification
for the controller of a pipelined processor only has to state that the pipelined
processor gives the same results as a non-pipelined reference design. This makes
such controllers a good target for automated synthesis. However, an efficient
abstraction for the complex datapath elements is needed, as a bit-precise description
is often infeasible. We present Suraq, the first controller synthesis tool which
uses uninterpreted functions for the abstraction. Quantified firstorder formulas
(with specific quantifier structure) serve as the specification language from
which Suraq synthesizes Boolean controllers. Suraq transforms the specification
into an unsatisfiable SMT formula, and uses Craig interpolation to compute its
results. Using Suraq, we were able to synthesize a controller (consisting of two
Boolean signals) for a five-stage pipelined DLX processor in roughly one hour
and 15 minutes.
acknowledgement: The work presented in this paper was supported in part by the European
Research Council (ERC) under grant agreement QUAINT (I774-N23)
alternative_title:
- LNCS
author:
- first_name: Georg
full_name: Hofferek, Georg
last_name: Hofferek
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
citation:
ama: 'Hofferek G, Gupta A. Suraq - a controller synthesis tool using uninterpreted
functions. In: Yahav E, ed. HVC 2014. Vol 8855. Springer; 2014:68-74. doi:10.1007/978-3-319-13338-6_6'
apa: 'Hofferek, G., & Gupta, A. (2014). Suraq - a controller synthesis tool
using uninterpreted functions. In E. Yahav (Ed.), HVC 2014 (Vol. 8855,
pp. 68–74). Haifa, Israel: Springer. https://doi.org/10.1007/978-3-319-13338-6_6'
chicago: Hofferek, Georg, and Ashutosh Gupta. “Suraq - a Controller Synthesis Tool
Using Uninterpreted Functions.” In HVC 2014, edited by Eran Yahav, 8855:68–74.
Springer, 2014. https://doi.org/10.1007/978-3-319-13338-6_6.
ieee: G. Hofferek and A. Gupta, “Suraq - a controller synthesis tool using uninterpreted
functions,” in HVC 2014, Haifa, Israel, 2014, vol. 8855, pp. 68–74.
ista: 'Hofferek G, Gupta A. 2014. Suraq - a controller synthesis tool using uninterpreted
functions. HVC 2014. HVC: Haifa Verification Conference, LNCS, vol. 8855, 68–74.'
mla: Hofferek, Georg, and Ashutosh Gupta. “Suraq - a Controller Synthesis Tool Using
Uninterpreted Functions.” HVC 2014, edited by Eran Yahav, vol. 8855, Springer,
2014, pp. 68–74, doi:10.1007/978-3-319-13338-6_6.
short: G. Hofferek, A. Gupta, in:, E. Yahav (Ed.), HVC 2014, Springer, 2014, pp.
68–74.
conference:
end_date: 2014-11-20
location: Haifa, Israel
name: 'HVC: Haifa Verification Conference'
start_date: 2014-11-18
date_created: 2018-12-11T11:54:27Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:44Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-319-13338-6_6
ec_funded: 1
editor:
- first_name: Eran
full_name: Yahav, Eran
last_name: Yahav
intvolume: ' 8855'
language:
- iso: eng
month: '01'
oa_version: None
page: 68 - 74
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: HVC 2014
publication_status: published
publisher: Springer
publist_id: '5228'
quality_controlled: '1'
status: public
title: Suraq - a controller synthesis tool using uninterpreted functions
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8855
year: '2014'
...
---
_id: '1872'
abstract:
- lang: eng
text: Extensionality axioms are common when reasoning about data collections, such
as arrays and functions in program analysis, or sets in mathematics. An extensionality
axiom asserts that two collections are equal if they consist of the same elements
at the same indices. Using extensionality is often required to show that two collections
are equal. A typical example is the set theory theorem (∀x)(∀y)x∪y = y ∪x. Interestingly,
while humans have no problem with proving such set identities using extensionality,
they are very hard for superposition theorem provers because of the calculi they
use. In this paper we show how addition of a new inference rule, called extensionality
resolution, allows first-order theorem provers to easily solve problems no modern
first-order theorem prover can solve. We illustrate this by running the VAMPIRE
theorem prover with extensionality resolution on a number of set theory and array
problems. Extensionality resolution helps VAMPIRE to solve problems from the TPTP
library of first-order problems that were never solved before by any prover.
acknowledgement: This research was supported in part by the Austrian National Research
Network RiSE (S11410-N23).
alternative_title:
- LNCS
author:
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Laura
full_name: Kovács, Laura
last_name: Kovács
- first_name: Bernhard
full_name: Kragl, Bernhard
id: 320FC952-F248-11E8-B48F-1D18A9856A87
last_name: Kragl
orcid: 0000-0001-7745-9117
- first_name: Andrei
full_name: Voronkov, Andrei
last_name: Voronkov
citation:
ama: 'Gupta A, Kovács L, Kragl B, Voronkov A. Extensional crisis and proving identity.
In: Cassez F, Raskin J-F, eds. ATVA 2014. Vol 8837. Springer; 2014:185-200.
doi:10.1007/978-3-319-11936-6_14'
apa: 'Gupta, A., Kovács, L., Kragl, B., & Voronkov, A. (2014). Extensional crisis
and proving identity. In F. Cassez & J.-F. Raskin (Eds.), ATVA 2014
(Vol. 8837, pp. 185–200). Sydney, Australia: Springer. https://doi.org/10.1007/978-3-319-11936-6_14'
chicago: Gupta, Ashutosh, Laura Kovács, Bernhard Kragl, and Andrei Voronkov. “Extensional
Crisis and Proving Identity.” In ATVA 2014, edited by Franck Cassez and
Jean-François Raskin, 8837:185–200. Springer, 2014. https://doi.org/10.1007/978-3-319-11936-6_14.
ieee: A. Gupta, L. Kovács, B. Kragl, and A. Voronkov, “Extensional crisis and proving
identity,” in ATVA 2014, Sydney, Australia, 2014, vol. 8837, pp. 185–200.
ista: 'Gupta A, Kovács L, Kragl B, Voronkov A. 2014. Extensional crisis and proving
identity. ATVA 2014. ATVA: Automated Technology for Verification and Analysis,
LNCS, vol. 8837, 185–200.'
mla: Gupta, Ashutosh, et al. “Extensional Crisis and Proving Identity.” ATVA
2014, edited by Franck Cassez and Jean-François Raskin, vol. 8837, Springer,
2014, pp. 185–200, doi:10.1007/978-3-319-11936-6_14.
short: A. Gupta, L. Kovács, B. Kragl, A. Voronkov, in:, F. Cassez, J.-F. Raskin
(Eds.), ATVA 2014, Springer, 2014, pp. 185–200.
conference:
end_date: 2014-11-07
location: Sydney, Australia
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2014-11-03
date_created: 2018-12-11T11:54:28Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:45Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-319-11936-6_14
ec_funded: 1
editor:
- first_name: Franck
full_name: Cassez, Franck
last_name: Cassez
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
file:
- access_level: open_access
checksum: af4bd3fc1f4c93075e4dc5cbf625fe7b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:15Z
date_updated: 2020-07-14T12:45:19Z
file_id: '4801'
file_name: IST-2016-641-v1+1_atva2014.pdf
file_size: 244294
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 8837'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 185 - 200
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: ATVA 2014
publication_status: published
publisher: Springer
publist_id: '5226'
pubrep_id: '641'
quality_controlled: '1'
scopus_import: 1
status: public
title: Extensional crisis and proving identity
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8837
year: '2014'
...
---
_id: '1870'
abstract:
- lang: eng
text: We investigate the problem of checking if a finite-state transducer is robust
to uncertainty in its input. Our notion of robustness is based on the analytic
notion of Lipschitz continuity - a transducer is K-(Lipschitz) robust if the perturbation
in its output is at most K times the perturbation in its input. We quantify input
and output perturbation using similarity functions. We show that K-robustness
is undecidable even for deterministic transducers. We identify a class of functional
transducers, which admits a polynomial time automata-theoretic decision procedure
for K-robustness. This class includes Mealy machines and functional letter-to-letter
transducers. We also study K-robustness of nondeterministic transducers. Since
a nondeterministic transducer generates a set of output words for each input word,
we quantify output perturbation using setsimilarity functions. We show that K-robustness
of nondeterministic transducers is undecidable, even for letter-to-letter transducers.
We identify a class of set-similarity functions which admit decidable K-robustness
of letter-to-letter transducers.
alternative_title:
- LIPIcs
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
- first_name: Roopsha
full_name: Samanta, Roopsha
id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87
last_name: Samanta
citation:
ama: 'Henzinger TA, Otop J, Samanta R. Lipschitz robustness of finite-state transducers.
In: Leibniz International Proceedings in Informatics, LIPIcs. Vol 29. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2014:431-443. doi:10.4230/LIPIcs.FSTTCS.2014.431'
apa: 'Henzinger, T. A., Otop, J., & Samanta, R. (2014). Lipschitz robustness
of finite-state transducers. In Leibniz International Proceedings in Informatics,
LIPIcs (Vol. 29, pp. 431–443). Delhi, India: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.431'
chicago: Henzinger, Thomas A, Jan Otop, and Roopsha Samanta. “Lipschitz Robustness
of Finite-State Transducers.” In Leibniz International Proceedings in Informatics,
LIPIcs, 29:431–43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.431.
ieee: T. A. Henzinger, J. Otop, and R. Samanta, “Lipschitz robustness of finite-state
transducers,” in Leibniz International Proceedings in Informatics, LIPIcs,
Delhi, India, 2014, vol. 29, pp. 431–443.
ista: 'Henzinger TA, Otop J, Samanta R. 2014. Lipschitz robustness of finite-state
transducers. Leibniz International Proceedings in Informatics, LIPIcs. FSTTCS:
Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol.
29, 431–443.'
mla: Henzinger, Thomas A., et al. “Lipschitz Robustness of Finite-State Transducers.”
Leibniz International Proceedings in Informatics, LIPIcs, vol. 29, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 431–43, doi:10.4230/LIPIcs.FSTTCS.2014.431.
short: T.A. Henzinger, J. Otop, R. Samanta, in:, Leibniz International Proceedings
in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014,
pp. 431–443.
conference:
end_date: 2014-12-17
location: Delhi, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2014-12-15
date_created: 2018-12-11T11:54:27Z
date_published: 2014-12-01T00:00:00Z
date_updated: 2021-01-12T06:53:45Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.FSTTCS.2014.431
file:
- access_level: open_access
checksum: 7b1aff1710a8bffb7080ec07f62d9a17
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:11Z
date_updated: 2020-07-14T12:45:19Z
file_id: '4734'
file_name: IST-2017-804-v1+1_37.pdf
file_size: 562151
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 29'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 431 - 443
publication: Leibniz International Proceedings in Informatics, LIPIcs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5227'
pubrep_id: '804'
quality_controlled: '1'
status: public
title: Lipschitz robustness of finite-state transducers
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: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2014'
...
---
_id: '1875'
abstract:
- lang: eng
text: We present a formal framework for repairing infinite-state, imperative, sequential
programs, with (possibly recursive) procedures and multiple assertions; the framework
can generate repaired programs by modifying the original erroneous program in
multiple program locations, and can ensure the readability of the repaired program
using user-defined expression templates; the framework also generates a set of
inductive assertions that serve as a proof of correctness of the repaired program.
As a step toward integrating programmer intent and intuition in automated program
repair, we present a cost-aware formulation - given a cost function associated
with permissible statement modifications, the goal is to ensure that the total
program modification cost does not exceed a given repair budget. As part of our
predicate abstractionbased solution framework, we present a sound and complete
algorithm for repair of Boolean programs. We have developed a prototype tool based
on SMT solving and used it successfully to repair diverse errors in benchmark
C programs.
alternative_title:
- LNCS
author:
- first_name: Roopsha
full_name: Samanta, Roopsha
id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87
last_name: Samanta
- first_name: Oswaldo
full_name: Olivo, Oswaldo
last_name: Olivo
- first_name: Emerson
full_name: Allen, Emerson
last_name: Allen
citation:
ama: 'Samanta R, Olivo O, Allen E. Cost-aware automatic program repair. In: Müller-Olm
M, Seidl H, eds. Vol 8723. Springer; 2014:268-284. doi:10.1007/978-3-319-10936-7_17'
apa: 'Samanta, R., Olivo, O., & Allen, E. (2014). Cost-aware automatic program
repair. In M. Müller-Olm & H. Seidl (Eds.) (Vol. 8723, pp. 268–284). Presented
at the SAS: Static Analysis Symposium, Munich, Germany: Springer. https://doi.org/10.1007/978-3-319-10936-7_17'
chicago: Samanta, Roopsha, Oswaldo Olivo, and Emerson Allen. “Cost-Aware Automatic
Program Repair.” edited by Markus Müller-Olm and Helmut Seidl, 8723:268–84. Springer,
2014. https://doi.org/10.1007/978-3-319-10936-7_17.
ieee: 'R. Samanta, O. Olivo, and E. Allen, “Cost-aware automatic program repair,”
presented at the SAS: Static Analysis Symposium, Munich, Germany, 2014, vol. 8723,
pp. 268–284.'
ista: 'Samanta R, Olivo O, Allen E. 2014. Cost-aware automatic program repair. SAS:
Static Analysis Symposium, LNCS, vol. 8723, 268–284.'
mla: Samanta, Roopsha, et al. Cost-Aware Automatic Program Repair. Edited
by Markus Müller-Olm and Helmut Seidl, vol. 8723, Springer, 2014, pp. 268–84,
doi:10.1007/978-3-319-10936-7_17.
short: R. Samanta, O. Olivo, E. Allen, in:, M. Müller-Olm, H. Seidl (Eds.), Springer,
2014, pp. 268–284.
conference:
end_date: 2014-09-14
location: Munich, Germany
name: 'SAS: Static Analysis Symposium'
start_date: 2014-09-11
date_created: 2018-12-11T11:54:29Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2021-01-12T06:53:46Z
day: '01'
ddc:
- '000'
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-319-10936-7_17
editor:
- first_name: Markus
full_name: Müller-Olm, Markus
last_name: Müller-Olm
- first_name: Helmut
full_name: Seidl, Helmut
last_name: Seidl
file:
- access_level: open_access
checksum: 78ec4ea1bdecc676cd3e8cad35c6182c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:51Z
date_updated: 2020-07-14T12:45:19Z
file_id: '4650'
file_name: IST-2014-313-v1+1_SOE.SAS14.pdf
file_size: 409485
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 8723'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 268 - 284
publication_status: published
publisher: Springer
publist_id: '5221'
pubrep_id: '313'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cost-aware automatic program repair
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8723
year: '2014'
...
---
_id: '2027'
abstract:
- lang: eng
text: We present a general framework for applying machine-learning algorithms to
the verification of Markov decision processes (MDPs). The primary goal of these
techniques is to improve performance by avoiding an exhaustive exploration of
the state space. Our framework focuses on probabilistic reachability, which is
a core property for verification, and is illustrated through two distinct instantiations.
The first assumes that full knowledge of the MDP is available, and performs a
heuristic-driven partial exploration of the model, yielding precise lower and
upper bounds on the required probability. The second tackles the case where we
may only sample the MDP, and yields probabilistic guarantees, again in terms of
both the lower and upper bounds, which provides efficient stopping criteria for
the approximation. The latter is the first extension of statistical model checking
for unbounded properties inMDPs. In contrast with other related techniques, our
approach is not restricted to time-bounded (finite-horizon) or discounted properties,
nor does it assume any particular properties of the MDP. We also show how our
methods extend to LTL objectives. We present experimental results showing the
performance of our framework on several examples.
acknowledgement: This research was funded in part by the European Research Council
(ERC) under grant agreement 246967 (VERIWARE), by the EU FP7 project HIERATIC, by
the Czech Science Foundation grant No P202/12/P612, by EPSRC project EP/K038575/1.
alternative_title:
- LNCS
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Vojtěch
full_name: Forejt, Vojtěch
last_name: Forejt
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Marta
full_name: Kwiatkowska, Marta
last_name: Kwiatkowska
- first_name: David
full_name: Parker, David
last_name: Parker
- first_name: Mateusz
full_name: Ujma, Mateusz
last_name: Ujma
citation:
ama: 'Brázdil T, Chatterjee K, Chmelik M, et al. Verification of markov decision
processes using learning algorithms. In: Cassez F, Raskin J-F, eds. Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics). Vol 8837. Society of Industrial and
Applied Mathematics; 2014:98-114. doi:10.1007/978-3-319-11936-6_8'
apa: 'Brázdil, T., Chatterjee, K., Chmelik, M., Forejt, V., Kretinsky, J., Kwiatkowska,
M., … Ujma, M. (2014). Verification of markov decision processes using learning
algorithms. In F. Cassez & J.-F. Raskin (Eds.), Lecture Notes in Computer
Science (including subseries Lecture Notes in Artificial Intelligence and Lecture
Notes in Bioinformatics) (Vol. 8837, pp. 98–114). Sydney, Australia: Society
of Industrial and Applied Mathematics. https://doi.org/10.1007/978-3-319-11936-6_8'
chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Vojtěch Forejt,
Jan Kretinsky, Marta Kwiatkowska, David Parker, and Mateusz Ujma. “Verification
of Markov Decision Processes Using Learning Algorithms.” In Lecture Notes
in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), edited by Franck Cassez and Jean-François
Raskin, 8837:98–114. Society of Industrial and Applied Mathematics, 2014. https://doi.org/10.1007/978-3-319-11936-6_8.
ieee: T. Brázdil et al., “Verification of markov decision processes using
learning algorithms,” in Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
Sydney, Australia, 2014, vol. 8837, pp. 98–114.
ista: 'Brázdil T, Chatterjee K, Chmelik M, Forejt V, Kretinsky J, Kwiatkowska M,
Parker D, Ujma M. 2014. Verification of markov decision processes using learning
algorithms. Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics). ALENEX: Algorithm
Engineering and Experiments, LNCS, vol. 8837, 98–114.'
mla: Brázdil, Tomáš, et al. “Verification of Markov Decision Processes Using Learning
Algorithms.” Lecture Notes in Computer Science (Including Subseries Lecture
Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), edited
by Franck Cassez and Jean-François Raskin, vol. 8837, Society of Industrial and
Applied Mathematics, 2014, pp. 98–114, doi:10.1007/978-3-319-11936-6_8.
short: T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska,
D. Parker, M. Ujma, in:, F. Cassez, J.-F. Raskin (Eds.), Lecture Notes in Computer
Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture
Notes in Bioinformatics), Society of Industrial and Applied Mathematics, 2014,
pp. 98–114.
conference:
end_date: 2014-11-07
location: Sydney, Australia
name: 'ALENEX: Algorithm Engineering and Experiments'
start_date: 2014-11-03
date_created: 2018-12-11T11:55:17Z
date_published: 2014-11-01T00:00:00Z
date_updated: 2021-01-12T06:54:49Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-319-11936-6_8
ec_funded: 1
editor:
- first_name: Franck
full_name: Cassez, Franck
last_name: Cassez
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
intvolume: ' 8837'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1402.2967
month: '11'
oa: 1
oa_version: Submitted Version
page: 98 - 114
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 26241A12-B435-11E9-9278-68D0E5697425
grant_number: '24696'
name: LIGHT-REGULATED LIGAND TRAPS FOR SPATIO-TEMPORAL INHIBITION OF CELL SIGNALING
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: ' Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)'
publication_status: published
publisher: Society of Industrial and Applied Mathematics
publist_id: '5046'
quality_controlled: '1'
status: public
title: Verification of markov decision processes using learning algorithms
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8837
year: '2014'
...
---
_id: '2026'
abstract:
- lang: eng
text: 'We present a tool for translating LTL formulae into deterministic ω-automata.
It is the first tool that covers the whole LTL that does not use Safra’s determinization
or any of its variants. This leads to smaller automata. There are several outputs
of the tool: firstly, deterministic Rabin automata, which are the standard input
for probabilistic model checking, e.g. for the probabilistic model-checker PRISM;
secondly, deterministic generalized Rabin automata, which can also be used for
probabilistic model checking and are sometimes by orders of magnitude smaller.
We also link our tool to PRISM and show that this leads to a significant speed-up
of probabilistic LTL model checking, especially with the generalized Rabin automata.'
acknowledgement: "Sponsor: P202/12/G061; GACR; Czech Science Foundation\r\n\r\n"
alternative_title:
- LNCS
author:
- first_name: Zuzana
full_name: Komárková, Zuzana
last_name: Komárková
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: 'Komárková Z, Kretinsky J. Rabinizer 3: Safraless translation of ltl to small
deterministic automata. In: Cassez F, Raskin J-F, eds. Lecture Notes in Computer
Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture
Notes in Bioinformatics). Vol 8837. Springer; 2014:235-241. doi:10.1007/978-3-319-11936-6_17'
apa: 'Komárková, Z., & Kretinsky, J. (2014). Rabinizer 3: Safraless translation
of ltl to small deterministic automata. In F. Cassez & J.-F. Raskin (Eds.),
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics) (Vol. 8837, pp. 235–241).
Sydney, Australia: Springer. https://doi.org/10.1007/978-3-319-11936-6_17'
chicago: 'Komárková, Zuzana, and Jan Kretinsky. “Rabinizer 3: Safraless Translation
of Ltl to Small Deterministic Automata.” In Lecture Notes in Computer Science
(Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics), edited by Franck Cassez and Jean-François Raskin, 8837:235–41.
Springer, 2014. https://doi.org/10.1007/978-3-319-11936-6_17.'
ieee: 'Z. Komárková and J. Kretinsky, “Rabinizer 3: Safraless translation of ltl
to small deterministic automata,” in Lecture Notes in Computer Science (including
subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
Sydney, Australia, 2014, vol. 8837, pp. 235–241.'
ista: 'Komárková Z, Kretinsky J. 2014. Rabinizer 3: Safraless translation of ltl
to small deterministic automata. Lecture Notes in Computer Science (including
subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).
ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 8837, 235–241.'
mla: 'Komárková, Zuzana, and Jan Kretinsky. “Rabinizer 3: Safraless Translation
of Ltl to Small Deterministic Automata.” Lecture Notes in Computer Science
(Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics), edited by Franck Cassez and Jean-François Raskin, vol.
8837, Springer, 2014, pp. 235–41, doi:10.1007/978-3-319-11936-6_17.'
short: Z. Komárková, J. Kretinsky, in:, F. Cassez, J.-F. Raskin (Eds.), Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Springer, 2014, pp. 235–241.
conference:
end_date: 2014-11-07
location: Sydney, Australia
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2014-11-03
date_created: 2018-12-11T11:55:17Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:49Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-319-11936-6_17
ec_funded: 1
editor:
- first_name: Franck
full_name: Cassez, Franck
last_name: Cassez
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
intvolume: ' 8837'
language:
- iso: eng
month: '01'
oa_version: None
page: 235 - 241
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Springer
publist_id: '5045'
quality_controlled: '1'
status: public
title: 'Rabinizer 3: Safraless translation of ltl to small deterministic automata'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8837
year: '2014'
...
---
_id: '2053'
abstract:
- lang: eng
text: In contrast to the usual understanding of probabilistic systems as stochastic
processes, recently these systems have also been regarded as transformers of probabilities.
In this paper, we give a natural definition of strong bisimulation for probabilistic
systems corresponding to this view that treats probability distributions as first-class
citizens. Our definition applies in the same way to discrete systems as well as
to systems with uncountable state and action spaces. Several examples demonstrate
that our definition refines the understanding of behavioural equivalences of probabilistic
systems. In particular, it solves a longstanding open problem concerning the representation
of memoryless continuous time by memoryfull continuous time. Finally, we give
algorithms for computing this bisimulation not only for finite but also for classes
of uncountably infinite systems.
acknowledgement: This work is supported by the EU 7th Framework Programme under grant
agreements 295261 (MEALS) and 318490 (SENSATION), Czech Science Foundation under
grant agreement P202/12/G061, the DFG Transregional Collaborative Research Centre
SFB/TR 14 AVACS, and by the CAS/SAFEA International Partnership Program for Creative
Research Teams.
alternative_title:
- LNCS
author:
- first_name: Holger
full_name: Hermanns, Holger
last_name: Hermanns
- first_name: Jan
full_name: Krčál, Jan
last_name: Krčál
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: 'Hermanns H, Krčál J, Kretinsky J. Probabilistic bisimulation: Naturally on
distributions. In: Baldan P, Gorla D, eds. Lecture Notes in Computer Science
(Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics). Vol 8704. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2014:249-265. doi:10.1007/978-3-662-44584-6_18'
apa: 'Hermanns, H., Krčál, J., & Kretinsky, J. (2014). Probabilistic bisimulation:
Naturally on distributions. In P. Baldan & D. Gorla (Eds.), Lecture Notes
in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics) (Vol. 8704, pp. 249–265). Rome, Italy:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-662-44584-6_18'
chicago: 'Hermanns, Holger, Jan Krčál, and Jan Kretinsky. “Probabilistic Bisimulation:
Naturally on Distributions.” In Lecture Notes in Computer Science (Including
Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
edited by Paolo Baldan and Daniele Gorla, 8704:249–65. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2014. https://doi.org/10.1007/978-3-662-44584-6_18.'
ieee: 'H. Hermanns, J. Krčál, and J. Kretinsky, “Probabilistic bisimulation: Naturally
on distributions,” in Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
Rome, Italy, 2014, vol. 8704, pp. 249–265.'
ista: 'Hermanns H, Krčál J, Kretinsky J. 2014. Probabilistic bisimulation: Naturally
on distributions. Lecture Notes in Computer Science (including subseries Lecture
Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). CONCUR:
Concurrency Theory, LNCS, vol. 8704, 249–265.'
mla: 'Hermanns, Holger, et al. “Probabilistic Bisimulation: Naturally on Distributions.”
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics), edited by Paolo Baldan
and Daniele Gorla, vol. 8704, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2014, pp. 249–65, doi:10.1007/978-3-662-44584-6_18.'
short: H. Hermanns, J. Krčál, J. Kretinsky, in:, P. Baldan, D. Gorla (Eds.), Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2014, pp. 249–265.
conference:
end_date: 2014-09-05
location: Rome, Italy
name: 'CONCUR: Concurrency Theory'
start_date: 2014-09-02
date_created: 2018-12-11T11:55:27Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2021-01-12T06:55:00Z
day: '01'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1007/978-3-662-44584-6_18
ec_funded: 1
editor:
- first_name: Paolo
full_name: Baldan, Paolo
last_name: Baldan
- first_name: Daniele
full_name: Gorla, Daniele
last_name: Gorla
intvolume: ' 8704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1404.5084
month: '09'
oa: 1
oa_version: Submitted Version
page: 249 - 265
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4993'
status: public
title: 'Probabilistic bisimulation: Naturally on distributions'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8704
year: '2014'
...
---
_id: '2056'
abstract:
- lang: eng
text: 'We consider a continuous-time Markov chain (CTMC) whose state space is partitioned
into aggregates, and each aggregate is assigned a probability measure. A sufficient
condition for defining a CTMC over the aggregates is presented as a variant of
weak lumpability, which also characterizes that the measure over the original
process can be recovered from that of the aggregated one. We show how the applicability
of de-aggregation depends on the initial distribution. The application section
is devoted to illustrate how the developed theory aids in reducing CTMC models
of biochemical systems particularly in connection to protein-protein interactions.
We assume that the model is written by a biologist in form of site-graph-rewrite
rules. Site-graph-rewrite rules compactly express that, often, only a local context
of a protein (instead of a full molecular species) needs to be in a certain configuration
in order to trigger a reaction event. This observation leads to suitable aggregate
Markov chains with smaller state spaces, thereby providing sufficient reduction
in computational complexity. This is further exemplified in two case studies:
simple unbounded polymerization and early EGFR/insulin crosstalk.'
acknowledgement: T. Petrov is supported by SystemsX.ch—the Swiss Inititative for Systems
Biology.
author:
- first_name: Arnab
full_name: Ganguly, Arnab
last_name: Ganguly
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
- first_name: Heinz
full_name: Koeppl, Heinz
last_name: Koeppl
citation:
ama: Ganguly A, Petrov T, Koeppl H. Markov chain aggregation and its applications
to combinatorial reaction networks. Journal of Mathematical Biology. 2014;69(3):767-797.
doi:10.1007/s00285-013-0738-7
apa: Ganguly, A., Petrov, T., & Koeppl, H. (2014). Markov chain aggregation
and its applications to combinatorial reaction networks. Journal of Mathematical
Biology. Springer. https://doi.org/10.1007/s00285-013-0738-7
chicago: Ganguly, Arnab, Tatjana Petrov, and Heinz Koeppl. “Markov Chain Aggregation
and Its Applications to Combinatorial Reaction Networks.” Journal of Mathematical
Biology. Springer, 2014. https://doi.org/10.1007/s00285-013-0738-7.
ieee: A. Ganguly, T. Petrov, and H. Koeppl, “Markov chain aggregation and its applications
to combinatorial reaction networks,” Journal of Mathematical Biology, vol.
69, no. 3. Springer, pp. 767–797, 2014.
ista: Ganguly A, Petrov T, Koeppl H. 2014. Markov chain aggregation and its applications
to combinatorial reaction networks. Journal of Mathematical Biology. 69(3), 767–797.
mla: Ganguly, Arnab, et al. “Markov Chain Aggregation and Its Applications to Combinatorial
Reaction Networks.” Journal of Mathematical Biology, vol. 69, no. 3, Springer,
2014, pp. 767–97, doi:10.1007/s00285-013-0738-7.
short: A. Ganguly, T. Petrov, H. Koeppl, Journal of Mathematical Biology 69 (2014)
767–797.
date_created: 2018-12-11T11:55:28Z
date_published: 2014-11-20T00:00:00Z
date_updated: 2021-01-12T06:55:01Z
day: '20'
department:
- _id: CaGu
- _id: ToHe
doi: 10.1007/s00285-013-0738-7
intvolume: ' 69'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1303.4532
month: '11'
oa: 1
oa_version: Submitted Version
page: 767 - 797
publication: Journal of Mathematical Biology
publication_status: published
publisher: Springer
publist_id: '4990'
quality_controlled: '1'
scopus_import: 1
status: public
title: Markov chain aggregation and its applications to combinatorial reaction networks
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2014'
...
---
_id: '2187'
abstract:
- lang: eng
text: 'Systems should not only be correct but also robust in the sense that they
behave reasonably in unexpected situations. This article addresses synthesis of
robust reactive systems from temporal specifications. Existing methods allow arbitrary
behavior if assumptions in the specification are violated. To overcome this, we
define two robustness notions, combine them, and show how to enforce them in synthesis.
The first notion applies to safety properties: If safety assumptions are violated
temporarily, we require that the system recovers to normal operation with as few
errors as possible. The second notion requires that, if liveness assumptions are
violated, as many guarantees as possible should be fulfilled nevertheless. We
present a synthesis procedure achieving this for the important class of GR(1)
specifications, and establish complexity bounds. We also present an implementation
of a special case of robustness, and show experimental results.'
article_processing_charge: No
article_type: original
author:
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Karin
full_name: Greimel, Karin
last_name: Greimel
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Georg
full_name: Hofferek, Georg
last_name: Hofferek
- first_name: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
- first_name: Bettina
full_name: Könighofer, Bettina
last_name: Könighofer
- first_name: Robert
full_name: Könighofer, Robert
last_name: Könighofer
citation:
ama: Bloem R, Chatterjee K, Greimel K, et al. Synthesizing robust systems. Acta
Informatica. 2014;51(3-4):193-220. doi:10.1007/s00236-013-0191-5
apa: Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., Hofferek, G., Jobstmann,
B., … Könighofer, R. (2014). Synthesizing robust systems. Acta Informatica.
Springer. https://doi.org/10.1007/s00236-013-0191-5
chicago: Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger,
Georg Hofferek, Barbara Jobstmann, Bettina Könighofer, and Robert Könighofer.
“Synthesizing Robust Systems.” Acta Informatica. Springer, 2014. https://doi.org/10.1007/s00236-013-0191-5.
ieee: R. Bloem et al., “Synthesizing robust systems,” Acta Informatica,
vol. 51, no. 3–4. Springer, pp. 193–220, 2014.
ista: Bloem R, Chatterjee K, Greimel K, Henzinger TA, Hofferek G, Jobstmann B, Könighofer
B, Könighofer R. 2014. Synthesizing robust systems. Acta Informatica. 51(3–4),
193–220.
mla: Bloem, Roderick, et al. “Synthesizing Robust Systems.” Acta Informatica,
vol. 51, no. 3–4, Springer, 2014, pp. 193–220, doi:10.1007/s00236-013-0191-5.
short: R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann,
B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.
date_created: 2018-12-11T11:56:13Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:51Z
day: '01'
ddc:
- '621'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/s00236-013-0191-5
ec_funded: 1
file:
- access_level: open_access
checksum: d7f560f3d923f0f00aa10a0652f83273
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:44Z
date_updated: 2020-07-14T12:45:31Z
file_id: '5234'
file_name: IST-2012-71-v1+1_Synthesizing_robust_systems.pdf
file_size: 169523
relation: main_file
file_date_updated: 2020-07-14T12:45:31Z
has_accepted_license: '1'
intvolume: ' 51'
issue: 3-4
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 193 - 220
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Acta Informatica
publication_status: published
publisher: Springer
publist_id: '4787'
pubrep_id: '71'
quality_controlled: '1'
scopus_import: 1
status: public
title: Synthesizing robust systems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2014'
...
---
_id: '2190'
abstract:
- lang: eng
text: We present a new algorithm to construct a (generalized) deterministic Rabin
automaton for an LTL formula φ. The automaton is the product of a master automaton
and an array of slave automata, one for each G-subformula of φ. The slave automaton
for G ψ is in charge of recognizing whether FG ψ holds. As opposed to standard
determinization procedures, the states of all our automata have a clear logical
structure, which allows for various optimizations. Our construction subsumes former
algorithms for fragments of LTL. Experimental results show improvement in the
sizes of the resulting automata compared to existing methods.
acknowledgement: The author is on leave from Faculty of Informatics, Masaryk University,
Czech Republic, and partially supported by the Czech Science Foundation, grant No.
P202/12/G061.
alternative_title:
- LNCS
author:
- first_name: Javier
full_name: Esparza, Javier
last_name: Esparza
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: 'Esparza J, Kretinsky J. From LTL to deterministic automata: A safraless compositional
approach. In: Vol 8559. Springer; 2014:192-208. doi:10.1007/978-3-319-08867-9_13'
apa: 'Esparza, J., & Kretinsky, J. (2014). From LTL to deterministic automata:
A safraless compositional approach (Vol. 8559, pp. 192–208). Presented at the
CAV: Computer Aided Verification, Springer. https://doi.org/10.1007/978-3-319-08867-9_13'
chicago: 'Esparza, Javier, and Jan Kretinsky. “From LTL to Deterministic Automata:
A Safraless Compositional Approach,” 8559:192–208. Springer, 2014. https://doi.org/10.1007/978-3-319-08867-9_13.'
ieee: 'J. Esparza and J. Kretinsky, “From LTL to deterministic automata: A safraless
compositional approach,” presented at the CAV: Computer Aided Verification, 2014,
vol. 8559, pp. 192–208.'
ista: 'Esparza J, Kretinsky J. 2014. From LTL to deterministic automata: A safraless
compositional approach. CAV: Computer Aided Verification, LNCS, vol. 8559, 192–208.'
mla: 'Esparza, Javier, and Jan Kretinsky. From LTL to Deterministic Automata:
A Safraless Compositional Approach. Vol. 8559, Springer, 2014, pp. 192–208,
doi:10.1007/978-3-319-08867-9_13.'
short: J. Esparza, J. Kretinsky, in:, Springer, 2014, pp. 192–208.
conference:
name: 'CAV: Computer Aided Verification'
date_created: 2018-12-11T11:56:14Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:55:53Z
day: '01'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1007/978-3-319-08867-9_13
ec_funded: 1
intvolume: ' 8559'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1402.3388
month: '01'
oa: 1
oa_version: Submitted Version
page: 192 - 208
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication_status: published
publisher: Springer
publist_id: '4784'
quality_controlled: '1'
status: public
title: 'From LTL to deterministic automata: A safraless compositional approach'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8559
year: '2014'
...
---
_id: '2233'
abstract:
- lang: eng
text: ' A discounted-sum automaton (NDA) is a nondeterministic finite automaton
with edge weights, valuing a run by the discounted sum of visited edge weights.
More precisely, the weight in the i-th position of the run is divided by λi, where
the discount factor λ is a fixed rational number greater than 1. The value of
a word is the minimal value of the automaton runs on it. Discounted summation
is a common and useful measuring scheme, especially for infinite sequences, reflecting
the assumption that earlier weights are more important than later weights. Unfortunately,
determinization of NDAs, which is often essential in formal verification, is,
in general, not possible. We provide positive news, showing that every NDA with
an integral discount factor is determinizable. We complete the picture by proving
that the integers characterize exactly the discount factors that guarantee determinizability:
for every nonintegral rational discount factor λ, there is a nondeterminizable
λ-NDA. We also prove that the class of NDAs with integral discount factors enjoys
closure under the algebraic operations min, max, addition, and subtraction, which
is not the case for general NDAs nor for deterministic NDAs. For general NDAs,
we look into approximate determinization, which is always possible as the influence
of a word''s suffix decays. We show that the naive approach, of unfolding the
automaton computations up to a sufficient level, is doubly exponential in the
discount factor. We provide an alternative construction for approximate determinization,
which is singly exponential in the discount factor, in the precision, and in the
number of states. We also prove matching lower bounds, showing that the exponential
dependency on each of these three parameters cannot be avoided. All our results
hold equally for automata over finite words and for automata over infinite words. '
author:
- first_name: Udi
full_name: Boker, Udi
last_name: Boker
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Boker U, Henzinger TA. Exact and approximate determinization of discounted-sum
automata. Logical Methods in Computer Science. 2014;10(1). doi:10.2168/LMCS-10(1:10)2014
apa: Boker, U., & Henzinger, T. A. (2014). Exact and approximate determinization
of discounted-sum automata. Logical Methods in Computer Science. International
Federation of Computational Logic. https://doi.org/10.2168/LMCS-10(1:10)2014
chicago: Boker, Udi, and Thomas A Henzinger. “Exact and Approximate Determinization
of Discounted-Sum Automata.” Logical Methods in Computer Science. International
Federation of Computational Logic, 2014. https://doi.org/10.2168/LMCS-10(1:10)2014.
ieee: U. Boker and T. A. Henzinger, “Exact and approximate determinization of discounted-sum
automata,” Logical Methods in Computer Science, vol. 10, no. 1. International
Federation of Computational Logic, 2014.
ista: Boker U, Henzinger TA. 2014. Exact and approximate determinization of discounted-sum
automata. Logical Methods in Computer Science. 10(1).
mla: Boker, Udi, and Thomas A. Henzinger. “Exact and Approximate Determinization
of Discounted-Sum Automata.” Logical Methods in Computer Science, vol.
10, no. 1, International Federation of Computational Logic, 2014, doi:10.2168/LMCS-10(1:10)2014.
short: U. Boker, T.A. Henzinger, Logical Methods in Computer Science 10 (2014).
date_created: 2018-12-11T11:56:28Z
date_published: 2014-02-13T00:00:00Z
date_updated: 2021-01-12T06:56:11Z
day: '13'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.2168/LMCS-10(1:10)2014
ec_funded: 1
file:
- access_level: open_access
checksum: 9f6ea2e2d8d4a32ff0becc29d835bbf8
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:45Z
date_updated: 2020-07-14T12:45:34Z
file_id: '4643'
file_name: IST-2015-389-v1+1_1401.3957.pdf
file_size: 550936
relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Logical Methods in Computer Science
publication_identifier:
issn:
- '18605974'
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '4728'
pubrep_id: '389'
quality_controlled: '1'
scopus_import: 1
status: public
title: Exact and approximate determinization of discounted-sum automata
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10
year: '2014'
...
---
_id: '2239'
abstract:
- lang: eng
text: The analysis of the energy consumption of software is an important goal for
quantitative formal methods. Current methods, using weighted transition systems
or energy games, model the energy source as an ideal resource whose status is
characterized by one number, namely the amount of remaining energy. Real batteries,
however, exhibit behaviors that can deviate substantially from an ideal energy
resource. Based on a discretization of a standard continuous battery model, we
introduce battery transition systems. In this model, a battery is viewed as consisting
of two parts-the available-charge tank and the bound-charge tank. Any charge or
discharge is applied to the available-charge tank. Over time, the energy from
each tank diffuses to the other tank. Battery transition systems are infinite
state systems that, being not well-structured, fall into no decidable class that
is known to us. Nonetheless, we are able to prove that the !-regular modelchecking
problem is decidable for battery transition systems. We also present a case study
on the verification of control programs for energy-constrained semi-autonomous
robots.
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: 'Boker U, Henzinger TA, Radhakrishna A. Battery transition systems. In: Vol
49. ACM; 2014:595-606. doi:10.1145/2535838.2535875'
apa: 'Boker, U., Henzinger, T. A., & Radhakrishna, A. (2014). Battery transition
systems (Vol. 49, pp. 595–606). Presented at the POPL: Principles of Programming
Languages, San Diego, USA: ACM. https://doi.org/10.1145/2535838.2535875'
chicago: Boker, Udi, Thomas A Henzinger, and Arjun Radhakrishna. “Battery Transition
Systems,” 49:595–606. ACM, 2014. https://doi.org/10.1145/2535838.2535875.
ieee: 'U. Boker, T. A. Henzinger, and A. Radhakrishna, “Battery transition systems,”
presented at the POPL: Principles of Programming Languages, San Diego, USA, 2014,
vol. 49, no. 1, pp. 595–606.'
ista: 'Boker U, Henzinger TA, Radhakrishna A. 2014. Battery transition systems.
POPL: Principles of Programming Languages vol. 49, 595–606.'
mla: Boker, Udi, et al. Battery Transition Systems. Vol. 49, no. 1, ACM,
2014, pp. 595–606, doi:10.1145/2535838.2535875.
short: U. Boker, T.A. Henzinger, A. Radhakrishna, in:, ACM, 2014, pp. 595–606.
conference:
end_date: 2014-01-24
location: San Diego, USA
name: 'POPL: Principles of Programming Languages'
start_date: 2014-01-22
date_created: 2018-12-11T11:56:30Z
date_published: 2014-01-13T00:00:00Z
date_updated: 2021-01-12T06:56:13Z
day: '13'
department:
- _id: ToHe
doi: 10.1145/2535838.2535875
ec_funded: 1
intvolume: ' 49'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 595 - 606
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_identifier:
isbn:
- 978-145032544-8
publication_status: published
publisher: ACM
publist_id: '4722'
quality_controlled: '1'
scopus_import: 1
status: public
title: Battery transition systems
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2014'
...
---
_id: '1733'
abstract:
- lang: eng
text: The classical (boolean) notion of refinement for behavioral interfaces of
system components is the alternating refinement preorder. In this paper, we define
a distance for interfaces, called interface simulation distance. It makes the
alternating refinement preorder quantitative by, intuitively, tolerating errors
(while counting them) in the alternating simulation game. We show that the interface
simulation distance satisfies the triangle inequality, that the distance between
two interfaces does not increase under parallel composition with a third interface,
that the distance between two interfaces can be bounded from above and below by
distances between abstractions of the two interfaces, and how to synthesize an
interface from incompatible requirements. We illustrate the framework, and the
properties of the distances under composition of interfaces, with two case studies.
author:
- first_name: Pavol
full_name: Cerny, Pavol
last_name: Cerny
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- 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
citation:
ama: Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. Interface simulation distances.
Theoretical Computer Science. 2014;560(3):348-363. doi:10.1016/j.tcs.2014.08.019
apa: Cerny, P., Chmelik, M., Henzinger, T. A., & Radhakrishna, A. (2014). Interface
simulation distances. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2014.08.019
chicago: Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna.
“Interface Simulation Distances.” Theoretical Computer Science. Elsevier,
2014. https://doi.org/10.1016/j.tcs.2014.08.019.
ieee: P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface simulation
distances,” Theoretical Computer Science, vol. 560, no. 3. Elsevier, pp.
348–363, 2014.
ista: Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2014. Interface simulation
distances. Theoretical Computer Science. 560(3), 348–363.
mla: Cerny, Pavol, et al. “Interface Simulation Distances.” Theoretical Computer
Science, vol. 560, no. 3, Elsevier, 2014, pp. 348–63, doi:10.1016/j.tcs.2014.08.019.
short: P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer
Science 560 (2014) 348–363.
date_created: 2018-12-11T11:53:43Z
date_published: 2014-12-04T00:00:00Z
date_updated: 2023-02-23T11:04:00Z
day: '04'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1016/j.tcs.2014.08.019
ec_funded: 1
intvolume: ' 560'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1210.2450
month: '12'
oa: 1
oa_version: Submitted Version
page: 348 - 363
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: 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: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '5392'
quality_controlled: '1'
related_material:
record:
- id: '2916'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Interface simulation distances
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 560
year: '2014'
...
---
_id: '2038'
abstract:
- lang: eng
text: Recently, there has been an effort to add quantitative objectives to formal
verification and synthesis. We introduce and investigate the extension of temporal
logics with quantitative atomic assertions. At the heart of quantitative objectives
lies the accumulation of values along a computation. It is often the accumulated
sum, as with energy objectives, or the accumulated average, as with mean-payoff
objectives. We investigate the extension of temporal logics with the prefix-accumulation
assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric (or Boolean) variable
of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the
accumulated sum and average of the values of v from the beginning of the computation
up to the current point in time. We also allow the path-accumulation assertions
LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an
entire infinite computation. We study the border of decidability for such quantitative
extensions of various temporal logics. In particular, we show that extending the
fragment of CTL that has only the EX, EF, AX, and AG temporal modalities with
both prefix-accumulation assertions, or extending LTL with both path-accumulation
assertions, results in temporal logics whose model-checking problem is decidable.
Moreover, the prefix-accumulation assertions may be generalized with "controlled
accumulation," allowing, for example, to specify constraints on the average
waiting time between a request and a grant. On the negative side, we show that
this branching-time logic is, in a sense, the maximal logic with one or both of
the prefix-accumulation assertions that permits a decidable model-checking procedure.
Extending a temporal logic that has the EG or EU modalities, such as CTL or LTL,
makes the problem undecidable.
acknowledgement: The research was supported in part by ERC Starting grant 278410 (QUALITY).
article_number: '27'
article_processing_charge: No
article_type: original
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Boker U, Chatterjee K, Henzinger TA, Kupferman O. Temporal specifications with
accumulative values. ACM Transactions on Computational Logic (TOCL). 2014;15(4).
doi:10.1145/2629686
apa: Boker, U., Chatterjee, K., Henzinger, T. A., & Kupferman, O. (2014). Temporal
specifications with accumulative values. ACM Transactions on Computational
Logic (TOCL). ACM. https://doi.org/10.1145/2629686
chicago: Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman.
“Temporal Specifications with Accumulative Values.” ACM Transactions on Computational
Logic (TOCL). ACM, 2014. https://doi.org/10.1145/2629686.
ieee: U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, “Temporal specifications
with accumulative values,” ACM Transactions on Computational Logic (TOCL),
vol. 15, no. 4. ACM, 2014.
ista: Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2014. Temporal specifications
with accumulative values. ACM Transactions on Computational Logic (TOCL). 15(4),
27.
mla: Boker, Udi, et al. “Temporal Specifications with Accumulative Values.” ACM
Transactions on Computational Logic (TOCL), vol. 15, no. 4, 27, ACM, 2014,
doi:10.1145/2629686.
short: U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on
Computational Logic (TOCL) 15 (2014).
date_created: 2018-12-11T11:55:21Z
date_published: 2014-09-16T00:00:00Z
date_updated: 2023-02-23T12:23:54Z
day: '16'
ddc:
- '000'
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1145/2629686
ec_funded: 1
file:
- access_level: open_access
checksum: 354c41d37500b56320afce94cf9a99c2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:59Z
date_updated: 2020-07-14T12:45:26Z
file_id: '4851'
file_name: IST-2014-192-v1+1_AccumulativeValues.pdf
file_size: 346184
relation: main_file
file_date_updated: 2020-07-14T12:45:26Z
has_accepted_license: '1'
intvolume: ' 15'
issue: '4'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _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: 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: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: ACM Transactions on Computational Logic (TOCL)
publication_status: published
publisher: ACM
publist_id: '5013'
pubrep_id: '192'
quality_controlled: '1'
related_material:
record:
- id: '3356'
relation: earlier_version
status: public
- id: '5385'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Temporal specifications with accumulative values
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2014'
...
---
_id: '5411'
abstract:
- lang: eng
text: "Model-based testing is a promising technology for black-box software and
hardware testing, in which test cases are generated automatically from high-level
specifications. Nowadays, systems typically consist of multiple interacting components
and, due to their complexity, testing presents a considerable portion of the effort
and cost in the design process. Exploiting the compositional structure of system
specifications can considerably reduce the effort in model-based testing. Moreover,
inferring properties about the system from testing its individual components allows
the designer to reduce the amount of integration testing.\r\nIn this paper, we
study compositional properties of the IOCO-testing theory. We propose a new approach
to composition and hiding operations, inspired by contract-based design and interface
theories. These operations preserve behaviors that are compatible under composition
and hiding, and prune away incompatible ones. The resulting specification characterizes
the input sequences for which the unit testing of components is sufficient to
infer the correctness of component integration without the need for further tests.
We provide a methodology that uses these results to minimize integration testing
effort, but also to detect potential weaknesses in specifications. While we focus
on asynchronous models and the IOCO conformance relation, the resulting methodology
can be applied to a broader class of systems."
alternative_title:
- IST Austria Technical Report
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: Willibald
full_name: Krenn, Willibald
last_name: Krenn
- first_name: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
citation:
ama: Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional Specifications
for IOCO Testing. IST Austria; 2014. doi:10.15479/AT:IST-2014-148-v2-1
apa: Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional
specifications for IOCO testing. IST Austria. https://doi.org/10.15479/AT:IST-2014-148-v2-1
chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic.
Compositional Specifications for IOCO Testing. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-148-v2-1.
ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, Compositional specifications
for IOCO testing. IST Austria, 2014.
ista: Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications
for IOCO testing, IST Austria, 20p.
mla: Daca, Przemyslaw, et al. Compositional Specifications for IOCO Testing.
IST Austria, 2014, doi:10.15479/AT:IST-2014-148-v2-1.
short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications
for IOCO Testing, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-01-28T00:00:00Z
date_updated: 2023-02-23T10:31:07Z
day: '28'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-148-v2-1
file:
- access_level: open_access
checksum: 0e03aba625cc334141a3148432aa5760
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:21Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5543'
file_name: IST-2014-148-v2+1_main_tr.pdf
file_size: 534732
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '152'
related_material:
record:
- id: '2167'
relation: later_version
status: public
status: public
title: Compositional specifications for IOCO testing
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2217'
abstract:
- lang: eng
text: "As hybrid systems involve continuous behaviors, they should be evaluated
by quantitative methods, rather than qualitative methods. In this paper we adapt
a quantitative framework, called model measuring, to the hybrid systems domain.
The model-measuring problem asks, given a model M and a specification, what is
the maximal distance such that all models within that distance from M satisfy
(or violate) the specification. A distance function on models is given as part
of the input of the problem. Distances, especially related to continuous behaviors
are more natural in the hybrid case than the discrete case. We are interested
in distances represented by monotonic hybrid automata, a hybrid counterpart of
(discrete) weighted automata, whose recognized timed languages are monotone (w.r.t.
inclusion) in the values of parameters.\r\n\r\nThe contributions of this paper
are twofold. First, we give sufficient conditions under which the model-measuring
problem can be solved. Second, we discuss the modeling of distances and applications
of the model-measuring problem."
acknowledgement: "This work was supported in part by the Austrian Science
Fund NFN RiSE (Rigorous Systems Engineering) and by the ERC Advanced Grant
QUAREM (Quantitative Reactive Modeling).\r\nA Technical Report of this paper is
available at: \r\nhttps://repository.ist.ac.at/id/eprint/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 hybrid systems. In: Proceedings
of the 17th International Conference on Hybrid Systems: Computation and Control.
Springer; 2014:213-222. doi:10.1145/2562059.2562130'
apa: 'Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems.
In Proceedings of the 17th international conference on Hybrid systems: computation
and control (pp. 213–222). Berlin, Germany: Springer. https://doi.org/10.1145/2562059.2562130'
chicago: 'Henzinger, Thomas A, and Jan Otop. “Model Measuring for Hybrid Systems.”
In Proceedings of the 17th International Conference on Hybrid Systems: Computation
and Control, 213–22. Springer, 2014. https://doi.org/10.1145/2562059.2562130.'
ieee: 'T. A. Henzinger and J. Otop, “Model measuring for hybrid systems,” in Proceedings
of the 17th international conference on Hybrid systems: computation and control,
Berlin, Germany, 2014, pp. 213–222.'
ista: 'Henzinger TA, Otop J. 2014. Model measuring for hybrid systems. Proceedings
of the 17th international conference on Hybrid systems: computation and control.
HSCC: Hybrid Systems - Computation and Control, 213–222.'
mla: 'Henzinger, Thomas A., and Jan Otop. “Model Measuring for Hybrid Systems.”
Proceedings of the 17th International Conference on Hybrid Systems: Computation
and Control, Springer, 2014, pp. 213–22, doi:10.1145/2562059.2562130.'
short: 'T.A. Henzinger, J. Otop, in:, Proceedings of the 17th International Conference
on Hybrid Systems: Computation and Control, Springer, 2014, pp. 213–222.'
conference:
end_date: 2014-04-17
location: Berlin, Germany
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2014-04-15
date_created: 2018-12-11T11:56:23Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2023-02-23T12:25:23Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2562059.2562130
ec_funded: 1
language:
- iso: eng
month: '04'
oa_version: None
page: 213 - 222
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
publication: 'Proceedings of the 17th international conference on Hybrid systems:
computation and control'
publication_status: published
publisher: Springer
publist_id: '4751'
quality_controlled: '1'
related_material:
record:
- id: '5416'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Model measuring for hybrid systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5417'
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.\r\nThe 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, and robustness
problems that measure how much a model can be perturbed without violating the
specification.\r\nWe show that for automatic distance functions, and ω-regular
linear-time and branching-time specifications, the model-measuring problem can
be solved.\r\nWe use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for standard word and tree automata by the optimal-weight
question for the weighted versions of these automata. We consider weighted automata
that accumulate weights by maximizing, summing, discounting, and limit averaging.
\r\nWe give several examples of using the model-measuring problem to compute various
notions of robustness and quantitative satisfaction for temporal specifications."
alternative_title:
- IST Austria Technical Report
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. From Model Checking to Model Measuring. IST Austria;
2014. doi:10.15479/AT:IST-2014-172-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). From model checking to model measuring.
IST Austria. https://doi.org/10.15479/AT:IST-2014-172-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-172-v1-1.
ieee: T. A. Henzinger and J. Otop, From model checking to model measuring.
IST Austria, 2014.
ista: Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria,
14p.
mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014, doi:10.15479/AT:IST-2014-172-v1-1.
short: T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria,
2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:38:10Z
day: '19'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-172-v1-1
file:
- access_level: open_access
checksum: fcc3eab903cfcd3778b338d2d0d44d18
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:20Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5481'
file_name: IST-2014-172-v1+1_report.pdf
file_size: 383052
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '14'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '175'
related_material:
record:
- id: '2327'
relation: later_version
status: public
status: public
title: From model checking to model measuring
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5416'
abstract:
- lang: eng
text: As hybrid systems involve continuous behaviors, they should be evaluated by
quantitative methods, rather than qualitative methods. In this paper we adapt
a quantitative framework, called model measuring, to the hybrid systems domain.
The model-measuring problem asks, given a model M and a specification, what is
the maximal distance such that all models within that distance from M satisfy
(or violate) the specification. A distance function on models is given as part
of the input of the problem. Distances, especially related to continuous behaviors
are more natural in the hybrid case than the discrete case. We are interested
in distances represented by monotonic hybrid automata, a hybrid counterpart of
(discrete) weighted automata, whose recognized timed languages are monotone (w.r.t.
inclusion) in the values of parameters.The contributions of this paper are twofold.
First, we give sufficient conditions under which the model-measuring problem can
be solved. Second, we discuss the modeling of distances and applications of the
model-measuring problem.
alternative_title:
- IST Austria Technical Report
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 Hybrid Systems. IST Austria;
2014. doi:10.15479/AT:IST-2014-171-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems.
IST Austria. https://doi.org/10.15479/AT:IST-2014-171-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-171-v1-1.
ieee: T. A. Henzinger and J. Otop, Model measuring for hybrid systems. IST
Austria, 2014.
ista: Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria,
22p.
mla: Henzinger, Thomas A., and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014, doi:10.15479/AT:IST-2014-171-v1-1.
short: T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria,
2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:33:21Z
day: '19'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-171-v1-1
file:
- access_level: open_access
checksum: 445456d22371e4e49aad2b9a0c13bf80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:32Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5492'
file_name: IST-2014-171-v1+1_report.pdf
file_size: 712077
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '171'
related_material:
record:
- id: '2217'
relation: later_version
status: public
status: public
title: Model measuring for hybrid systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5415'
abstract:
- lang: eng
text: 'Recently there has been a significant effort to add quantitative properties
in formal verification and synthesis. While weighted automata over finite and
infinite words provide a natural and flexible framework to express quantitative
properties, perhaps surprisingly, several basic system properties such as average
response time cannot be expressed with weighted automata. In this work, we introduce
nested weighted automata as a new formalism for expressing important quantitative
properties such as average response time. We establish an almost complete decidability
picture for the basic decision problems for nested weighted automata, and illustrate
its applicability in several domains. '
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria;
2014. doi:10.15479/AT:IST-2014-170-v1-1
apa: Chatterjee, K., Henzinger, T. A., & Otop, J. (2014). Nested weighted
automata. IST Austria. https://doi.org/10.15479/AT:IST-2014-170-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted
Automata. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-170-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata.
IST Austria, 2014.
ista: Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria,
27p.
mla: Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria,
2014, doi:10.15479/AT:IST-2014-170-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria,
2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T12:26:19Z
day: '19'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2014-170-v1-1
file:
- access_level: open_access
checksum: 31f90dcf2cf899c3f8c6427cfcc2b3c7
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:36Z
date_updated: 2020-07-14T12:46:48Z
file_id: '5497'
file_name: IST-2014-170-v1+1_main.pdf
file_size: 573457
relation: main_file
file_date_updated: 2020-07-14T12:46:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '170'
related_material:
record:
- id: '1656'
relation: later_version
status: public
- id: '467'
relation: later_version
status: public
- id: '5436'
relation: later_version
status: public
status: public
title: Nested weighted automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2218'
abstract:
- lang: eng
text: While fixing concurrency bugs, program repair algorithms may introduce new
concurrency bugs. We present an algorithm that avoids such regressions. The solution
space is given by a set of program transformations we consider in the repair process.
These include reordering of instructions within a thread and inserting atomic
sections. The new algorithm learns a constraint on the space of candidate solutions,
from both positive examples (error-free traces) and counterexamples (error traces).
From each counterexample, the algorithm learns a constraint necessary to remove
the errors. From each positive examples, it learns a constraint that is necessary
in order to prevent the repair from turning the trace into an error trace. We
implemented the algorithm and evaluated it on simplified Linux device drivers
with known bugs.
alternative_title:
- LNCS
author:
- first_name: Pavol
full_name: Cerny, Pavol
last_name: Cerny
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- 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: Thorsten
full_name: Tarrach, Thorsten
id: 3D6E8F2C-F248-11E8-B48F-1D18A9856A87
last_name: Tarrach
orcid: 0000-0003-4409-8487
citation:
ama: 'Cerny P, Henzinger TA, Radhakrishna A, Ryzhyk L, Tarrach T. Regression-free
synthesis for concurrency. In: Vol 8559. Springer; 2014:568-584. doi:10.1007/978-3-319-08867-9_38'
apa: 'Cerny, P., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., & Tarrach,
T. (2014). Regression-free synthesis for concurrency (Vol. 8559, pp. 568–584).
Presented at the CAV: Computer Aided Verification, Vienna, Austria: Springer.
https://doi.org/10.1007/978-3-319-08867-9_38'
chicago: Cerny, Pavol, Thomas A Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, and
Thorsten Tarrach. “Regression-Free Synthesis for Concurrency,” 8559:568–84. Springer,
2014. https://doi.org/10.1007/978-3-319-08867-9_38.
ieee: 'P. Cerny, T. A. Henzinger, A. Radhakrishna, L. Ryzhyk, and T. Tarrach, “Regression-free
synthesis for concurrency,” presented at the CAV: Computer Aided Verification,
Vienna, Austria, 2014, vol. 8559, pp. 568–584.'
ista: 'Cerny P, Henzinger TA, Radhakrishna A, Ryzhyk L, Tarrach T. 2014. Regression-free
synthesis for concurrency. CAV: Computer Aided Verification, LNCS, vol. 8559,
568–584.'
mla: Cerny, Pavol, et al. Regression-Free Synthesis for Concurrency. Vol.
8559, Springer, 2014, pp. 568–84, doi:10.1007/978-3-319-08867-9_38.
short: P. Cerny, T.A. Henzinger, A. Radhakrishna, L. Ryzhyk, T. Tarrach, in:, Springer,
2014, pp. 568–584.
conference:
end_date: 2014-07-22
location: Vienna, Austria
name: 'CAV: Computer Aided Verification'
start_date: 2014-07-18
date_created: 2018-12-11T11:56:23Z
date_published: 2014-07-22T00:00:00Z
date_updated: 2023-09-07T11:57:01Z
day: '22'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-319-08867-9_38
ec_funded: 1
file:
- access_level: open_access
checksum: a631d3105509f239724644e77a1212e2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:14Z
date_updated: 2020-07-14T12:45:33Z
file_id: '4995'
file_name: IST-2014-297-v1+1_cav14-final.pdf
file_size: 416732
relation: main_file
- access_level: open_access
checksum: f8b0f748cc9fa697ca992cc56c87bc4e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:15Z
date_updated: 2020-07-14T12:45:33Z
file_id: '4996'
file_name: IST-2014-297-v2+1_cav14-final2.pdf
file_size: 616293
relation: main_file
file_date_updated: 2020-07-14T12:45:33Z
has_accepted_license: '1'
intvolume: ' 8559'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://link.springer.com/chapter/10.1007%2F978-3-319-08867-9_38
month: '07'
oa: 1
oa_version: Submitted Version
page: 568 - 584
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication_identifier:
isbn:
- 978-331908866-2
publication_status: published
publisher: Springer
publist_id: '4749'
pubrep_id: '297'
quality_controlled: '1'
related_material:
record:
- id: '1130'
relation: dissertation_contains
status: public
status: public
title: Regression-free synthesis for concurrency
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8559
year: '2014'
...
---
_id: '2167'
abstract:
- lang: eng
text: Model-based testing is a promising technology for black-box software and hardware
testing, in which test cases are generated automatically from high-level specifications.
Nowadays, systems typically consist of multiple interacting components and, due
to their complexity, testing presents a considerable portion of the effort and
cost in the design process. Exploiting the compositional structure of system specifications
can considerably reduce the effort in model-based testing. Moreover, inferring
properties about the system from testing its individual components allows the
designer to reduce the amount of integration testing. In this paper, we study
compositional properties of the ioco-testing theory. We propose a new approach
to composition and hiding operations, inspired by contract-based design and interface
theories. These operations preserve behaviors that are compatible under composition
and hiding, and prune away incompatible ones. The resulting specification characterizes
the input sequences for which the unit testing of components is sufficient to
infer the correctness of component integration without the need for further tests.
We provide a methodology that uses these results to minimize integration testing
effort, but also to detect potential weaknesses in specifications. While we focus
on asynchronous models and the ioco conformance relation, the resulting methodology
can be applied to a broader class of systems.
article_number: '6823899'
article_processing_charge: No
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: Willibald
full_name: Krenn, Willibald
last_name: Krenn
- first_name: Dejan
full_name: Nickovic, Dejan
last_name: Nickovic
citation:
ama: 'Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional specifications for
IOCO testing. In: IEEE 7th International Conference on Software Testing, Verification
and Validation. IEEE; 2014. doi:10.1109/ICST.2014.50'
apa: 'Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional
specifications for IOCO testing. In IEEE 7th International Conference on Software
Testing, Verification and Validation. Cleveland, USA: IEEE. https://doi.org/10.1109/ICST.2014.50'
chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic.
“Compositional Specifications for IOCO Testing.” In IEEE 7th International
Conference on Software Testing, Verification and Validation. IEEE, 2014. https://doi.org/10.1109/ICST.2014.50.
ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, “Compositional specifications
for IOCO testing,” in IEEE 7th International Conference on Software Testing,
Verification and Validation, Cleveland, USA, 2014.
ista: 'Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications
for IOCO testing. IEEE 7th International Conference on Software Testing, Verification
and Validation. ICST: International Conference on Software Testing, Verification
and Validation, 6823899.'
mla: Daca, Przemyslaw, et al. “Compositional Specifications for IOCO Testing.” IEEE
7th International Conference on Software Testing, Verification and Validation,
6823899, IEEE, 2014, doi:10.1109/ICST.2014.50.
short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, in:, IEEE 7th International
Conference on Software Testing, Verification and Validation, IEEE, 2014.
conference:
end_date: 2014-04-04
location: Cleveland, USA
name: 'ICST: International Conference on Software Testing, Verification and Validation'
start_date: 2014-03-31
date_created: 2018-12-11T11:56:06Z
date_published: 2014-03-01T00:00:00Z
date_updated: 2023-09-07T11:58:33Z
day: '01'
department:
- _id: ToHe
doi: 10.1109/ICST.2014.50
ec_funded: 1
external_id:
arxiv:
- '1904.07083'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1904.07083
month: '03'
oa: 1
oa_version: Preprint
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: IEEE 7th International Conference on Software Testing, Verification and
Validation
publication_identifier:
isbn:
- 978-1-4799-2255-0
issn:
- 2159-4848
publication_status: published
publisher: IEEE
publist_id: '4817'
quality_controlled: '1'
related_material:
record:
- id: '5411'
relation: earlier_version
status: public
- id: '1155'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Compositional specifications for IOCO testing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2063'
abstract:
- lang: eng
text: We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems.We focus on qualitative properties forMDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability. We introduce a new simulation relation to capture
the refinement relation ofMDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.We present an automated technique for assume-guarantee style reasoning
for compositional analysis ofMDPs with qualitative properties by giving a counterexample
guided abstraction-refinement approach to compute our new simulation relation.
We have implemented our algorithms and show that the compositional analysis leads
to significant improvements.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
citation:
ama: 'Chatterjee K, Chmelik M, Daca P. CEGAR for qualitative analysis of probabilistic
systems. In: Vol 8559. Springer; 2014:473-490. doi:10.1007/978-3-319-08867-9_31'
apa: 'Chatterjee, K., Chmelik, M., & Daca, P. (2014). CEGAR for qualitative
analysis of probabilistic systems (Vol. 8559, pp. 473–490). Presented at the CAV:
Computer Aided Verification, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-319-08867-9_31'
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for
Qualitative Analysis of Probabilistic Systems,” 8559:473–90. Springer, 2014. https://doi.org/10.1007/978-3-319-08867-9_31.
ieee: 'K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for qualitative analysis of
probabilistic systems,” presented at the CAV: Computer Aided Verification, Vienna,
Austria, 2014, vol. 8559, pp. 473–490.'
ista: 'Chatterjee K, Chmelik M, Daca P. 2014. CEGAR for qualitative analysis of
probabilistic systems. CAV: Computer Aided Verification, LNCS, vol. 8559, 473–490.'
mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic
Systems. Vol. 8559, Springer, 2014, pp. 473–90, doi:10.1007/978-3-319-08867-9_31.
short: K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490.
conference:
end_date: 2014-07-22
location: Vienna, Austria
name: 'CAV: Computer Aided Verification'
start_date: 2014-07-18
date_created: 2018-12-11T11:55:30Z
date_published: 2014-07-01T00:00:00Z
date_updated: 2023-09-07T11:58:33Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-319-08867-9_31
ec_funded: 1
intvolume: ' 8559'
language:
- iso: eng
month: '07'
oa_version: None
page: 473 - 490
project:
- _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
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '4978'
quality_controlled: '1'
related_material:
record:
- id: '5412'
relation: earlier_version
status: public
- id: '5413'
relation: earlier_version
status: public
- id: '5414'
relation: earlier_version
status: public
- id: '1155'
relation: dissertation_contains
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8559
year: '2014'
...
---
_id: '5428'
abstract:
- lang: eng
text: "Simulation is an attractive alternative for language inclusion for automata
as it is an under-approximation of language inclusion, but usually has much lower
complexity. For non-deterministic automata, while language inclusion is PSPACE-complete,
simulation can be computed in polynomial time. 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. Again, 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 for mean-payoff automata
and the decidability is open for discounted-sum automata, whereas the (quantitative)
simulation reduce to mean-payoff games and discounted-sum 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. For example, whereas for mean-payoff and discounted-sum games, the players
do not need memory to play optimally; we show in contrast that for simulation
games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal
strategies for both players require infinite memory in general, and (ii) for discounted-sum
objectives, optimal strategies need not exist for both players. While the simulation
games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory
requirements for mean-payoff objectives) as compared to their counterpart without
Büchi acceptance conditions, we still present pseudo-polynomial time algorithms
to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff
and weighted discounted-sum automata."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: 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. IST Austria; 2014. doi:10.15479/AT:IST-2014-315-v1-1
apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Velner, Y. (2014). Quantitative
fair simulation games. IST Austria. https://doi.org/10.15479/AT:IST-2014-315-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner.
Quantitative Fair Simulation Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-315-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, Quantitative fair
simulation games. IST Austria, 2014.
ista: Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation
games, IST Austria, 26p.
mla: Chatterjee, Krishnendu, et al. Quantitative Fair Simulation Games. IST
Austria, 2014, doi:10.15479/AT:IST-2014-315-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation
Games, IST Austria, 2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-12-05T00:00:00Z
date_updated: 2023-09-20T12:07:48Z
day: '05'
ddc:
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.15479/AT:IST-2014-315-v1-1
file:
- access_level: open_access
checksum: b1d573bc04365625ff9974880c0aa807
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:59Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5521'
file_name: IST-2014-315-v1+1_report.pdf
file_size: 531046
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '26'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '315'
related_material:
record:
- id: '1066'
relation: later_version
status: public
status: public
title: Quantitative fair simulation games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '10898'
abstract:
- lang: eng
text: A prominent remedy to multicore scalability issues in concurrent data structure
implementations is to relax the sequential specification of the data structure.
We present distributed queues (DQ), a new family of relaxed concurrent queue implementations.
DQs implement relaxed queues with linearizable emptiness check and either configurable
or bounded out-of-order behavior or pool behavior. Our experiments show that DQs
outperform and outscale in micro- and macrobenchmarks all strict and relaxed queue
as well as pool implementations that we considered.
article_number: '17'
article_processing_charge: No
author:
- first_name: Andreas
full_name: Haas, Andreas
last_name: Haas
- first_name: Michael
full_name: Lippautz, Michael
last_name: Lippautz
- 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: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
- first_name: Christoph M.
full_name: Kirsch, Christoph M.
last_name: Kirsch
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
citation:
ama: 'Haas A, Lippautz M, Henzinger TA, et al. Distributed queues in shared memory:
Multicore performance and scalability through quantitative relaxation. In: Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. ACM Press;
2013. doi:10.1145/2482767.2482789'
apa: 'Haas, A., Lippautz, M., Henzinger, T. A., Payer, H., Sokolova, A., Kirsch,
C. M., & Sezgin, A. (2013). Distributed queues in shared memory: Multicore
performance and scalability through quantitative relaxation. In Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. Ischia,
Italy: ACM Press. https://doi.org/10.1145/2482767.2482789'
chicago: 'Haas, Andreas, Michael Lippautz, Thomas A Henzinger, Hannes Payer, Ana
Sokolova, Christoph M. Kirsch, and Ali Sezgin. “Distributed Queues in Shared Memory:
Multicore Performance and Scalability through Quantitative Relaxation.” In Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. ACM Press,
2013. https://doi.org/10.1145/2482767.2482789.'
ieee: 'A. Haas et al., “Distributed queues in shared memory: Multicore performance
and scalability through quantitative relaxation,” in Proceedings of the ACM
International Conference on Computing Frontiers - CF ’13, Ischia, Italy, 2013,
no. 5.'
ista: 'Haas A, Lippautz M, Henzinger TA, Payer H, Sokolova A, Kirsch CM, Sezgin
A. 2013. Distributed queues in shared memory: Multicore performance and scalability
through quantitative relaxation. Proceedings of the ACM International Conference
on Computing Frontiers - CF ’13. CF: Conference on Computing Frontiers, 17.'
mla: 'Haas, Andreas, et al. “Distributed Queues in Shared Memory: Multicore Performance
and Scalability through Quantitative Relaxation.” Proceedings of the ACM International
Conference on Computing Frontiers - CF ’13, no. 5, 17, ACM Press, 2013, doi:10.1145/2482767.2482789.'
short: A. Haas, M. Lippautz, T.A. Henzinger, H. Payer, A. Sokolova, C.M. Kirsch,
A. Sezgin, in:, Proceedings of the ACM International Conference on Computing Frontiers
- CF ’13, ACM Press, 2013.
conference:
end_date: 2013-05-16
location: Ischia, Italy
name: 'CF: Conference on Computing Frontiers'
start_date: 2013-05-14
date_created: 2022-03-21T07:33:22Z
date_published: 2013-05-01T00:00:00Z
date_updated: 2022-06-21T08:01:19Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2482767.2482789
issue: '5'
language:
- iso: eng
month: '05'
oa_version: None
publication: Proceedings of the ACM International Conference on Computing Frontiers
- CF '13
publication_identifier:
isbn:
- 978-145032053-5
publication_status: published
publisher: ACM Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Distributed queues in shared memory: Multicore performance and scalability
through quantitative relaxation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1385'
abstract:
- lang: eng
text: It is often difficult to correctly implement a Boolean controller for a complex
system, especially when concurrency is involved. Yet, it may be easy to formally
specify a controller. For instance, for a pipelined processor it suffices to state
that the visible behavior of the pipelined system should be identical to a non-pipelined
reference system (Burch-Dill paradigm). We present a novel procedure to efficiently
synthesize multiple Boolean control signals from a specification given as a quantified
first-order formula (with a specific quantifier structure). Our approach uses
uninterpreted functions to abstract details of the design. We construct an unsatisfiable
SMT formula from the given specification. Then, from just one proof of unsatisfiability,
we use a variant of Craig interpolation to compute multiple coordinated interpolants
that implement the Boolean control signals. Our method avoids iterative learning
and back-substitution of the control functions. We applied our approach to synthesize
a controller for a simple two-stage pipelined processor, and present first experimental
results.
acknowledgement: "This research was supported by the European Commission through project\r\nDIAMOND
\ (FP7-2009-IST-4-248613), and QUAINT (I774-N23), "
author:
- first_name: Georg
full_name: Hofferek, Georg
last_name: Hofferek
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Bettina
full_name: Könighofer, Bettina
last_name: Könighofer
- first_name: Jie
full_name: Jiang, Jie
last_name: Jiang
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
citation:
ama: 'Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. Synthesizing multiple
boolean functions using interpolation on a single proof. In: 2013 Formal Methods
in Computer-Aided Design. IEEE; 2013:77-84. doi:10.1109/FMCAD.2013.6679394'
apa: 'Hofferek, G., Gupta, A., Könighofer, B., Jiang, J., & Bloem, R. (2013).
Synthesizing multiple boolean functions using interpolation on a single proof.
In 2013 Formal Methods in Computer-Aided Design (pp. 77–84). Portland,
OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679394'
chicago: Hofferek, Georg, Ashutosh Gupta, Bettina Könighofer, Jie Jiang, and Roderick
Bloem. “Synthesizing Multiple Boolean Functions Using Interpolation on a Single
Proof.” In 2013 Formal Methods in Computer-Aided Design, 77–84. IEEE, 2013.
https://doi.org/10.1109/FMCAD.2013.6679394.
ieee: G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, and R. Bloem, “Synthesizing
multiple boolean functions using interpolation on a single proof,” in 2013
Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013,
pp. 77–84.
ista: 'Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. 2013. Synthesizing multiple
boolean functions using interpolation on a single proof. 2013 Formal Methods in
Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 77–84.'
mla: Hofferek, Georg, et al. “Synthesizing Multiple Boolean Functions Using Interpolation
on a Single Proof.” 2013 Formal Methods in Computer-Aided Design, IEEE,
2013, pp. 77–84, doi:10.1109/FMCAD.2013.6679394.
short: G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, R. Bloem, in:, 2013 Formal
Methods in Computer-Aided Design, IEEE, 2013, pp. 77–84.
conference:
end_date: 2013-10-23
location: Portland, OR, United States
name: 'FMCAD: Formal Methods in Computer-Aided Design'
start_date: 2013-10-20
date_created: 2018-12-11T11:51:43Z
date_published: 2013-12-11T00:00:00Z
date_updated: 2021-01-12T06:50:19Z
day: '11'
department:
- _id: ToHe
doi: 10.1109/FMCAD.2013.6679394
ec_funded: 1
external_id:
arxiv:
- '1308.4767'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1308.4767
month: '12'
oa: 1
oa_version: Preprint
page: 77 - 84
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: 2013 Formal Methods in Computer-Aided Design
publication_status: published
publisher: IEEE
publist_id: '5825'
quality_controlled: '1'
status: public
title: Synthesizing multiple boolean functions using interpolation on a single proof
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1387'
abstract:
- lang: eng
text: Choices made by nondeterministic word automata depend on both the past (the
prefix of the word read so far) and the future (the suffix yet to be read). In
several applications, most notably synthesis, the future is diverse or unknown,
leading to algorithms that are based on deterministic automata. Hoping to retain
some of the advantages of nondeterministic automata, researchers have studied
restricted classes of nondeterministic automata. Three such classes are nondeterministic
automata that are good for trees (GFT; i.e., ones that can be expanded to tree
automata accepting the derived tree languages, thus whose choices should satisfy
diverse futures), good for games (GFG; i.e., ones whose choices depend only on
the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent
deterministic automata). The theoretical properties and relative merits of the
different classes are still open, having vagueness on whether they really differ
from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known
whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also
open is the possible succinctness of GFG and GFT automata compared to deterministic
automata. We study these problems for ω-regular automata with all common acceptance
conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction
for GFG automata.
acknowledgement: and ERC Grant QUALITY.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Denis
full_name: Kuperberg, Denis
last_name: Kuperberg
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Michał
full_name: Skrzypczak, Michał
last_name: Skrzypczak
citation:
ama: Boker U, Kuperberg D, Kupferman O, Skrzypczak M. Nondeterminism in the presence
of a diverse or unknown future. 2013;7966(PART 2):89-100. doi:10.1007/978-3-642-39212-2_11
apa: 'Boker, U., Kuperberg, D., Kupferman, O., & Skrzypczak, M. (2013). Nondeterminism
in the presence of a diverse or unknown future. Presented at the ICALP: Automata,
Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39212-2_11'
chicago: Boker, Udi, Denis Kuperberg, Orna Kupferman, and Michał Skrzypczak. “Nondeterminism
in the Presence of a Diverse or Unknown Future.” Lecture Notes in Computer Science.
Springer, 2013. https://doi.org/10.1007/978-3-642-39212-2_11.
ieee: U. Boker, D. Kuperberg, O. Kupferman, and M. Skrzypczak, “Nondeterminism in
the presence of a diverse or unknown future,” vol. 7966, no. PART 2. Springer,
pp. 89–100, 2013.
ista: Boker U, Kuperberg D, Kupferman O, Skrzypczak M. 2013. Nondeterminism in the
presence of a diverse or unknown future. 7966(PART 2), 89–100.
mla: Boker, Udi, et al. Nondeterminism in the Presence of a Diverse or Unknown
Future. Vol. 7966, no. PART 2, Springer, 2013, pp. 89–100, doi:10.1007/978-3-642-39212-2_11.
short: U. Boker, D. Kuperberg, O. Kupferman, M. Skrzypczak, 7966 (2013) 89–100.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: Automata, Languages and Programming'
start_date: 2013-07-08
date_created: 2018-12-11T11:51:44Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2020-08-11T10:09:09Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-39212-2_11
ec_funded: 1
file:
- access_level: open_access
checksum: 98bc02e3793072e279ec8d364b381ff3
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T11:05:50Z
date_updated: 2020-07-14T12:44:48Z
file_id: '7857'
file_name: 2013_ICALP_Boker.pdf
file_size: 276982
relation: main_file
file_date_updated: 2020-07-14T12:44:48Z
has_accepted_license: '1'
intvolume: ' 7966'
issue: PART 2
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 89 - 100
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '5823'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Nondeterminism in the presence of a diverse or unknown future
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...
---
_id: '2181'
abstract:
- lang: eng
text: 'There is a trade-off between performance and correctness in implementing
concurrent data structures. Better performance may be achieved at the expense
of relaxing correctness, by redefining the semantics of data structures. We address
such a redefinition of data structure semantics and present a systematic and formal
framework for obtaining new data structures by quantitatively relaxing existing
ones. We view a data structure as a sequential specification S containing all
"legal" sequences over an alphabet of method calls. Relaxing the data
structure corresponds to defining a distance from any sequence over the alphabet
to the sequential specification: the k-relaxed sequential specification contains
all sequences over the alphabet within distance k from the original specification.
In contrast to other existing work, our relaxations are semantic (distance in
terms of data structure states). As an instantiation of our framework, we present
two simple yet generic relaxation schemes, called out-of-order and stuttering
relaxation, along with several ways of computing distances. We show that the out-of-order
relaxation, when further instantiated to stacks, queues, and priority queues,
amounts to tolerating bounded out-of-order behavior, which cannot be captured
by a purely syntactic relaxation (distance in terms of sequence manipulation,
e.g. edit distance). We give concurrent implementations of relaxed data structures
and demonstrate that bounded relaxations provide the means for trading correctness
for performance in a controlled way. The relaxations are monotonic which further
highlights the trade-off: increasing k increases the number of permitted sequences,
which as we demonstrate can lead to better performance. Finally, since a relaxed
stack or queue also implements a pool, we actually have new concurrent pool implementations
that outperform the state-of-the-art ones.'
acknowledgement: ' and an Elise Richter Fellowship (Austrian Science Fund V00125). '
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
citation:
ama: 'Henzinger TA, Kirsch C, Payer H, Sezgin A, Sokolova A. Quantitative relaxation
of concurrent data structures. In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Language. ACM; 2013:317-328. doi:10.1145/2429069.2429109'
apa: 'Henzinger, T. A., Kirsch, C., Payer, H., Sezgin, A., & Sokolova, A. (2013).
Quantitative relaxation of concurrent data structures. In Proceedings of the
40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language
(pp. 317–328). Rome, Italy: ACM. https://doi.org/10.1145/2429069.2429109'
chicago: Henzinger, Thomas A, Christoph Kirsch, Hannes Payer, Ali Sezgin, and Ana
Sokolova. “Quantitative Relaxation of Concurrent Data Structures.” In Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
317–28. ACM, 2013. https://doi.org/10.1145/2429069.2429109.
ieee: T. A. Henzinger, C. Kirsch, H. Payer, A. Sezgin, and A. Sokolova, “Quantitative
relaxation of concurrent data structures,” in Proceedings of the 40th annual
ACM SIGPLAN-SIGACT symposium on Principles of programming language, Rome,
Italy, 2013, pp. 317–328.
ista: 'Henzinger TA, Kirsch C, Payer H, Sezgin A, Sokolova A. 2013. Quantitative
relaxation of concurrent data structures. Proceedings of the 40th annual ACM SIGPLAN-SIGACT
symposium on Principles of programming language. POPL: Principles of Programming
Languages, 317–328.'
mla: Henzinger, Thomas A., et al. “Quantitative Relaxation of Concurrent Data Structures.”
Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Language, ACM, 2013, pp. 317–28, doi:10.1145/2429069.2429109.
short: T.A. Henzinger, C. Kirsch, H. Payer, A. Sezgin, A. Sokolova, in:, Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
ACM, 2013, pp. 317–328.
conference:
end_date: 2013-01-25
location: Rome, Italy
name: 'POPL: Principles of Programming Languages'
start_date: 2013-01-23
date_created: 2018-12-11T11:56:11Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2023-02-21T16:06:49Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1145/2429069.2429109
ec_funded: 1
file:
- access_level: open_access
checksum: adf465e70948f4e80e48057524516456
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:33Z
date_updated: 2020-07-14T12:45:31Z
file_id: '5086'
file_name: IST-2014-198-v1+1_popl128-henzinger-clean.pdf
file_size: 294689
relation: main_file
file_date_updated: 2020-07-14T12:45:31Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 317 - 328
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles
of programming language
publication_identifier:
isbn:
- 978-1-4503-1832-7
publication_status: published
publisher: ACM
publist_id: '4801'
pubrep_id: '198'
quality_controlled: '1'
related_material:
record:
- id: '10901'
relation: later_version
status: deleted
scopus_import: 1
status: public
title: Quantitative relaxation of concurrent data structures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2182'
abstract:
- lang: eng
text: We propose a general framework for abstraction with respect to quantitative
properties, such as worst-case execution time, or power consumption. Our framework
provides a systematic way for counter-example guided abstraction refinement for
quantitative properties. The salient aspect of the framework is that it allows
anytime verification, that is, verification algorithms that can be stopped at
any time (for example, due to exhaustion of memory), and report approximations
that improve monotonically when the algorithms are given more time. We instantiate
the framework with a number of quantitative abstractions and refinement schemes,
which differ in terms of how much quantitative information they keep from the
original system. We introduce both state-based and trace-based quantitative abstractions,
and we describe conditions that define classes of quantitative properties for
which the abstractions provide over-approximations. We give algorithms for evaluating
the quantitative properties on the abstract systems. We present algorithms for
counter-example based refinements for quantitative properties for both state-based
and segment-based abstractions. We perform a case study on worst-case execution
time of executables to evaluate the anytime verification aspect and the quantitative
abstractions we proposed.
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: 'Cerny P, Henzinger TA, Radhakrishna A. Quantitative abstraction refinement.
In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles
of Programming Language. ACM; 2013:115-128. doi:10.1145/2429069.2429085'
apa: 'Cerny, P., Henzinger, T. A., & Radhakrishna, A. (2013). Quantitative abstraction
refinement. In Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium
on Principles of programming language (pp. 115–128). Rome, Italy: ACM. https://doi.org/10.1145/2429069.2429085'
chicago: Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Quantitative
Abstraction Refinement.” In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Language, 115–28. ACM, 2013. https://doi.org/10.1145/2429069.2429085.
ieee: P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Quantitative abstraction
refinement,” in Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium
on Principles of programming language, Rome, Italy, 2013, pp. 115–128.
ista: 'Cerny P, Henzinger TA, Radhakrishna A. 2013. Quantitative abstraction refinement.
Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming
language. POPL: Principles of Programming Languages, 115–128.'
mla: Cerny, Pavol, et al. “Quantitative Abstraction Refinement.” Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
ACM, 2013, pp. 115–28, doi:10.1145/2429069.2429085.
short: P. Cerny, T.A. Henzinger, A. Radhakrishna, in:, Proceedings of the 40th Annual
ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language, ACM, 2013,
pp. 115–128.
conference:
end_date: 2013-01-25
location: Rome, Italy
name: 'POPL: Principles of Programming Languages'
start_date: 2013-07-23
date_created: 2018-12-11T11:56:11Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:55:50Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2429069.2429085
ec_funded: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 115 - 128
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles
of programming language
publication_status: published
publisher: ACM
publist_id: '4800'
quality_controlled: '1'
scopus_import: 1
status: public
title: Quantitative abstraction refinement
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2237'
abstract:
- lang: eng
text: We describe new extensions of the Vampire theorem prover for computing tree
interpolants. These extensions generalize Craig interpolation in Vampire, and
can also be used to derive sequence interpolants. We evaluated our implementation
on a large number of examples over the theory of linear integer arithmetic and
integer-indexed arrays, with and without quantifiers. When compared to other methods,
our experiments show that some examples could only be solved by our implementation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Régis
full_name: Blanc, Régis
last_name: Blanc
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Laura
full_name: Kovács, Laura
last_name: Kovács
- first_name: Bernhard
full_name: Kragl, Bernhard
id: 320FC952-F248-11E8-B48F-1D18A9856A87
last_name: Kragl
orcid: 0000-0001-7745-9117
citation:
ama: Blanc R, Gupta A, Kovács L, Kragl B. Tree interpolation in Vampire. 2013;8312:173-181.
doi:10.1007/978-3-642-45221-5_13
apa: 'Blanc, R., Gupta, A., Kovács, L., & Kragl, B. (2013). Tree interpolation
in Vampire. Presented at the LPAR: Logic for Programming, Artificial Intelligence,
and Reasoning, Stellenbosch, South Africa: Springer. https://doi.org/10.1007/978-3-642-45221-5_13'
chicago: Blanc, Régis, Ashutosh Gupta, Laura Kovács, and Bernhard Kragl. “Tree Interpolation
in Vampire.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-45221-5_13.
ieee: R. Blanc, A. Gupta, L. Kovács, and B. Kragl, “Tree interpolation in Vampire,”
vol. 8312. Springer, pp. 173–181, 2013.
ista: Blanc R, Gupta A, Kovács L, Kragl B. 2013. Tree interpolation in Vampire.
8312, 173–181.
mla: Blanc, Régis, et al. Tree Interpolation in Vampire. Vol. 8312, Springer,
2013, pp. 173–81, doi:10.1007/978-3-642-45221-5_13.
short: R. Blanc, A. Gupta, L. Kovács, B. Kragl, 8312 (2013) 173–181.
conference:
end_date: 2013-12-19
location: Stellenbosch, South Africa
name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
start_date: 2013-12-14
date_created: 2018-12-11T11:56:29Z
date_published: 2013-01-14T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-45221-5_13
file:
- access_level: open_access
checksum: 9cebaafca032e6769d273f393305c705
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T11:10:40Z
date_updated: 2020-07-14T12:45:34Z
file_id: '7858'
file_name: 2013_LPAR_Blanc.pdf
file_size: 279206
relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: ' 8312'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 173 - 181
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '4724'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Tree interpolation in Vampire
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8312
year: '2013'
...
---
_id: '2243'
abstract:
- lang: eng
text: We show that modal logic over universally first-order definable classes of
transitive frames is decidable. More precisely, let K be an arbitrary class of
transitive Kripke frames definable by a universal first-order sentence. We show
that the global and finite global satisfiability problems of modal logic over
K are decidable in NP, regardless of choice of K. We also show that the local
satisfiability and the finite local satisfiability problems of modal logic over
K are decidable in NEXPTIME.
alternative_title:
- LIPIcs
author:
- first_name: Jakub
full_name: Michaliszyn, Jakub
last_name: Michaliszyn
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Michaliszyn J, Otop J. Elementary modal logics over transitive structures.
2013;23:563-577. doi:10.4230/LIPIcs.CSL.2013.563
apa: 'Michaliszyn, J., & Otop, J. (2013). Elementary modal logics over transitive
structures. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.563'
chicago: Michaliszyn, Jakub, and Jan Otop. “Elementary Modal Logics over Transitive
Structures.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.563.
ieee: J. Michaliszyn and J. Otop, “Elementary modal logics over transitive structures,”
vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 563–577, 2013.
ista: Michaliszyn J, Otop J. 2013. Elementary modal logics over transitive structures.
23, 563–577.
mla: Michaliszyn, Jakub, and Jan Otop. Elementary Modal Logics over Transitive
Structures. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013,
pp. 563–77, doi:10.4230/LIPIcs.CSL.2013.563.
short: J. Michaliszyn, J. Otop, 23 (2013) 563–577.
conference:
end_date: 2013-09-05
location: Torino, Italy
name: 'CSL: Computer Science Logic'
start_date: 2013-09-02
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CSL.2013.563
ec_funded: 1
file:
- access_level: open_access
checksum: e0732e73a8b1e39483df7717d53e3e35
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:11Z
date_updated: 2020-07-14T12:45:34Z
file_id: '4929'
file_name: IST-2016-136-v1+2_39.pdf
file_size: 454915
relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: ' 23'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 563 - 577
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4708'
pubrep_id: '136'
quality_controlled: '1'
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: Elementary modal logics over transitive structures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '2289'
abstract:
- lang: eng
text: Formal verification aims to improve the quality of software by detecting errors
before they do harm. At the basis of formal verification is the logical notion
of correctness, which purports to capture whether or not a program behaves as
desired. We suggest that the boolean partition of software into correct and incorrect
programs falls short of the practical need to assess the behavior of software
in a more nuanced fashion against multiple criteria. We therefore propose to introduce
quantitative fitness measures for programs, specifically for measuring the function,
performance, and robustness of reactive programs such as concurrent processes.
This article describes the goals of the ERC Advanced Investigator Project QUAREM.
The project aims to build and evaluate a theory of quantitative fitness measures
for reactive models. Such a theory must strive to obtain quantitative generalizations
of the paradigms that have been success stories in qualitative reactive modeling,
such as compositionality, property-preserving abstraction and abstraction refinement,
model checking, and synthesis. The theory will be evaluated not only in the context
of software and hardware engineering, but also in the context of systems biology.
In particular, we will use the quantitative reactive models and fitness measures
developed in this project for testing hypotheses about the mechanisms behind data
from biological experiments.
author:
- 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: Henzinger TA. Quantitative reactive modeling and verification. Computer
Science Research and Development. 2013;28(4):331-344. doi:10.1007/s00450-013-0251-7
apa: Henzinger, T. A. (2013). Quantitative reactive modeling and verification. Computer
Science Research and Development. Springer. https://doi.org/10.1007/s00450-013-0251-7
chicago: Henzinger, Thomas A. “Quantitative Reactive Modeling and Verification.”
Computer Science Research and Development. Springer, 2013. https://doi.org/10.1007/s00450-013-0251-7.
ieee: T. A. Henzinger, “Quantitative reactive modeling and verification,” Computer
Science Research and Development, vol. 28, no. 4. Springer, pp. 331–344, 2013.
ista: Henzinger TA. 2013. Quantitative reactive modeling and verification. Computer
Science Research and Development. 28(4), 331–344.
mla: Henzinger, Thomas A. “Quantitative Reactive Modeling and Verification.” Computer
Science Research and Development, vol. 28, no. 4, Springer, 2013, pp. 331–44,
doi:10.1007/s00450-013-0251-7.
short: T.A. Henzinger, Computer Science Research and Development 28 (2013) 331–344.
date_created: 2018-12-11T11:56:47Z
date_published: 2013-10-05T00:00:00Z
date_updated: 2021-01-12T06:56:33Z
day: '05'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s00450-013-0251-7
ec_funded: 1
file:
- access_level: open_access
checksum: f117a00f9f046165bfa95595681e08a0
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:51Z
date_updated: 2020-07-14T12:45:37Z
file_id: '5308'
file_name: IST-2016-626-v1+1_s00450-013-0251-7.pdf
file_size: 570361
relation: main_file
file_date_updated: 2020-07-14T12:45:37Z
has_accepted_license: '1'
intvolume: ' 28'
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 331 - 344
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Computer Science Research and Development
publication_status: published
publisher: Springer
publist_id: '4642'
pubrep_id: '626'
quality_controlled: '1'
scopus_import: 1
status: public
title: Quantitative reactive modeling and verification
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: 28
year: '2013'
...
---
_id: '2288'
abstract:
- lang: eng
text: This book constitutes the proceedings of the 11th International Conference
on Computational Methods in Systems Biology, CMSB 2013, held in Klosterneuburg,
Austria, in September 2013. The 15 regular papers included in this volume were
carefully reviewed and selected from 27 submissions. They deal with computational
models for all levels, from molecular and cellular, to organs and entire organisms.
alternative_title:
- LNCS
citation:
ama: Gupta A, Henzinger TA, eds. Computational Methods in Systems Biology.
Vol 8130. Springer; 2013. doi:10.1007/978-3-642-40708-6
apa: 'Gupta, A., & Henzinger, T. A. (Eds.). (2013). Computational Methods
in Systems Biology (Vol. 8130). Presented at the CMSB: Computational Methods
in Systems Biology, Klosterneuburg, Austria: Springer. https://doi.org/10.1007/978-3-642-40708-6'
chicago: Gupta, Ashutosh, and Thomas A Henzinger, eds. Computational Methods
in Systems Biology. Vol. 8130. Springer, 2013. https://doi.org/10.1007/978-3-642-40708-6.
ieee: A. Gupta and T. A. Henzinger, Eds., Computational Methods in Systems Biology,
vol. 8130. Springer, 2013.
ista: Gupta A, Henzinger TA eds. 2013. Computational Methods in Systems Biology,
Springer,p.
mla: Gupta, Ashutosh, and Thomas A. Henzinger, editors. Computational Methods
in Systems Biology. Vol. 8130, Springer, 2013, doi:10.1007/978-3-642-40708-6.
short: A. Gupta, T.A. Henzinger, eds., Computational Methods in Systems Biology,
Springer, 2013.
conference:
end_date: 2013-09-24
location: Klosterneuburg, Austria
name: 'CMSB: Computational Methods in Systems Biology'
start_date: 2013-09-22
date_created: 2018-12-11T11:56:47Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2019-08-02T12:37:44Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-40708-6
editor:
- 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
intvolume: ' 8130'
language:
- iso: eng
month: '07'
oa_version: None
publication_identifier:
isbn:
- 978-3-642-40707-9
publication_status: published
publisher: Springer
publist_id: '4643'
quality_controlled: '1'
status: public
title: Computational Methods in Systems Biology
type: conference_editor
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8130
year: '2013'
...
---
_id: '2298'
abstract:
- lang: eng
text: "We present a shape analysis for programs that manipulate overlaid data structures
which share sets of objects. The abstract domain contains Separation Logic formulas
that (1) combine a per-object separating conjunction with a per-field separating
conjunction and (2) constrain a set of variables interpreted as sets of objects.
The definition of the abstract domain operators is based on a notion of homomorphism
between formulas, viewed as graphs, used recently to define optimal decision procedures
for fragments of the Separation Logic. Based on a Frame Rule that supports the
two versions of the separating conjunction, the analysis is able to reason in
a modular manner about non-overlaid data structures and then, compose information
only at a few program points, e.g., procedure returns. We have implemented this
analysis in a prototype tool and applied it on several interesting case studies
that manipulate overlaid and nested linked lists.\r\n"
alternative_title:
- LNCS
author:
- first_name: Cezara
full_name: Dragoi, Cezara
id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87
last_name: Dragoi
- first_name: Constantin
full_name: Enea, Constantin
last_name: Enea
- first_name: Mihaela
full_name: Sighireanu, Mihaela
last_name: Sighireanu
citation:
ama: 'Dragoi C, Enea C, Sighireanu M. Local shape analysis for overlaid data structures.
In: Vol 7935. Springer; 2013:150-171. doi:10.1007/978-3-642-38856-9_10'
apa: 'Dragoi, C., Enea, C., & Sighireanu, M. (2013). Local shape analysis for
overlaid data structures (Vol. 7935, pp. 150–171). Presented at the SAS: Static
Analysis Symposium, Seattle, WA, United States: Springer. https://doi.org/10.1007/978-3-642-38856-9_10'
chicago: Dragoi, Cezara, Constantin Enea, and Mihaela Sighireanu. “Local Shape Analysis
for Overlaid Data Structures,” 7935:150–71. Springer, 2013. https://doi.org/10.1007/978-3-642-38856-9_10.
ieee: 'C. Dragoi, C. Enea, and M. Sighireanu, “Local shape analysis for overlaid
data structures,” presented at the SAS: Static Analysis Symposium, Seattle, WA,
United States, 2013, vol. 7935, pp. 150–171.'
ista: 'Dragoi C, Enea C, Sighireanu M. 2013. Local shape analysis for overlaid data
structures. SAS: Static Analysis Symposium, LNCS, vol. 7935, 150–171.'
mla: Dragoi, Cezara, et al. Local Shape Analysis for Overlaid Data Structures.
Vol. 7935, Springer, 2013, pp. 150–71, doi:10.1007/978-3-642-38856-9_10.
short: C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2013, pp. 150–171.
conference:
end_date: 2013-06-22
location: Seattle, WA, United States
name: 'SAS: Static Analysis Symposium'
start_date: 2013-06-20
date_created: 2018-12-11T11:56:50Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:36Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1007/978-3-642-38856-9_10
ec_funded: 1
file:
- access_level: open_access
checksum: 907edd33a5892e3af093365f1fd57ed7
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:36Z
date_updated: 2020-07-14T12:45:37Z
file_id: '4824'
file_name: IST-2014-196-v1+1_sas13.pdf
file_size: 299004
relation: main_file
file_date_updated: 2020-07-14T12:45:37Z
has_accepted_license: '1'
intvolume: ' 7935'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 150 - 171
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '4630'
pubrep_id: '196'
quality_controlled: '1'
scopus_import: 1
status: public
title: Local shape analysis for overlaid data structures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7935
year: '2013'
...
---
_id: '2299'
abstract:
- lang: eng
text: 'The standard hardware design flow involves: (a) design of an integrated circuit
using a hardware description language, (b) extensive functional and formal verification,
and (c) logical synthesis. However, the above-mentioned processes consume significant
effort and time. An alternative approach is to use a formal specification language
as a high-level hardware description language and synthesize hardware from formal
specifications. Our work is a case study of the synthesis of the widely and industrially
used AMBA AHB protocol from formal specifications. Bloem et al. presented the
first formal specifications for the AMBA AHB Arbiter and synthesized the AHB Arbiter
circuit. However, in the first formal specification some important assumptions
were missing. Our contributions are as follows: (a) We present detailed formal
specifications for the AHB Arbiter incorporating the missing details, and obtain
significant improvements in the synthesis results (both with respect to the number
of gates in the synthesized circuit and with respect to the time taken to synthesize
the circuit), and (b) we present formal specifications to generate compact circuits
for the remaining two main components of AMBA AHB, namely, AHB Master and AHB
Slave. Thus with systematic description we are able to automatically and completely
synthesize an important and widely used industrial protocol.'
author:
- first_name: Yashdeep
full_name: Godhal, Yashdeep
id: 5B547124-EB61-11E9-8887-89D9C04DBDF5
last_name: Godhal
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Godhal Y, Chatterjee K, Henzinger TA. Synthesis of AMBA AHB from formal specification:
A case study. International Journal on Software Tools for Technology Transfer.
2013;15(5-6):585-601. doi:10.1007/s10009-011-0207-9'
apa: 'Godhal, Y., Chatterjee, K., & Henzinger, T. A. (2013). Synthesis of AMBA
AHB from formal specification: A case study. International Journal on Software
Tools for Technology Transfer. Springer. https://doi.org/10.1007/s10009-011-0207-9'
chicago: 'Godhal, Yashdeep, Krishnendu Chatterjee, and Thomas A Henzinger. “Synthesis
of AMBA AHB from Formal Specification: A Case Study.” International Journal
on Software Tools for Technology Transfer. Springer, 2013. https://doi.org/10.1007/s10009-011-0207-9.'
ieee: 'Y. Godhal, K. Chatterjee, and T. A. Henzinger, “Synthesis of AMBA AHB from
formal specification: A case study,” International Journal on Software Tools
for Technology Transfer, vol. 15, no. 5–6. Springer, pp. 585–601, 2013.'
ista: 'Godhal Y, Chatterjee K, Henzinger TA. 2013. Synthesis of AMBA AHB from formal
specification: A case study. International Journal on Software Tools for Technology
Transfer. 15(5–6), 585–601.'
mla: 'Godhal, Yashdeep, et al. “Synthesis of AMBA AHB from Formal Specification:
A Case Study.” International Journal on Software Tools for Technology Transfer,
vol. 15, no. 5–6, Springer, 2013, pp. 585–601, doi:10.1007/s10009-011-0207-9.'
short: Y. Godhal, K. Chatterjee, T.A. Henzinger, International Journal on Software
Tools for Technology Transfer 15 (2013) 585–601.
date_created: 2018-12-11T11:56:51Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2021-01-12T06:56:37Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/s10009-011-0207-9
file:
- access_level: open_access
checksum: 57b06a732dd8d6349190dba6b5b0d33b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:53Z
date_updated: 2020-07-14T12:45:37Z
file_id: '4910'
file_name: IST-2012-87-v1+1_Synthesis_of_AMBA_AHB_from_formal_specifications-_A_case_study.pdf
file_size: 277372
relation: main_file
file_date_updated: 2020-07-14T12:45:37Z
has_accepted_license: '1'
intvolume: ' 15'
issue: 5-6
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 585 - 601
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: International Journal on Software Tools for Technology Transfer
publication_status: published
publisher: Springer
publist_id: '4629'
pubrep_id: '87'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Synthesis of AMBA AHB from formal specification: A case study'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2013'
...
---
_id: '2301'
abstract:
- lang: eng
text: We describe the design and implementation of P, a domain-specific language
to write asynchronous event driven code. P allows the programmer to specify the
system as a collection of interacting state machines, which communicate with each
other using events. P unifies modeling and programming into one activity for the
programmer. Not only can a P program be compiled into executable code, but it
can also be tested using model checking techniques. P allows the programmer to
specify the environment, used to "close" the system during testing,
as nondeterministic ghost machines. Ghost machines are erased during compilation
to executable code; a type system ensures that the erasure is semantics preserving.
The P language is designed so that a P program can be checked for responsiveness-the
ability to handle every event in a timely manner. By default, a machine needs
to handle every event that arrives in every state. But handling every event in
every state is impractical. The language provides a notion of deferred events
where the programmer can annotate when she wants to delay processing an event.
The default safety checker looks for presence of unhan-dled events. The language
also provides default liveness checks that an event cannot be potentially deferred
forever. P was used to implement and verify the core of the USB device driver
stack that ships with Microsoft Windows 8. The resulting driver is more reliable
and performs better than its prior incarnation (which did not use P); we have
more confidence in the robustness of its design due to the language abstractions
and verification provided by P.
author:
- first_name: Ankush
full_name: Desai, Ankush
last_name: Desai
- first_name: Vivek
full_name: Gupta, Vivek
last_name: Gupta
- first_name: Ethan
full_name: Jackson, Ethan
last_name: Jackson
- first_name: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
- first_name: Sriram
full_name: Rajamani, Sriram
last_name: Rajamani
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: 'Desai A, Gupta V, Jackson E, Qadeer S, Rajamani S, Zufferey D. P: Safe asynchronous
event-driven programming. In: Proceedings of the 34th ACM SIGPLAN Conference
on Programming Language Design and Implementation. ACM; 2013:321-331. doi:10.1145/2491956.2462184'
apa: 'Desai, A., Gupta, V., Jackson, E., Qadeer, S., Rajamani, S., & Zufferey,
D. (2013). P: Safe asynchronous event-driven programming. In Proceedings of
the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation
(pp. 321–331). Seattle, WA, United States: ACM. https://doi.org/10.1145/2491956.2462184'
chicago: 'Desai, Ankush, Vivek Gupta, Ethan Jackson, Shaz Qadeer, Sriram Rajamani,
and Damien Zufferey. “P: Safe Asynchronous Event-Driven Programming.” In Proceedings
of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation,
321–31. ACM, 2013. https://doi.org/10.1145/2491956.2462184.'
ieee: 'A. Desai, V. Gupta, E. Jackson, S. Qadeer, S. Rajamani, and D. Zufferey,
“P: Safe asynchronous event-driven programming,” in Proceedings of the 34th
ACM SIGPLAN Conference on Programming Language Design and Implementation,
Seattle, WA, United States, 2013, pp. 321–331.'
ista: 'Desai A, Gupta V, Jackson E, Qadeer S, Rajamani S, Zufferey D. 2013. P: Safe
asynchronous event-driven programming. Proceedings of the 34th ACM SIGPLAN Conference
on Programming Language Design and Implementation. PLDI: Programming Languages
Design and Implementation, 321–331.'
mla: 'Desai, Ankush, et al. “P: Safe Asynchronous Event-Driven Programming.” Proceedings
of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation,
ACM, 2013, pp. 321–31, doi:10.1145/2491956.2462184.'
short: A. Desai, V. Gupta, E. Jackson, S. Qadeer, S. Rajamani, D. Zufferey, in:,
Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design
and Implementation, ACM, 2013, pp. 321–331.
conference:
end_date: 2013-06-19
location: Seattle, WA, United States
name: 'PLDI: Programming Languages Design and Implementation'
start_date: 2013-06-16
date_created: 2018-12-11T11:56:52Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2021-01-12T06:56:38Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2491956.2462184
ec_funded: 1
language:
- iso: eng
main_file_link:
- url: http://research.microsoft.com/pubs/191069/pldi212_desai.pdf
month: '06'
oa_version: None
page: 321 - 331
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language
Design and Implementation
publication_status: published
publisher: ACM
publist_id: '4626'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'P: Safe asynchronous event-driven programming'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2328'
abstract:
- lang: eng
text: "Linearizability of concurrent data structures is usually proved by monolithic
simulation arguments relying on identifying the so-called linearization points.
Regrettably, such proofs, whether manual or automatic, are often complicated and
scale poorly to advanced non-blocking concurrency patterns, such as helping and
optimistic updates.\r\nIn response, we propose a more modular way of checking
linearizability of concurrent queue algorithms that does not involve identifying
linearization points. We reduce the task of proving linearizability with respect
to the queue specification to establishing four basic properties, each of which
can be proved independently by simpler arguments. As a demonstration of our approach,
we verify the Herlihy and Wing queue, an algorithm that is challenging to verify
by a simulation proof."
alternative_title:
- LNCS
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: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
- first_name: Viktor
full_name: Vafeiadis, Viktor
last_name: Vafeiadis
citation:
ama: Henzinger TA, Sezgin A, Vafeiadis V. Aspect-oriented linearizability proofs.
2013;8052:242-256. doi:10.1007/978-3-642-40184-8_18
apa: 'Henzinger, T. A., Sezgin, A., & Vafeiadis, V. (2013). Aspect-oriented
linearizability proofs. Presented at the CONCUR: Concurrency Theory, Buenos Aires,
Argentina: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-642-40184-8_18'
chicago: Henzinger, Thomas A, Ali Sezgin, and Viktor Vafeiadis. “Aspect-Oriented
Linearizability Proofs.” Lecture Notes in Computer Science. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.1007/978-3-642-40184-8_18.
ieee: T. A. Henzinger, A. Sezgin, and V. Vafeiadis, “Aspect-oriented linearizability
proofs,” vol. 8052. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 242–256,
2013.
ista: Henzinger TA, Sezgin A, Vafeiadis V. 2013. Aspect-oriented linearizability
proofs. 8052, 242–256.
mla: Henzinger, Thomas A., et al. Aspect-Oriented Linearizability Proofs.
Vol. 8052, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 242–56,
doi:10.1007/978-3-642-40184-8_18.
short: T.A. Henzinger, A. Sezgin, V. Vafeiadis, 8052 (2013) 242–256.
conference:
end_date: 2013-08-30
location: Buenos Aires, Argentina
name: 'CONCUR: Concurrency Theory'
start_date: 2013-08-27
date_created: 2018-12-11T11:57:01Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2023-02-23T10:16:27Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1007/978-3-642-40184-8_18
ec_funded: 1
file:
- access_level: open_access
checksum: bdbb520de91751fe0136309ad4ef67e4
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:58Z
date_updated: 2020-07-14T12:45:39Z
file_id: '4721'
file_name: IST-2014-197-v1+1_main-queue-verification.pdf
file_size: 337059
relation: main_file
file_date_updated: 2020-07-14T12:45:39Z
has_accepted_license: '1'
intvolume: ' 8052'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 242 - 256
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4598'
pubrep_id: '197'
quality_controlled: '1'
related_material:
record:
- id: '1832'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Aspect-oriented linearizability proofs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8052
year: '2013'
...
---
_id: '2447'
abstract:
- lang: eng
text: "Separation logic (SL) has gained widespread popularity because of its ability
to succinctly express complex invariants of a program’s heap configurations. Several
specialized provers have been developed for decidable SL fragments. However, these
provers cannot be easily extended or combined with solvers for other theories
that are important in program verification, e.g., linear arithmetic. In this paper,
we present a reduction of decidable SL fragments to a decidable first-order theory
that fits well into the satisfiability modulo theories (SMT) framework. We show
how to use this reduction to automate satisfiability, entailment, frame inference,
and abduction problems for separation logic using SMT solvers. Our approach provides
a simple method of integrating separation logic into existing verification tools
that provide SMT backends, and an elegant way of combining SL fragments with other
decidable first-order theories. We implemented this approach in a verification
tool and applied it to heap-manipulating programs whose verification involves
reasoning in theory combinations.\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ruzica
full_name: Piskac, Ruzica
last_name: Piskac
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: Piskac R, Wies T, Zufferey D. Automating separation logic using SMT. 2013;8044:773-789.
doi:10.1007/978-3-642-39799-8_54
apa: 'Piskac, R., Wies, T., & Zufferey, D. (2013). Automating separation logic
using SMT. Presented at the CAV: Computer Aided Verification, St. Petersburg,
Russia: Springer. https://doi.org/10.1007/978-3-642-39799-8_54'
chicago: Piskac, Ruzica, Thomas Wies, and Damien Zufferey. “Automating Separation
Logic Using SMT.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-39799-8_54.
ieee: R. Piskac, T. Wies, and D. Zufferey, “Automating separation logic using SMT,”
vol. 8044. Springer, pp. 773–789, 2013.
ista: Piskac R, Wies T, Zufferey D. 2013. Automating separation logic using SMT.
8044, 773–789.
mla: Piskac, Ruzica, et al. Automating Separation Logic Using SMT. Vol. 8044,
Springer, 2013, pp. 773–89, doi:10.1007/978-3-642-39799-8_54.
short: R. Piskac, T. Wies, D. Zufferey, 8044 (2013) 773–789.
conference:
end_date: 2013-07-19
location: St. Petersburg, Russia
name: 'CAV: Computer Aided Verification'
start_date: 2013-07-13
date_created: 2018-12-11T11:57:43Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2020-08-11T10:09:47Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-39799-8_54
file:
- access_level: open_access
checksum: 2e866932ab688f47ecd504acb4d5c7d4
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T11:13:01Z
date_updated: 2020-07-14T12:45:41Z
file_id: '7859'
file_name: 2013_CAV_Piskac.pdf
file_size: 309182
relation: main_file
file_date_updated: 2020-07-14T12:45:41Z
has_accepted_license: '1'
intvolume: ' 8044'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 773 - 789
publication_status: published
publisher: Springer
publist_id: '4456'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Automating separation logic using SMT
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8044
year: '2013'
...
---
_id: '2517'
abstract:
- lang: eng
text: 'Traditional formal methods are based on a Boolean satisfaction notion: a
reactive system satisfies, or not, a given specification. We generalize formal
methods to also address the quality of systems. As an adequate specification formalism
we introduce the linear temporal logic LTL[F]. The satisfaction value of an LTL[F]
formula is a number between 0 and 1, describing the quality of the satisfaction.
The logic generalizes traditional LTL by augmenting it with a (parameterized)
set F of arbitrary functions over the interval [0,1]. For example, F may contain
the maximum or minimum between the satisfaction values of subformulas, their product,
and their average. The classical decision problems in formal methods, such as
satisfiability, model checking, and synthesis, are generalized to search and optimization
problems in the quantitative setting. For example, model checking asks for the
quality in which a specification is satisfied, and synthesis returns a system
satisfying the specification with the highest quality. Reasoning about quality
gives rise to other natural questions, like the distance between specifications.
We formalize these basic questions and study them for LTL[F]. By extending the
automata-theoretic approach for LTL to a setting that takes quality into an account,
we are able to solve the above problems and show that reasoning about LTL[F] has
roughly the same complexity as reasoning about traditional LTL.'
acknowledgement: 'ERC Grant QUALITY. '
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shaull
full_name: Almagor, Shaull
last_name: Almagor
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Almagor S, Boker U, Kupferman O. Formalizing and reasoning about quality. 2013;7966(Part
2):15-27. doi:10.1007/978-3-642-39212-2_3
apa: 'Almagor, S., Boker, U., & Kupferman, O. (2013). Formalizing and reasoning
about quality. Presented at the ICALP: Automata, Languages and Programming, Riga,
Latvia: Springer. https://doi.org/10.1007/978-3-642-39212-2_3'
chicago: Almagor, Shaull, Udi Boker, and Orna Kupferman. “Formalizing and Reasoning
about Quality.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-39212-2_3.
ieee: S. Almagor, U. Boker, and O. Kupferman, “Formalizing and reasoning about quality,”
vol. 7966, no. Part 2. Springer, pp. 15–27, 2013.
ista: Almagor S, Boker U, Kupferman O. 2013. Formalizing and reasoning about quality.
7966(Part 2), 15–27.
mla: Almagor, Shaull, et al. Formalizing and Reasoning about Quality. Vol.
7966, no. Part 2, Springer, 2013, pp. 15–27, doi:10.1007/978-3-642-39212-2_3.
short: S. Almagor, U. Boker, O. Kupferman, 7966 (2013) 15–27.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: Automata, Languages and Programming'
start_date: 2013-07-08
date_created: 2018-12-11T11:58:08Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2020-08-11T10:09:47Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-39212-2_3
ec_funded: 1
file:
- access_level: open_access
checksum: 85afbf6c18a2c7e377c52c9410e2d824
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T11:16:12Z
date_updated: 2020-07-14T12:45:42Z
file_id: '7860'
file_name: 2013_ICALP_Almagor.pdf
file_size: 363031
relation: main_file
file_date_updated: 2020-07-14T12:45:42Z
has_accepted_license: '1'
intvolume: ' 7966'
issue: Part 2
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 15 - 27
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '4384'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Formalizing and reasoning about quality
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...
---
_id: '2854'
abstract:
- lang: eng
text: We consider concurrent games played on graphs. At every round of a game, each
player simultaneously and independently selects a move; the moves jointly determine
the transition to a successor state. Two basic objectives are the safety objective
to stay forever in a given set of states, and its dual, the reachability objective
to reach a given set of states. First, we present a simple proof of the fact that
in concurrent reachability games, for all ε>0, memoryless ε-optimal strategies
exist. A memoryless strategy is independent of the history of plays, and an ε-optimal
strategy achieves the objective with probability within ε of the value of the
game. In contrast to previous proofs of this fact, our proof is more elementary
and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration)
algorithm for concurrent games with reachability objectives. Finally, we present
a strategy-improvement algorithm for turn-based stochastic games (where each player
selects moves in turns) with safety objectives. Our algorithms yield sequences
of player-1 strategies which ensure probabilities of winning that converge monotonically
(from below) to the value of the game. © 2012 Elsevier Inc.
acknowledgement: This work was partially supported in part by the NSF grants CCR-0132780,
CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant
Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft
faculty fellows
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: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent
reachability and turn based stochastic safety games. Journal of Computer and
System Sciences. 2013;79(5):640-657. doi:10.1016/j.jcss.2012.12.001
apa: Chatterjee, K., De Alfaro, L., & Henzinger, T. A. (2013). Strategy improvement
for concurrent reachability and turn based stochastic safety games. Journal
of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2012.12.001
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy
Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.”
Journal of Computer and System Sciences. Elsevier, 2013. https://doi.org/10.1016/j.jcss.2012.12.001.
ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for
concurrent reachability and turn based stochastic safety games,” Journal of
Computer and System Sciences, vol. 79, no. 5. Elsevier, pp. 640–657, 2013.
ista: Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent
reachability and turn based stochastic safety games. Journal of Computer and System
Sciences. 79(5), 640–657.
mla: Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability
and Turn Based Stochastic Safety Games.” Journal of Computer and System Sciences,
vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:10.1016/j.jcss.2012.12.001.
short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System
Sciences 79 (2013) 640–657.
date_created: 2018-12-11T11:59:57Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2021-01-12T07:00:16Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jcss.2012.12.001
ec_funded: 1
file:
- access_level: open_access
checksum: 6d3ee12cceb946a0abe69594b6a22409
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:48Z
date_updated: 2020-07-14T12:45:51Z
file_id: '5370'
file_name: IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf
file_size: 425488
relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
has_accepted_license: '1'
intvolume: ' 79'
issue: '5'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 640 - 657
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '3938'
pubrep_id: '388'
quality_controlled: '1'
scopus_import: 1
status: public
title: Strategy improvement for concurrent reachability and turn based stochastic
safety games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 79
year: '2013'
...
---
_id: '2885'
abstract:
- lang: eng
text: 'This volume contains the post-proceedings of the 8th Doctoral Workshop on
Mathematical and Engineering Methods in Computer Science, MEMICS 2012, held in
Znojmo, Czech Republic, in October, 2012. The 13 thoroughly revised papers were
carefully selected out of 31 submissions and are presented together with 6 invited
papers. The topics covered by the papers include: computer-aided analysis and
verification, applications of game theory in computer science, networks and security,
modern trends of graph theory in computer science, electronic systems design and
testing, and quantum information processing.'
acknowledgement: Red Hat Czech Republic, Y Soft
alternative_title:
- LNCS
citation:
ama: Kucera A, Henzinger TA, Nesetril J, Vojnar T, Antos D, eds. Mathematical
and Engineering Methods in Computer Science. Vol 7721. Springer; 2013:1-228.
doi:10.1007/978-3-642-36046-6
apa: 'Kucera, A., Henzinger, T. A., Nesetril, J., Vojnar, T., & Antos, D. (Eds.).
(2013). Mathematical and Engineering Methods in Computer Science (Vol.
7721, pp. 1–228). Presented at the MEMICS: Mathematical and Engineering methods
in computer science, Znojmo, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-36046-6'
chicago: Kucera, Antonin, Thomas A Henzinger, Jaroslav Nesetril, Tomas Vojnar, and
David Antos, eds. Mathematical and Engineering Methods in Computer Science.
Vol. 7721. Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-36046-6.
ieee: A. Kucera, T. A. Henzinger, J. Nesetril, T. Vojnar, and D. Antos, Eds., Mathematical
and Engineering Methods in Computer Science, vol. 7721. Springer, 2013, pp.
1–228.
ista: Kucera A, Henzinger TA, Nesetril J, Vojnar T, Antos D eds. 2013. Mathematical
and Engineering Methods in Computer Science, Springer,p.
mla: Kucera, Antonin, et al., editors. Mathematical and Engineering Methods in
Computer Science. Vol. 7721, Springer, 2013, pp. 1–228, doi:10.1007/978-3-642-36046-6.
short: A. Kucera, T.A. Henzinger, J. Nesetril, T. Vojnar, D. Antos, eds., Mathematical
and Engineering Methods in Computer Science, Springer, 2013.
conference:
end_date: 2012-10-28
location: Znojmo, Czech Republic
name: 'MEMICS: Mathematical and Engineering methods in computer science'
start_date: 2012-10-25
date_created: 2018-12-11T12:00:08Z
date_published: 2013-01-09T00:00:00Z
date_updated: 2019-08-02T12:37:55Z
day: '09'
department:
- _id: ToHe
doi: 10.1007/978-3-642-36046-6
editor:
- first_name: Antonin
full_name: Kucera, Antonin
last_name: Kucera
- 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: Jaroslav
full_name: Nesetril, Jaroslav
last_name: Nesetril
- first_name: Tomas
full_name: Vojnar, Tomas
last_name: Vojnar
- first_name: David
full_name: Antos, David
last_name: Antos
intvolume: ' 7721'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 228
publication_status: published
publisher: Springer
publist_id: '3874'
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Mathematical and Engineering Methods in Computer Science
type: conference_editor
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7721
year: '2013'
...
---
_id: '5402'
abstract:
- lang: eng
text: "Linearizability requires that the outcome of calls by competing threads to
a concurrent data structure is the same as some sequential execution where each
thread has exclusive access to the data structure. In an ordered data structure,
such as a queue or a stack, linearizability is ensured by requiring threads commit
in the order dictated by the sequential semantics of the data structure; e.g.,
in a concurrent queue implementation a dequeue can only remove the oldest element.
\r\nIn this paper, we investigate the impact of this strict ordering, by comparing
what linearizability allows to what existing implementations do. We first give
an operational definition for linearizability which allows us to build the most
general linearizable implementation as a transition system for any given sequential
specification. We then use this operational definition to categorize linearizable
implementations based on whether they are bound or free. In a bound implementation,
whenever all threads observe the same logical state, the updates to the logical
state and the temporal order of commits coincide. All existing queue implementations
we know of are bound. We then proceed to present, to the best of our knowledge,
the first ever free queue implementation. Our experiments show that free implementations
have the potential for better performance by suffering less from contention."
alternative_title:
- IST Austria Technical Report
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: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
citation:
ama: Henzinger TA, Sezgin A. How Free Is Your Linearizable Concurrent Data Structure?
IST Austria; 2013. doi:10.15479/AT:IST-2013-123-v1-1
apa: Henzinger, T. A., & Sezgin, A. (2013). How free is your linearizable
concurrent data structure? IST Austria. https://doi.org/10.15479/AT:IST-2013-123-v1-1
chicago: Henzinger, Thomas A, and Ali Sezgin. How Free Is Your Linearizable Concurrent
Data Structure? IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-123-v1-1.
ieee: T. A. Henzinger and A. Sezgin, How free is your linearizable concurrent
data structure? IST Austria, 2013.
ista: Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data
structure?, IST Austria, 16p.
mla: Henzinger, Thomas A., and Ali Sezgin. How Free Is Your Linearizable Concurrent
Data Structure? IST Austria, 2013, doi:10.15479/AT:IST-2013-123-v1-1.
short: T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data
Structure?, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-06-12T00:00:00Z
date_updated: 2020-07-14T23:04:47Z
day: '12'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2013-123-v1-1
file:
- access_level: open_access
checksum: ce580605ae9756a8c99d7b403ebb8eed
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:19Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5480'
file_name: IST-2013-123-v1+1_main-concur2013.pdf
file_size: 249790
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '16'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '123'
status: public
title: How free is your linearizable concurrent data structure?
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1376'
abstract:
- lang: eng
text: 'We consider the distributed synthesis problem for temporal logic specifications.
Traditionally, the problem has been studied for LTL, and the previous results
show that the problem is decidable iff there is no information fork in the architecture.
We consider the problem for fragments of LTL and our main results are as follows:
(1) We show that the problem is undecidable for architectures with information
forks even for the fragment of LTL with temporal operators restricted to next
and eventually. (2) For specifications restricted to globally along with non-nested
next operators, we establish decidability (in EXPSPACE) for star architectures
where the processes receive disjoint inputs, whereas we establish undecidability
for architectures containing an information fork-meet structure. (3) Finally,
we consider LTL without the next operator, and establish decidability (NEXPTIME-complete)
for all architectures for a fragment that consists of a set of safety assumptions,
and a set of guarantees where each guarantee is a safety, reachability, or liveness
condition.'
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: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis
for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided
Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386'
apa: 'Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013).
Distributed synthesis for LTL fragments. In 13th International Conference on
Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United
States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
“Distributed Synthesis for LTL Fragments.” In 13th International Conference
on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed
synthesis for LTL fragments,” in 13th International Conference on Formal Methods
in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25.
ista: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided
Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.'
mla: Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th
International Conference on Formal Methods in Computer-Aided Design, IEEE,
2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386.
short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International
Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.
conference:
end_date: 2013-10-23
location: Portland, OR, United States
name: 'FMCAD: Formal Methods in Computer-Aided Design'
start_date: 2013-10-20
date_created: 2018-12-11T11:51:40Z
date_published: 2013-12-11T00:00:00Z
date_updated: 2023-02-23T12:24:53Z
day: '11'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/FMCAD.2013.6679386
ec_funded: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 18 - 25
project:
- _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: 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: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 13th International Conference on Formal Methods in Computer-Aided Design
publication_status: published
publisher: IEEE
publist_id: '5835'
quality_controlled: '1'
related_material:
record:
- id: '5406'
relation: earlier_version
status: public
status: public
title: Distributed synthesis for LTL fragments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5406'
abstract:
- lang: eng
text: 'We consider the distributed synthesis problem fortemporal logic specifications.
Traditionally, the problem has been studied for LTL, and the previous results
show that the problem is decidable iff there is no information fork in the architecture.
We consider the problem for fragments of LTLand our main results are as follows:
(1) We show that the problem is undecidable for architectures with information
forks even for the fragment of LTL with temporal operators restricted to next
and eventually. (2) For specifications restricted to globally along with non-nested
next operators, we establish decidability (in EXPSPACE) for star architectures
where the processes receive disjoint inputs, whereas we establish undecidability
for architectures containing an information fork-meet structure. (3)Finally, we
consider LTL without the next operator, and establish decidability (NEXPTIME-complete)
for all architectures for a fragment that consists of a set of safety assumptions,
and a set of guarantees where each guarantee is a safety, reachability, or liveness
condition.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- 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, Henzinger TA, Otop J, Pavlogiannis A. Distributed Synthesis
for LTL Fragments. IST Austria; 2013. doi:10.15479/AT:IST-2013-130-v1-1
apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013).
Distributed synthesis for LTL Fragments. IST Austria. https://doi.org/10.15479/AT:IST-2013-130-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
Distributed Synthesis for LTL Fragments. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-130-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed
synthesis for LTL Fragments. IST Austria, 2013.
ista: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
for LTL Fragments, IST Austria, 11p.
mla: Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments.
IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis
for LTL Fragments, IST Austria, 2013.
date_created: 2018-12-12T11:39:09Z
date_published: 2013-07-08T00:00:00Z
date_updated: 2023-02-21T17:01:26Z
day: '08'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2013-130-v1-1
file:
- access_level: open_access
checksum: 855513ebaf6f72228800c5fdb522f93c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:18Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5540'
file_name: IST-2013-130-v1+1_Distributed_Synthesis.pdf
file_size: 467895
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '11'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '130'
related_material:
record:
- id: '1376'
relation: later_version
status: public
status: public
title: Distributed synthesis for LTL Fragments
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2327'
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, and robustness
problems that measure how much a model can be perturbed without violating the
specification. We show that for automatic distance functions, and ω-regular linear-time
and branching-time specifications, the model-measuring problem can be solved.
We use automata-theoretic model-checking methods for model measuring, replacing
the emptiness question for standard word and tree automata by the optimal-weight
question for the weighted versions of these automata. We consider weighted automata
that accumulate weights by maximizing, summing, discounting, and limit averaging.
We give several examples of using the model-measuring problem to compute various
notions of robustness and quantitative satisfaction for temporal specifications.'
alternative_title:
- LNCS
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. From model checking to model measuring. 2013;8052:273-287.
doi:10.1007/978-3-642-40184-8_20
apa: 'Henzinger, T. A., & Otop, J. (2013). From model checking to model measuring.
Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentina: Springer.
https://doi.org/10.1007/978-3-642-40184-8_20'
chicago: Henzinger, Thomas A, and Jan Otop. “From Model Checking to Model Measuring.”
Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40184-8_20.
ieee: T. A. Henzinger and J. Otop, “From model checking to model measuring,” vol.
8052. Springer, pp. 273–287, 2013.
ista: Henzinger TA, Otop J. 2013. From model checking to model measuring. 8052,
273–287.
mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring.
Vol. 8052, Springer, 2013, pp. 273–87, doi:10.1007/978-3-642-40184-8_20.
short: T.A. Henzinger, J. Otop, 8052 (2013) 273–287.
conference:
end_date: 2013-08-30
location: Buenos Aires, Argentina
name: 'CONCUR: Concurrency Theory'
start_date: 2013-08-27
date_created: 2018-12-11T11:57:00Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2023-02-23T12:25:26Z
day: '01'
ddc:
- '005'
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-40184-8_20
file:
- access_level: open_access
checksum: 4c04695c4bfdf2119cd4f5d1babc3e8a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:45Z
date_updated: 2020-07-14T12:45:38Z
file_id: '5301'
file_name: IST-2013-129-v1+1_concur.pdf
file_size: 378587
relation: main_file
file_date_updated: 2020-07-14T12:45:38Z
has_accepted_license: '1'
intvolume: ' 8052'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 273 - 287
publication_status: published
publisher: Springer
publist_id: '4599'
pubrep_id: '129'
quality_controlled: '1'
related_material:
record:
- id: '5417'
relation: earlier_version
status: public
series_title: Lecture Notes in Computer Science
status: public
title: From model checking to model measuring
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8052
year: '2013'
...
---
_id: '6440'
abstract:
- lang: eng
text: In order to guarantee that each method of a data structure updates the logical
state exactly once, al-most all non-blocking implementations employ Compare-And-Swap
(CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods
competing among themselves to update the same variable, the tail or the head,
respectively, leading to high contention and poor scalability. Recent non-blocking
queue implementations try to alleviate high contentionby increasing the number
of contention points, all the while using CAS-based synchronization. Furthermore,
obtaining a wait-free implementation with competition is achieved by additional
synchronization which leads to further degradation of performance.In this paper
we formalize the notion of competitiveness of a synchronizing statement which
can beused as a measure for the scalability of concurrent implementations. We
present a new queue implementation, the Speculative Pairing (SP) queue, which,
as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead
of CAS. We prove that the SP queue is linearizable and lock-free.We also show
that replacing CAS with FAI leads to wait-freedom for dequeue methods without
an adverse effect on performance. In fact, our experiments suggest that the SP
queue can perform and scale better than the state-of-the-art queue implementations.
alternative_title:
- IST Austria Technical Report
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: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
citation:
ama: Henzinger TA, Payer H, Sezgin A. Replacing Competition with Cooperation
to Achieve Scalable Lock-Free FIFO Queues . IST Austria; 2013. doi:10.15479/AT:IST-2013-124-v1-1
apa: Henzinger, T. A., Payer, H., & Sezgin, A. (2013). Replacing competition
with cooperation to achieve scalable lock-free FIFO queues . IST Austria.
https://doi.org/10.15479/AT:IST-2013-124-v1-1
chicago: Henzinger, Thomas A, Hannes Payer, and Ali Sezgin. Replacing Competition
with Cooperation to Achieve Scalable Lock-Free FIFO Queues . IST Austria,
2013. https://doi.org/10.15479/AT:IST-2013-124-v1-1.
ieee: T. A. Henzinger, H. Payer, and A. Sezgin, Replacing competition with cooperation
to achieve scalable lock-free FIFO queues . IST Austria, 2013.
ista: Henzinger TA, Payer H, Sezgin A. 2013. Replacing competition with cooperation
to achieve scalable lock-free FIFO queues , IST Austria, 23p.
mla: Henzinger, Thomas A., et al. Replacing Competition with Cooperation to Achieve
Scalable Lock-Free FIFO Queues . IST Austria, 2013, doi:10.15479/AT:IST-2013-124-v1-1.
short: T.A. Henzinger, H. Payer, A. Sezgin, Replacing Competition with Cooperation
to Achieve Scalable Lock-Free FIFO Queues , IST Austria, 2013.
date_created: 2019-05-13T14:13:27Z
date_published: 2013-06-13T00:00:00Z
date_updated: 2020-07-14T23:06:19Z
day: '13'
ddc:
- '000'
- '005'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2013-124-v1-1
file:
- access_level: open_access
checksum: a219ba4eada6cd62befed52262ee15d4
content_type: application/pdf
creator: dernst
date_created: 2019-05-13T14:11:39Z
date_updated: 2020-07-14T12:47:30Z
file_id: '6441'
file_name: 2013_TechRep_Henzinger.pdf
file_size: 549684
relation: main_file
file_date_updated: 2020-07-14T12:47:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '23'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '124'
status: public
title: 'Replacing competition with cooperation to achieve scalable lock-free FIFO
queues '
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5747'
article_processing_charge: No
author:
- first_name: Cezara
full_name: Dragoi, Cezara
id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87
last_name: Dragoi
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Dragoi C, Gupta A, Henzinger TA. Automatic Linearizability Proofs of Concurrent
Objects with Cooperating Updates. In: Computer Aided Verification. Vol
8044. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg; 2013:174-190. doi:10.1007/978-3-642-39799-8_11'
apa: 'Dragoi, C., Gupta, A., & Henzinger, T. A. (2013). Automatic Linearizability
Proofs of Concurrent Objects with Cooperating Updates. In Computer Aided Verification
(Vol. 8044, pp. 174–190). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-39799-8_11'
chicago: 'Dragoi, Cezara, Ashutosh Gupta, and Thomas A Henzinger. “Automatic Linearizability
Proofs of Concurrent Objects with Cooperating Updates.” In Computer Aided Verification,
8044:174–90. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. https://doi.org/10.1007/978-3-642-39799-8_11.'
ieee: 'C. Dragoi, A. Gupta, and T. A. Henzinger, “Automatic Linearizability Proofs
of Concurrent Objects with Cooperating Updates,” in Computer Aided Verification,
vol. 8044, Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 174–190.'
ista: 'Dragoi C, Gupta A, Henzinger TA. 2013.Automatic Linearizability Proofs of
Concurrent Objects with Cooperating Updates. In: Computer Aided Verification.
vol. 8044, 174–190.'
mla: Dragoi, Cezara, et al. “Automatic Linearizability Proofs of Concurrent Objects
with Cooperating Updates.” Computer Aided Verification, vol. 8044, Springer
Berlin Heidelberg, 2013, pp. 174–90, doi:10.1007/978-3-642-39799-8_11.
short: C. Dragoi, A. Gupta, T.A. Henzinger, in:, Computer Aided Verification, Springer
Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 174–190.
conference:
end_date: 2013-07-19
location: Saint Petersburg, Russia
name: CAV 2013
start_date: 2013-07-13
date_created: 2018-12-18T13:10:21Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2023-09-05T14:16:07Z
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-642-39799-8_11
ec_funded: 1
file:
- access_level: open_access
checksum: a901cc6b71db08b61c0d4c0cbacc6287
content_type: application/pdf
creator: dernst
date_created: 2018-12-18T13:13:33Z
date_updated: 2020-07-14T12:47:10Z
file_id: '5748'
file_name: 2013_CAV_Dragoi.pdf
file_size: 236480
relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
has_accepted_license: '1'
intvolume: ' 8044'
language:
- iso: eng
oa: 1
oa_version: None
page: 174-190
place: Berlin, Heidelberg
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
publication: Computer Aided Verification
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783642397981'
- '9783642397998'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
pubrep_id: '195'
quality_controlled: '1'
scopus_import: '1'
series_title: CAV
status: public
title: Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 8044
year: '2013'
...
---
_id: '1405'
abstract:
- lang: eng
text: "Motivated by the analysis of highly dynamic message-passing systems, i.e.
unbounded thread creation, mobility, etc. we present a framework for the analysis
of depth-bounded systems. Depth-bounded systems are one of the most expressive
known fragment of the π-calculus for which interesting verification problems are
still decidable. Even though they are infinite state systems depth-bounded systems
are well-structured, thus can be analyzed algorithmically. We give an interpretation
of depth-bounded systems as graph-rewriting systems. This gives more flexibility
and ease of use to apply depth-bounded systems to other type of systems like shared
memory concurrency.\r\n\r\nFirst, we develop an adequate domain of limits for
depth-bounded systems, a prerequisite for the effective representation of downward-closed
sets. Downward-closed sets are needed by forward saturation-based algorithms to
represent potentially infinite sets of states. Then, we present an abstract interpretation
framework to compute the covering set of well-structured transition systems. Because,
in general, the covering set is not computable, our abstraction over-approximates
the actual covering set. Our abstraction captures the essence of acceleration
based-algorithms while giving up enough precision to ensure convergence. We have
implemented the analysis in the PICASSO tool and show that it is accurate in practice.
Finally, we build some further analyses like termination using the covering set
as starting point."
acknowledgement: "This work was supported in part by the Austrian Science Fund NFN
RiSE (Rigorous Systems Engineering) and by the ERC Advanced Grant QUAREM (Quantitative
Reactve Modeling).\r\nChapter 2, 3, and 4 are joint work with Thomas A. Henzinger
and Thomas Wies. Chapter 2 was published in FoSSaCS 2010 as “Forward Analysis of
Depth-Bounded Processes” [112]. Chapter 3 was published in VMCAI 2012 as “Ideal
Abstractions for Well-Structured Transition Systems” [114]. Chap- ter 5.1 is joint
work with Kshitij Bansal, Eric Koskinen, and Thomas Wies. It was published in TACAS
2013 as “Structural Counter Abstraction” [13]. The author’s contribution in this
part is mostly related to the implementation. The theory required to understand
the method and its implementation is quickly recalled to make the thesis self-contained,
but should not be considered as a contribution. For the details of the methods,
we refer the reader to the orig- inal publication [13] and the corresponding technical
report [14]. Chapter 5.2 is ongoing work with Shahram Esmaeilsabzali, Rupak Majumdar,
and Thomas Wies. I also would like to thank the people who supported over the past
4 years. My advisor Thomas A. Henzinger who gave me a lot of freedom to work on
projects I was interested in. My collaborators, especially Thomas Wies with whom
I worked since the beginning. The members of my thesis committee, Viktor Kun- cak
and Rupak Majumdar, who also agreed to advise me. Simon Aeschbacher, Pavol Cerny,
Cezara Dragoi, Arjun Radhakrishna, my family, friends and col- leagues who created
an enjoyable environment. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: Zufferey D. Analysis of dynamic message passing programs. 2013. doi:10.15479/at:ista:1405
apa: Zufferey, D. (2013). Analysis of dynamic message passing programs. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:1405
chicago: Zufferey, Damien. “Analysis of Dynamic Message Passing Programs.” Institute
of Science and Technology Austria, 2013. https://doi.org/10.15479/at:ista:1405.
ieee: D. Zufferey, “Analysis of dynamic message passing programs,” Institute of
Science and Technology Austria, 2013.
ista: Zufferey D. 2013. Analysis of dynamic message passing programs. Institute
of Science and Technology Austria.
mla: Zufferey, Damien. Analysis of Dynamic Message Passing Programs. Institute
of Science and Technology Austria, 2013, doi:10.15479/at:ista:1405.
short: D. Zufferey, Analysis of Dynamic Message Passing Programs, Institute of Science
and Technology Austria, 2013.
date_created: 2018-12-11T11:51:50Z
date_published: 2013-09-05T00:00:00Z
date_updated: 2023-09-07T11:36:37Z
day: '05'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: ToHe
- _id: GradSch
doi: 10.15479/at:ista:1405
ec_funded: 1
file:
- access_level: open_access
checksum: ed2d7b52933d134e8dc69d569baa284e
content_type: application/pdf
creator: dernst
date_created: 2021-02-22T11:28:36Z
date_updated: 2021-02-22T11:28:36Z
file_id: '9176'
file_name: 2013_Zufferey_thesis_final.pdf
file_size: 1514906
relation: main_file
success: 1
- access_level: closed
checksum: cecc4c4b14225bee973d32e3dba91a55
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-16T14:42:52Z
date_updated: 2021-11-17T13:47:58Z
file_id: '10298'
file_name: 2013_Zufferey_thesis_final_pdfa.pdf
file_size: 1378313
relation: main_file
file_date_updated: 2021-11-17T13:47:58Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- url: http://dzufferey.github.io/files/2013_thesis.pdf
month: '09'
oa: 1
oa_version: Published Version
page: '134'
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '5802'
related_material:
record:
- id: '2847'
relation: part_of_dissertation
status: public
- id: '3251'
relation: part_of_dissertation
status: public
- id: '4361'
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: Analysis of dynamic message passing programs
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2013'
...