---
_id: '5437'
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.
\r\nThe 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.\r\nOur main
theoretical results are as follows.\r\nFirst, for constant treewidth graphs we
present an algorithm that approximates the mean-payoff value within a multiplicative
factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ 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 \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when
the output is $\\frac{a}{b}$, as compared to the previously best known algorithm
with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial
credit problem we show that (i)~for general graphs the problem can be solved in
$O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot
m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$
and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs
we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the
previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe 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
orcid: 0000-0003-4783-0389
- 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, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-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-330-v2-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-330-v2-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, 27p.
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-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:19Z
date_published: 2015-04-27T00:00:00Z
date_updated: 2023-02-23T12:26:05Z
day: '27'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-330-v2-1
file:
- access_level: open_access
checksum: f5917c20f84018b362d385c000a2e123
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:12Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5473'
file_name: IST-2015-330-v2+1_main.pdf
file_size: 1072137
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: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '333'
related_material:
record:
- id: '1607'
relation: later_version
status: public
- id: '5430'
relation: earlier_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: '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
orcid: 0000-0003-4783-0389
- 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, 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: 2023-02-23T12:26:22Z
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: '1607'
relation: later_version
status: public
- id: '5437'
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: 2023-02-23T10:08:48Z
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: '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
orcid: 0000-0003-4783-0389
- 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: 2023-02-23T12:20:08Z
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: '5440'
abstract:
- lang: eng
text: 'Evolution occurs in populations of reproducing individuals. The structure
of the population affects the outcome of the evolutionary process. Evolutionary
graph theory is a powerful approach to study this phenomenon. There are two graphs.
The interaction graph specifies who interacts with whom for payoff in the context
of evolution. The replacement graph specifies who competes with whom for reproduction.
The vertices of the two graphs are the same, and each vertex corresponds to an
individual of the population. The fitness (or the reproductive rate) is a non-negative
number, and depends on the payoff. A key quantity is the fixation probability
of a new mutant. It is defined as the probability that a newly introduced mutant
(on a single vertex) generates a lineage of offspring which eventually takes over
the entire population of resident individuals. The basic computational questions
are as follows: (i) the qualitative question asks whether the fixation probability
is positive; and (ii) the quantitative approximation question asks for an approximation
of the fixation probability. Our main results are as follows: First, we consider
a special case of the general problem, where the residents do not reproduce. We
show that the qualitative question is NP-complete, and the quantitative approximation
question is #P-complete, and the hardness results hold even in the special case
where the interaction and the replacement graphs coincide. Second, we show that
in general both the qualitative and the quantitative approximation questions are
PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds
even when the fitness is always positive.'
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
orcid: 0000-0003-4783-0389
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games
on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v2-2
apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity
of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v2-2
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity
of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v2-2.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolutionary
games on graphs. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary
games on graphs, IST Austria, 18p.
mla: Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs.
IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v2-2.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary
Games on Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-06-16T00:00:00Z
date_updated: 2023-02-23T12:26:10Z
day: '16'
ddc:
- '005'
- '576'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-323-v2-2
file:
- access_level: open_access
checksum: 66aace7d367032af97c15e35c9be9636
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:23Z
date_updated: 2020-07-14T12:46:56Z
file_id: '5484'
file_name: IST-2015-323-v2+2_main.pdf
file_size: 466161
relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '338'
related_material:
record:
- id: '5421'
relation: earlier_version
status: public
- id: '5432'
relation: earlier_version
status: public
status: public
title: The complexity of evolutionary games on graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...