---
_id: '5430'
abstract:
- lang: eng
text: We consider the core algorithmic problems related to verification of systems
with respect to three classical quantitative properties, namely, the mean- payoff
property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute
the optimal value (the infimum value over all traces) from every node of the graph.
We consider graphs with constant treewidth, and it is well-known that the control-flow
graphs of most programs have constant treewidth. Let n denote the number of nodes
of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) )
and W the largest absolute value of the weights. Our main theoretical results
are as follows. First, for constant treewidth graphs we present an algorithm that
approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time
O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms
that require quadratic time. Second, for the ratio property we present an algorithm
that for constant treewidth graphs works in time O ( n · log( | a · b · n | ))
= O ( n · log( n · W )) , when the output is a b , as compared to the previously
best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the
minimum initial credit problem we show that (i) for general graphs the problem
can be solved in O ( n 2 · m ) time and the associated decision problem can be
solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n
· W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth
graphs we present an algorithm that requires O ( n · log n ) time, improving the
previous known O ( n 4 · log( n · W )) bound. We have implemented some of our
algorithms and show that they present a significant speedup on standard benchmarks.
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
citation:
ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. *Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-319-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). *Faster
algorithms for quantitative verification in constant treewidth graphs*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-319-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
*Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-319-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, *Faster algorithms
for quantitative verification in constant treewidth graphs*. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for
quantitative verification in constant treewidth graphs, IST Austria, 31p.
mla: Chatterjee, Krishnendu, et al. *Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs*. IST Austria, 2015, doi:10.15479/AT:IST-2015-319-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:17Z
date_published: 2015-02-10T00:00:00Z
date_updated: 2020-08-11T10:09:21Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-319-v1-1
file:
- access_level: open_access
checksum: 62c6ea01e342553dcafb88a070fb1ad5
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:21Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5482'
file_name: IST-2015-319-v1+1_long.pdf
file_size: 1089651
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '31'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '319'
related_material:
record:
- id: '5437'
relation: later_version
status: public
- id: '1607'
relation: later_version
status: public
status: public
title: Faster algorithms for quantitative verification in constant treewidth graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5439'
abstract:
- lang: eng
text: 'The target discounted-sum problem is the following: Given a rational discount
factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite
or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals
t? The problem turns out to relate to many fields of mathematics and computer
science, and its decidability question is surprisingly hard to solve. We solve
the finite version of the problem, and show the hardness of the infinite version,
linking it to various areas and open problems in mathematics and computer science:
β-expansions, discounted-sum automata, piecewise affine maps, and generalizations
of the Cantor set. We provide some partial results to the infinite version, among
which are solutions to its restriction to eventually-periodic sequences and to
the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving
some open problems on discounted-sum automata, among which are the exact-value
problem for nondeterministic automata over finite words and the universality and
inclusion problems for functional automata. '
alternative_title:
- IST Austria Technical Report
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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Boker U, Henzinger TA, Otop J. *The Target Discounted-Sum Problem*. IST
Austria; 2015. doi:10.15479/AT:IST-2015-335-v1-1
apa: Boker, U., Henzinger, T. A., & Otop, J. (2015). *The target discounted-sum
problem*. IST Austria. https://doi.org/10.15479/AT:IST-2015-335-v1-1
chicago: Boker, Udi, Thomas A Henzinger, and Jan Otop. *The Target Discounted-Sum
Problem*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-335-v1-1.
ieee: U. Boker, T. A. Henzinger, and J. Otop, *The target discounted-sum problem*.
IST Austria, 2015.
ista: Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST
Austria, 20p.
mla: Boker, Udi, et al. *The Target Discounted-Sum Problem*. IST Austria, 2015,
doi:10.15479/AT:IST-2015-335-v1-1.
short: U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST
Austria, 2015.
date_created: 2018-12-12T11:39:20Z
date_published: 2015-05-18T00:00:00Z
date_updated: 2020-08-11T10:09:25Z
day: '18'
ddc:
- '004'
- '512'
- '513'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2015-335-v1-1
file:
- access_level: open_access
checksum: 40405907aa012acece1bc26cf0be554d
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:55Z
date_updated: 2020-07-14T12:46:55Z
file_id: '5517'
file_name: IST-2015-335-v1+1_report.pdf
file_size: 589619
relation: main_file
file_date_updated: 2020-07-14T12:46:55Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '335'
related_material:
record:
- id: '1659'
relation: later_version
status: public
status: public
title: The target discounted-sum problem
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5435'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. \r\nThere have been two different views: (i) the
expectation semantics, where the goal is to optimize the expected mean-payoff
objective, and (ii) the satisfaction semantics, where the goal is to maximize
the probability of runs such that the mean-payoff value stays above a given vector.
\ \r\nWe consider the problem where the goal is to optimize the expectation under
the constraint that the satisfaction semantics is ensured, and thus consider a
generalization that unifies the existing semantics. Our problem captures the notion
of optimization with respect to strategies that are risk-averse (i.e., ensures
certain probabilistic guarantee).\r\nOur main results are algorithms for the decision
problem which are always polynomial in the size of the MDP.\r\nWe also show that
an approximation of the Pareto-curve can be computed in time polynomial in the
size of the MDP, and the approximation factor, but exponential in the number of
dimensions. Finally, we present a complete characterization of the strategy complexity
(in terms of memory bounds and randomization) required to solve our problem."
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: Zuzana
full_name: Komarkova, Zuzana
last_name: Komarkova
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: Chatterjee K, Komarkova Z, Kretinsky J. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v2-1
apa: Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). *Unifying two
views on multiple mean-payoff objectives in Markov decision processes*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-318-v2-1
chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. *Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v2-1.
ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, *Unifying two views on multiple
mean-payoff objectives in Markov decision processes*. IST Austria, 2015.
ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes, IST Austria, 51p.
mla: Chatterjee, Krishnendu, et al. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v2-1.
short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-02-23T00:00:00Z
date_updated: 2020-08-11T10:10:15Z
day: '23'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v2-1
file:
- access_level: open_access
checksum: 75284adec80baabdfe71ff9ebbc27445
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:03Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5525'
file_name: IST-2015-318-v2+1_main.pdf
file_size: 717630
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '51'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '327'
related_material:
record:
- id: '5429'
relation: earlier_version
status: public
- id: '1657'
relation: later_version
status: public
- id: '466'
relation: later_version
status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5429'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. \r\nThere have been two different views: (i) the
expectation semantics, where the goal is to optimize the expected mean-payoff
objective, and (ii) the satisfaction semantics, where the goal is to maximize
the probability of runs such that the mean-payoff value stays above a given vector.
\ \r\nWe consider the problem where the goal is to optimize the expectation under
the constraint that the satisfaction semantics is ensured, and thus consider a
generalization that unifies the existing semantics.\r\nOur problem captures the
notion of optimization with respect to strategies that are risk-averse (i.e.,
ensures certain probabilistic guarantee).\r\nOur main results are algorithms for
the decision problem which are always polynomial in the size of the MDP. We also
show that an approximation of the Pareto-curve can be computed in time polynomial
in the size of the MDP, and the approximation factor, but exponential in the number
of dimensions.\r\nFinally, we present a complete characterization of the strategy
complexity (in terms of memory bounds and randomization) required to solve our
problem."
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: Zuzana
full_name: Komarkova, Zuzana
last_name: Komarkova
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: Chatterjee K, Komarkova Z, Kretinsky J. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1
apa: Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). *Unifying two
views on multiple mean-payoff objectives in Markov decision processes*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1
chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. *Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.
ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, *Unifying two views on multiple
mean-payoff objectives in Markov decision processes*. IST Austria, 2015.
ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes, IST Austria, 41p.
mla: Chatterjee, Krishnendu, et al. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1.
short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:17Z
date_published: 2015-01-12T00:00:00Z
date_updated: 2020-08-11T10:10:15Z
day: '12'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v1-1
file:
- access_level: open_access
checksum: e4869a584567c506349abda9c8ec7db3
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:11Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5533'
file_name: IST-2015-318-v1+1_main.pdf
file_size: 689863
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '41'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '318'
related_material:
record:
- id: '5435'
relation: later_version
status: public
- id: '1657'
relation: later_version
status: public
- id: '466'
relation: later_version
status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5438'
abstract:
- lang: eng
text: "The edit distance between two words w1, w2 is the minimal number of word
operations (letter insertions, deletions, and substitutions) necessary to transform
w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance
is the minimal number k such that for every word from L1 there exists a word in
L2 with edit distance at most k. We study the edit distance computation problem
between pushdown automata and their subclasses.\r\nThe problem of computing edit
distance to a pushdown automaton is undecidable, and in practice, the interesting
question is to compute the edit distance from a pushdown automaton (the implementation,
a standard model for programs with recursion) to a regular language (the specification).
In this work, we present a complete picture of decidability and complexity for
deciding whether, for a given threshold k, the edit distance from a pushdown automaton
to a finite automaton is at most k. "
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. *Edit Distance for Pushdown
Automata*. IST Austria; 2015. doi:10.15479/AT:IST-2015-334-v1-1
apa: Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015).
*Edit distance for pushdown automata*. IST Austria. https://doi.org/10.15479/AT:IST-2015-334-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan
Otop. *Edit Distance for Pushdown Automata*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-334-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, *Edit distance
for pushdown automata*. IST Austria, 2015.
ista: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for
pushdown automata, IST Austria, 15p.
mla: Chatterjee, Krishnendu, et al. *Edit Distance for Pushdown Automata*.
IST Austria, 2015, doi:10.15479/AT:IST-2015-334-v1-1.
short: K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for
Pushdown Automata, IST Austria, 2015.
date_created: 2018-12-12T11:39:20Z
date_published: 2015-05-05T00:00:00Z
date_updated: 2020-08-11T10:10:15Z
day: '05'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-334-v1-1
file:
- access_level: open_access
checksum: 8a5f2d77560e552af87eb1982437a43b
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:56Z
date_updated: 2020-07-14T12:46:55Z
file_id: '5518'
file_name: IST-2015-334-v1+1_report.pdf
file_size: 422573
relation: main_file
file_date_updated: 2020-07-14T12:46:55Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '15'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '334'
related_material:
record:
- id: '1610'
relation: later_version
status: public
- id: '465'
relation: later_version
status: public
status: public
title: Edit distance for pushdown automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5436'
abstract:
- lang: eng
text: "Recently there has been a significant effort to handle 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, some basic system properties such as average
response time cannot be expressed using weighted automata, nor in any other know
decidable formalism. In this work, we introduce nested weighted automata as a
natural extension of weighted automata which makes it possible to express important
quantitative properties such as average response time.\r\nIn nested weighted automata,
a master automaton spins off and collects results from weighted slave automata,
each of which computes a quantity along a finite portion of an infinite word.
Nested weighted automata can be viewed as the quantitative analogue of monitor
automata, which are used in run-time verification. We establish an almost complete
decidability picture for the basic decision problems about nested weighted automata,
and illustrate their applicability in several domains. In particular, nested weighted
automata can be used to decide average response time properties."
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;
2015. doi:10.15479/AT:IST-2015-170-v2-2
apa: Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). *Nested weighted
automata*. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. *Nested Weighted
Automata*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, *Nested weighted automata*.
IST Austria, 2015.
ista: Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria,
29p.
mla: Chatterjee, Krishnendu, et al. *Nested Weighted Automata*. IST Austria,
2015, doi:10.15479/AT:IST-2015-170-v2-2.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria,
2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-04-24T00:00:00Z
date_updated: 2020-08-11T10:10:16Z
day: '24'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2015-170-v2-2
file:
- access_level: open_access
checksum: 3c402f47d3669c28d04d1af405a08e3f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:19Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5541'
file_name: IST-2015-170-v2+2_report.pdf
file_size: 569991
relation: main_file
file_date_updated: 2020-07-14T12:46:54Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '29'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '331'
related_material:
record:
- id: '5415'
relation: earlier_version
status: public
- id: '1656'
relation: later_version
status: public
- id: '467'
relation: later_version
status: public
status: public
title: Nested weighted automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5441'
abstract:
- lang: eng
text: We study algorithmic questions for concurrent systems where the transitions
are labeled from a complete, closed semiring, and path properties are algebraic
with semiring operations. The algebraic path properties can model dataflow analysis
problems, the shortest path problem, and many other natural problems that arise
in program analysis. We consider that each component of the concurrent system
is a graph with constant treewidth, a property satisfied by the controlflow graphs
of most programs. We allow for multiple possible queries, which arise naturally
in demand driven dataflow analysis. The study of multiple queries allows us to
consider the tradeoff between the resource usage of the one-time preprocessing
and for each individual query. The traditional approach constructs the product
graph of all components and applies the best-known graph algorithm on the product.
In this approach, even the answer to a single query requires the transitive closure
(i.e., the results of all possible queries), which provides no room for tradeoff
between preprocessing and query time. Our main contributions are algorithms that
significantly improve the worst-case running time of the traditional approach,
and provide various tradeoffs depending on the number of queries. For example,
in a concurrent system of two components, the traditional approach requires hexic
time in the worst case for answering one query as well as computing the transitive
closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive
closure can be computed in almost quartic time. Furthermore, we establish conditional
optimality results showing that the worst-case running time of our algorithms
cannot be improved without achieving major breakthroughs in graph algorithms (i.e.,
improving the worst-case bound for the shortest path problem in general graphs).
Preliminary experimental results show that our algorithms perform favorably on
several benchmarks.
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
- first_name: Amir
full_name: Goharshady, Amir
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
citation:
ama: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. *Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components*.
IST Austria; 2015. doi:10.15479/AT:IST-2015-340-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A.
(2015). *Algorithms for algebraic path properties in concurrent systems of constant
treewidth components*. IST Austria. https://doi.org/10.15479/AT:IST-2015-340-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady,
and Andreas Pavlogiannis. *Algorithms for Algebraic Path Properties in Concurrent
Systems of Constant Treewidth Components*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-340-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, *Algorithms
for algebraic path properties in concurrent systems of constant treewidth components*.
IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms
for algebraic path properties in concurrent systems of constant treewidth components,
IST Austria, 24p.
mla: Chatterjee, Krishnendu, et al. *Algorithms for Algebraic Path Properties
in Concurrent Systems of Constant Treewidth Components*. IST Austria, 2015,
doi:10.15479/AT:IST-2015-340-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components,
IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-07-11T00:00:00Z
date_updated: 2020-08-11T10:10:29Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-340-v1-1
file:
- access_level: open_access
checksum: df383dc62c94d7b2ea639aba088a76c6
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:09Z
date_updated: 2020-07-14T12:46:56Z
file_id: '5531'
file_name: IST-2015-340-v1+1_main.pdf
file_size: 861396
relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '24'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '340'
related_material:
record:
- id: '1437'
relation: later_version
status: public
- id: '5442'
relation: earlier_version
status: public
- id: '6009'
relation: later_version
status: public
status: public
title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5442'
abstract:
- lang: eng
text: "We study algorithmic questions for concurrent systems where the transitions
are labeled from a complete, closed semiring, and path properties are algebraic
with semiring operations. The algebraic path properties can model dataflow analysis
problems, the shortest path problem, and many other natural properties that arise
in program analysis.\r\nWe consider that each component of the concurrent system
is a graph with constant treewidth, and it is known that the controlflow graphs
of most programs have constant treewidth. We allow for multiple possible queries,
which arise naturally in demand driven dataflow analysis problems (e.g., alias
analysis). The study of multiple queries allows us to consider the tradeoff between
the resource usage of the \\emph{one-time} preprocessing and for \\emph{each individual}
query. The traditional approaches construct the product graph of all components
and apply the best-known graph algorithm on the product. In the traditional approach,
even the answer to a single query requires the transitive closure computation
(i.e., the results of all possible queries), which provides no room for tradeoff
between preprocessing and query time.\r\n\r\nOur main contributions are algorithms
that significantly improve the worst-case running time of the traditional approach,
and provide various tradeoffs depending on the number of queries. For example,
in a concurrent system of two components, the traditional approach requires hexic
time in the worst case for answering one query as well as computing the transitive
closure, whereas we show that with one-time preprocessing in almost cubic time,
\r\neach subsequent query can be answered in at most linear time, and even the
transitive closure can be computed in almost quartic time. Furthermore, we establish
conditional optimality results that show that the worst-case running times of
our algorithms cannot be improved without achieving major breakthroughs in graph
algorithms (such as improving \r\nthe worst-case bounds for the shortest path
problem in general graphs whose current best-known bound has not been improved
in five decades). Finally, we provide a prototype implementation of our algorithms
which significantly outperforms the existing algorithmic methods on several benchmarks."
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
- first_name: '3'
full_name: Anonymous, 3
last_name: Anonymous
- first_name: '4'
full_name: Anonymous, 4
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. *Algorithms for Algebraic
Path Properties in Concurrent Systems of Constant Treewidth Components*. IST
Austria; 2015.
apa: Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2015). *Algorithms
for algebraic path properties in concurrent systems of constant treewidth components*.
IST Austria.
chicago: Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. *Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components*.
IST Austria, 2015.
ieee: 1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, *Algorithms for
algebraic path properties in concurrent systems of constant treewidth components*.
IST Austria, 2015.
ista: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic
path properties in concurrent systems of constant treewidth components, IST Austria,
22p.
mla: Anonymous, 1, et al. *Algorithms for Algebraic Path Properties in Concurrent
Systems of Constant Treewidth Components*. IST Austria, 2015.
short: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic
Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria,
2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-07-14T00:00:00Z
date_updated: 2020-08-11T10:10:29Z
day: '14'
ddc:
- '000'
file:
- access_level: open_access
checksum: 98fd936102f3e057fc321ef6d316001d
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:37Z
date_updated: 2020-07-14T12:46:57Z
file_id: '5498'
file_name: IST-2015-343-v2+1_main.pdf
file_size: 658747
relation: main_file
- access_level: closed
checksum: b31d09b1241b59c75e1f42dadf09d258
content_type: text/plain
creator: dernst
date_created: 2019-04-16T12:36:08Z
date_updated: 2020-07-14T12:46:57Z
file_id: '6316'
file_name: IST-2015-343-v2+2_anonymous.txt
file_size: 139
relation: main_file
file_date_updated: 2020-07-14T12:46:57Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '344'
related_material:
record:
- id: '1437'
relation: later_version
status: public
- id: '5441'
relation: later_version
status: public
- id: '6009'
relation: later_version
status: public
scopus_import: 1
status: public
title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5412'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems. We focus on qualitative properties for MDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability.\r\nWe introduce a new simulation relation to capture
the refinement relation of MDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.\r\nWe present an automated technique for assume-guarantee style reasoning
for compositional analysis of MDPs with qualitative properties by giving a counter-example
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:
- 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: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Daca P, Chmelik M. *CEGAR for Qualitative Analysis of Probabilistic
Systems*. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v1-1
apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). *CEGAR for qualitative
analysis of probabilistic systems*. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v1-1
chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. *CEGAR for
Qualitative Analysis of Probabilistic Systems*. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v1-1.
ieee: K. Chatterjee, P. Daca, and M. Chmelik, *CEGAR for qualitative analysis
of probabilistic systems*. IST Austria, 2014.
ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic
systems, IST Austria, 31p.
mla: Chatterjee, Krishnendu, et al. *CEGAR for Qualitative Analysis of Probabilistic
Systems*. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v1-1.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-01-29T00:00:00Z
date_updated: 2020-07-14T23:04:53Z
day: '29'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v1-1
file:
- access_level: open_access
checksum: 4d6cda4bebed970926403ad6ad8c745f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:39Z
date_updated: 2020-07-14T12:46:47Z
file_id: '5500'
file_name: IST-2014-153-v1+1_main.pdf
file_size: 423322
relation: main_file
file_date_updated: 2020-07-14T12:46:47Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '31'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '153'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5414'
relation: later_version
status: public
- id: '5413'
relation: later_version
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5413'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems. We focus on qualitative properties for MDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability.\r\nWe introduce a new simulation relation to capture
the refinement relation of MDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.\r\nWe present an automated technique for assume-guarantee style reasoning
for compositional analysis of MDPs with qualitative properties by giving a counter-example
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:
- 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: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Daca P, Chmelik M. *CEGAR for Qualitative Analysis of Probabilistic
Systems*. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v2-2
apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). *CEGAR for qualitative
analysis of probabilistic systems*. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v2-2
chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. *CEGAR for
Qualitative Analysis of Probabilistic Systems*. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v2-2.
ieee: K. Chatterjee, P. Daca, and M. Chmelik, *CEGAR for qualitative analysis
of probabilistic systems*. IST Austria, 2014.
ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic
systems, IST Austria, 33p.
mla: Chatterjee, Krishnendu, et al. *CEGAR for Qualitative Analysis of Probabilistic
Systems*. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v2-2.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-02-06T00:00:00Z
date_updated: 2020-07-14T23:04:52Z
day: '06'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v2-2
file:
- access_level: open_access
checksum: ce4967a184d84863eec76c66cbac1614
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:17Z
date_updated: 2020-07-14T12:46:47Z
file_id: '5539'
file_name: IST-2014-153-v2+2_main.pdf
file_size: 606049
relation: main_file
file_date_updated: 2020-07-14T12:46:47Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '164'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5414'
relation: later_version
status: public
- id: '5412'
relation: earlier_version
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...