---
_id: '5419'
abstract:
- lang: eng
text: "We consider the reachability and shortest path problems on low tree-width
graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize
W. We use O to hide polynomial factors of the inverse of the Ackermann function.
Our main contributions are three fold:\r\n1. For reachability, we present an algorithm
that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space,
and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries.
Note that for constant t our algorithm uses O(n·logn) time for preprocessing;
and O(n/W) time for single-source queries, which is faster than depth first search/breath
first search (after the preprocessing).\r\n2. We present an algorithm for shortest
path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for
pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus
query time trade-off algorithm for shortest path that, given any constant >0,
requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair
queries.\r\nOur algorithms improve all existing results, and use very simple data
structures."
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. Improved Algorithms for Reachability
and Shortest Path on Low Tree-Width Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-187-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Improved
algorithms for reachability and shortest path on low tree-width graphs. IST
Austria. https://doi.org/10.15479/AT:IST-2014-187-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-187-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Improved algorithms
for reachability and shortest path on low tree-width graphs. IST Austria,
2014.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for
reachability and shortest path on low tree-width graphs, IST Austria, 34p.
mla: Chatterjee, Krishnendu, et al. Improved Algorithms for Reachability and
Shortest Path on Low Tree-Width Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-187-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for
Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-04-14T00:00:00Z
date_updated: 2021-01-12T08:02:03Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-187-v1-1
file:
- access_level: open_access
checksum: c608e66030a4bf51d2d99b451f539b99
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:25Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5548'
file_name: IST-2014-187-v1+1_main_full_tech.pdf
file_size: 670031
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '34'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '187'
status: public
title: Improved algorithms for reachability and shortest path on low tree-width graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5418'
abstract:
- lang: eng
text: We consider multi-player graph games with partial-observation and parity objective.
While the decision problem for three-player games with a coalition of the first
and second players against the third player is undecidable, we present a decidability
result for partial-observation games where the first and third player are in a
coalition against the second player, thus where the second player is adversarial
but weaker due to partial-observation. We establish tight complexity bounds in
the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness
for parity objectives. The symmetric case of player 1 more informed than player
2 is much more complicated, and we show that already in the case where player
1 has perfect observation, memory of size non-elementary is necessary in general
for reachability objectives, and the problem is decidable for safety and reachability
objectives. Our results have tight connections with partial-observation stochastic
games for which we derive new complexity results.
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: Chatterjee K, Doyen L. Games with a Weak Adversary. IST Austria; 2014.
doi:10.15479/AT:IST-2014-176-v1-1
apa: Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary.
IST Austria. https://doi.org/10.15479/AT:IST-2014-176-v1-1
chicago: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-176-v1-1.
ieee: K. Chatterjee and L. Doyen, Games with a weak adversary. IST Austria,
2014.
ista: Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.
mla: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary.
IST Austria, 2014, doi:10.15479/AT:IST-2014-176-v1-1.
short: K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-03-22T00:00:00Z
date_updated: 2023-02-23T10:30:58Z
day: '22'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-176-v1-1
file:
- access_level: open_access
checksum: 1d6958aa60050e1c3e932c6e5f34c39f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:07Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5468'
file_name: IST-2014-176-v1+1_icalp_14.pdf
file_size: 328253
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '176'
related_material:
record:
- id: '2163'
relation: later_version
status: public
status: public
title: Games with a weak adversary
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5420'
abstract:
- lang: eng
text: 'We consider concurrent mean-payoff games, a very well-studied class of two-player
(player 1 vs player 2) zero-sum games on finite-state graphs where every transition
is assigned a reward between 0 and 1, and the payoff function is the long-run
average of the rewards. The value is the maximal expected payoff that player 1
can guarantee against all strategies of player 2. We consider the computation
of the set of states with value 1 under finite-memory strategies for player 1,
and our main results for the problem are as follows: (1) we present a polynomial-time
algorithm; (2) we show that whenever there is a finite-memory strategy, there
is a stationary strategy that does not need memory at all; and (3) we present
an optimal bound (which is double exponential) on the patience of stationary strategies
(where patience of a distribution is the inverse of the smallest positive probability
and represents a complexity measure of a stationary strategy).'
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
citation:
ama: Chatterjee K, Ibsen-Jensen R. The Value 1 Problem for Concurrent Mean-Payoff
Games. IST Austria; 2014. doi:10.15479/AT:IST-2014-191-v1-1
apa: Chatterjee, K., & Ibsen-Jensen, R. (2014). The value 1 problem for concurrent
mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2014-191-v1-1
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem
for Concurrent Mean-Payoff Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-191-v1-1.
ieee: K. Chatterjee and R. Ibsen-Jensen, The value 1 problem for concurrent mean-payoff
games. IST Austria, 2014.
ista: Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff
games, IST Austria, 49p.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for
Concurrent Mean-Payoff Games. IST Austria, 2014, doi:10.15479/AT:IST-2014-191-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff
Games, IST Austria, 2014.
date_created: 2018-12-12T11:39:14Z
date_published: 2014-04-14T00:00:00Z
date_updated: 2021-01-12T08:02:05Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-191-v1-1
file:
- access_level: open_access
checksum: 49e0fd3e62650346daf7dc04604f7a0a
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:58Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5520'
file_name: IST-2014-191-v1+1_main_full.pdf
file_size: 584368
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '49'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '191'
status: public
title: The value 1 problem for concurrent mean-payoff games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5424'
abstract:
- lang: eng
text: We consider partially observable Markov decision processes (POMDPs), that
are a standard framework for robotics applications to model uncertainties present
in the real world, with temporal logic specifications. All temporal logic specifications
in linear-time temporal logic (LTL) can be expressed as parity objectives. We
study the qualitative analysis problem for POMDPs with parity objectives that
asks whether there is a controller (policy) to ensure that the objective holds
with probability 1 (almost-surely). While the qualitative analysis of POMDPs with
parity objectives is undecidable, recent results show that when restricted to
finite-memory policies the problem is EXPTIME-complete. While the problem is intractable
in theory, we present a practical approach to solve the qualitative analysis problem.
We designed several heuristics to deal with the exponential complexity, and have
used our implementation on a number of well-known POMDP examples for robotics
applications. Our results provide the first practical approach to solve the qualitative
analysis of robot motion planning with LTL properties in the presence of uncertainty.
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: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Raghav
full_name: Gupta, Raghav
last_name: Gupta
- first_name: Ayush
full_name: Kanodia, Ayush
last_name: Kanodia
citation:
ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative Analysis of POMDPs
with Temporal Logic Specifications for Robotics Applications. IST Austria;
2014. doi:10.15479/AT:IST-2014-305-v1-1
apa: Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative
analysis of POMDPs with temporal logic specifications for robotics applications.
IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v1-1
chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics
Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v1-1.
ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, Qualitative analysis
of POMDPs with temporal logic specifications for robotics applications. IST
Austria, 2014.
ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of
POMDPs with temporal logic specifications for robotics applications, IST Austria,
12p.
mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal
Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v1-1.
short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of
POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria,
2014.
date_created: 2018-12-12T11:39:15Z
date_published: 2014-09-09T00:00:00Z
date_updated: 2023-02-23T12:25:52Z
day: '09'
ddc:
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-305-v1-1
file:
- access_level: open_access
checksum: 35009d5fad01198341e6c1a3353481b7
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:51Z
date_updated: 2020-07-14T12:46:51Z
file_id: '5512'
file_name: IST-2014-305-v1+1_main.pdf
file_size: 655774
relation: main_file
file_date_updated: 2020-07-14T12:46:51Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '12'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '305'
related_material:
record:
- id: '1732'
relation: later_version
status: public
- id: '5426'
relation: later_version
status: public
status: public
title: Qualitative analysis of POMDPs with temporal logic specifications for robotics
applications
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5426'
abstract:
- lang: eng
text: We consider partially observable Markov decision processes (POMDPs), that
are a standard framework for robotics applications to model uncertainties present
in the real world, with temporal logic specifications. All temporal logic specifications
in linear-time temporal logic (LTL) can be expressed as parity objectives. We
study the qualitative analysis problem for POMDPs with parity objectives that
asks whether there is a controller (policy) to ensure that the objective holds
with probability 1 (almost-surely). While the qualitative analysis of POMDPs with
parity objectives is undecidable, recent results show that when restricted to
finite-memory policies the problem is EXPTIME-complete. While the problem is intractable
in theory, we present a practical approach to solve the qualitative analysis problem.
We designed several heuristics to deal with the exponential complexity, and have
used our implementation on a number of well-known POMDP examples for robotics
applications. Our results provide the first practical approach to solve the qualitative
analysis of robot motion planning with LTL properties in the presence of uncertainty.
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: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Raghav
full_name: Gupta, Raghav
last_name: Gupta
- first_name: Ayush
full_name: Kanodia, Ayush
last_name: Kanodia
citation:
ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative Analysis of POMDPs
with Temporal Logic Specifications for Robotics Applications. IST Austria;
2014. doi:10.15479/AT:IST-2014-305-v2-1
apa: Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative
analysis of POMDPs with temporal logic specifications for robotics applications.
IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v2-1
chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics
Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v2-1.
ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, Qualitative analysis
of POMDPs with temporal logic specifications for robotics applications. IST
Austria, 2014.
ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of
POMDPs with temporal logic specifications for robotics applications, IST Austria,
10p.
mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal
Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v2-1.
short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of
POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria,
2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-09-29T00:00:00Z
date_updated: 2023-02-23T12:25:47Z
day: '29'
ddc:
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-305-v2-1
file:
- access_level: open_access
checksum: 730c0a8e97cf2712a884b2cc423f3919
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:15Z
date_updated: 2020-07-14T12:46:51Z
file_id: '5537'
file_name: IST-2014-305-v2+1_main2.pdf
file_size: 656019
relation: main_file
file_date_updated: 2020-07-14T12:46:51Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '10'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '311'
related_material:
record:
- id: '1732'
relation: later_version
status: public
- id: '5424'
relation: earlier_version
status: public
status: public
title: Qualitative analysis of POMDPs with temporal logic specifications for robotics
applications
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5423'
abstract:
- lang: eng
text: 'We present a flexible framework for the automated competitive analysis of
on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective
graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled
transition system, along with some optional safety, liveness, and/or limit-average
constraints for the adversary, we automatically compute the competitive ratio
of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility
and power of our approach by comparing the competitive ratio of several on-line
algorithms, including D(over), that have been proposed in the past, for various
tasksets. Our experimental results reveal that none of these algorithms is universally
optimal, in the sense that there are tasksets where other schedulers provide better
performance. Our framework is hence a very useful design tool for selecting optimal
algorithms for a given application. '
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: Alexander
full_name: Kössler, Alexander
last_name: Kössler
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
citation:
ama: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. A Framework for Automated
Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria;
2014. doi:10.15479/AT:IST-2014-300-v1-1
apa: Chatterjee, K., Kössler, A., Pavlogiannis, A., & Schmid, U. (2014). A
framework for automated competitive analysis of on-line scheduling of firm-deadline
tasks. IST Austria. https://doi.org/10.15479/AT:IST-2014-300-v1-1
chicago: Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich
Schmid. A Framework for Automated Competitive Analysis of On-Line Scheduling
of Firm-Deadline Tasks. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-300-v1-1.
ieee: K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, A framework
for automated competitive analysis of on-line scheduling of firm-deadline tasks.
IST Austria, 2014.
ista: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated
competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria,
14p.
mla: Chatterjee, Krishnendu, et al. A Framework for Automated Competitive Analysis
of On-Line Scheduling of Firm-Deadline Tasks. IST Austria, 2014, doi:10.15479/AT:IST-2014-300-v1-1.
short: K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated
Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria,
2014.
date_created: 2018-12-12T11:39:15Z
date_published: 2014-07-29T00:00:00Z
date_updated: 2023-02-23T10:11:15Z
day: '29'
ddc:
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-300-v1-1
file:
- access_level: open_access
checksum: 4b8fde4d9ef6653837f6803921d83032
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:53Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5514'
file_name: IST-2014-300-v1+1_main.pdf
file_size: 1270021
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '14'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '300'
related_material:
record:
- id: '1714'
relation: later_version
status: public
status: public
title: A framework for automated competitive analysis of on-line scheduling of firm-deadline
tasks
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5427'
abstract:
- lang: eng
text: 'We consider graphs with n nodes together with their tree-decomposition that
has b = O ( n ) bags and width t , on the standard RAM computational model with
wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution
is an algorithm that given a graph and its tree-decomposition as input, computes
a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph
in O ( b ) time and space, improving a long-standing (from 1992) bound of O (
n · log n ) time for constant treewidth graphs. Our second contribution is on
reachability queries for low treewidth graphs. We build on our tree-balancing
algorithm and present a data-structure for graph reachability that requires O
( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time
for pair queries, and O ( n · t · log t/ log n ) time for single-source queries.
For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time
for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically)
optimal and is faster than DFS/BFS when answering more than a constant number
of single-source queries.'
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. Optimal Tree-Decomposition
Balancing and Reachability on Low Treewidth Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-314-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Optimal
tree-decomposition balancing and reachability on low treewidth graphs. IST
Austria. https://doi.org/10.15479/AT:IST-2014-314-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-314-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Optimal tree-decomposition
balancing and reachability on low treewidth graphs. IST Austria, 2014.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition
balancing and reachability on low treewidth graphs, IST Austria, 24p.
mla: Chatterjee, Krishnendu, et al. Optimal Tree-Decomposition Balancing and
Reachability on Low Treewidth Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-314-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition
Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-11-05T00:00:00Z
date_updated: 2021-01-12T08:02:09Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-314-v1-1
file:
- access_level: open_access
checksum: 9d3b90bf4fff74664f182f2d95ef727a
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:10Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5471'
file_name: IST-2014-314-v1+1_long.pdf
file_size: 405561
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: '24'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '314'
status: public
title: Optimal tree-decomposition balancing and reachability on low treewidth graphs
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: '5421'
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 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.
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: (1) We show that the qualitative question is NP-complete and the quantitative
approximation question is #P-hard in the special case when the interaction and
the replacement graphs coincide and even with the restriction that the resident
individuals do not reproduce (which corresponds to an invading population taking
over an empty structure). (2) We show that in general the qualitative question
is PSPACE-complete and the quantitative approximation question is PSPACE-hard
and can be solved in exponential time.'
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 Evolution on Graphs.
IST Austria; 2014. doi:10.15479/AT:IST-2014-190-v2-2
apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2014). The complexity
of evolution on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2014-190-v2-2
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity
of Evolution on Graphs. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-190-v2-2.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolution
on graphs. IST Austria, 2014.
ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on
graphs, IST Austria, 27p.
mla: Chatterjee, Krishnendu, et al. The Complexity of Evolution on Graphs.
IST Austria, 2014, doi:10.15479/AT:IST-2014-190-v2-2.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on
Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:14Z
date_published: 2014-04-18T00:00:00Z
date_updated: 2023-02-23T12:26:33Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-190-v2-2
file:
- access_level: open_access
checksum: 42f3d8b563286eb0d903832bd9a848d3
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:16Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5538'
file_name: IST-2014-190-v2+2_main_full.pdf
file_size: 443529
relation: main_file
- access_level: open_access
checksum: 0c9a2fd822309719634495a35957e34d
content_type: application/pdf
creator: kschuh
date_created: 2019-09-06T07:30:20Z
date_updated: 2020-07-14T12:46:50Z
file_id: '6852'
file_name: IST-2014-190-v1+1_main_full.pdf
file_size: 440911
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
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: '190'
related_material:
record:
- id: '5432'
relation: later_version
status: public
- id: '5440'
relation: later_version
status: public
status: public
title: The complexity of evolution on graphs
type: technical_report
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '10885'
abstract:
- lang: eng
text: "Two-player games on graphs provide the theoretical framework for many important
problems such as reactive synthesis. While the traditional study of two-player
zero-sum games has been extended to multi-player games with several notions of
equilibria, they are decidable only for perfect-information games, whereas several
applications require imperfect-information games.\r\nIn this paper we propose
a new notion of equilibria, called doomsday equilibria, which is a strategy profile
such that all players satisfy their own objective, and if any coalition of players
deviates and violates even one of the players objective, then the objective of
every player is violated.\r\nWe present algorithms and complexity results for
deciding the existence of doomsday equilibria for various classes of ω-regular
objectives, both for imperfect-information games, and for perfect-information
games.We provide optimal complexity bounds for imperfect-information games, and
in most cases for perfect-information games."
acknowledgement: " Supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF
NFN Grant No\r\nS11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Emmanuel
full_name: Filiot, Emmanuel
last_name: Filiot
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
citation:
ama: 'Chatterjee K, Doyen L, Filiot E, Raskin J-F. Doomsday equilibria for omega-regular
games. In: VMCAI 2014: Verification, Model Checking, and Abstract Interpretation.
Vol 8318. Springer Nature; 2014:78-97. doi:10.1007/978-3-642-54013-4_5'
apa: 'Chatterjee, K., Doyen, L., Filiot, E., & Raskin, J.-F. (2014). Doomsday
equilibria for omega-regular games. In VMCAI 2014: Verification, Model Checking,
and Abstract Interpretation (Vol. 8318, pp. 78–97). San Diego, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-642-54013-4_5'
chicago: 'Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean-François
Raskin. “Doomsday Equilibria for Omega-Regular Games.” In VMCAI 2014: Verification,
Model Checking, and Abstract Interpretation, 8318:78–97. Springer Nature,
2014. https://doi.org/10.1007/978-3-642-54013-4_5.'
ieee: 'K. Chatterjee, L. Doyen, E. Filiot, and J.-F. Raskin, “Doomsday equilibria
for omega-regular games,” in VMCAI 2014: Verification, Model Checking, and
Abstract Interpretation, San Diego, CA, United States, 2014, vol. 8318, pp.
78–97.'
ista: 'Chatterjee K, Doyen L, Filiot E, Raskin J-F. 2014. Doomsday equilibria for
omega-regular games. VMCAI 2014: Verification, Model Checking, and Abstract Interpretation.
VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318,
78–97.'
mla: 'Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.”
VMCAI 2014: Verification, Model Checking, and Abstract Interpretation,
vol. 8318, Springer Nature, 2014, pp. 78–97, doi:10.1007/978-3-642-54013-4_5.'
short: 'K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification,
Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.'
conference:
end_date: 2014-01-21
location: San Diego, CA, United States
name: 'VMCAI: Verifcation, Model Checking, and Abstract Interpretation'
start_date: 2014-01-19
date_created: 2022-03-18T13:03:15Z
date_published: 2014-01-30T00:00:00Z
date_updated: 2023-02-23T12:52:24Z
day: '30'
department:
- _id: KrCh
doi: 10.1007/978-3-642-54013-4_5
ec_funded: 1
external_id:
arxiv:
- '1311.3238'
intvolume: ' 8318'
language:
- iso: eng
month: '01'
oa_version: Preprint
page: 78-97
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: 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: 'VMCAI 2014: Verification, Model Checking, and Abstract Interpretation'
publication_identifier:
eisbn:
- '9783642540134'
eissn:
- 1611-3349
isbn:
- '9783642540127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '681'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Doomsday equilibria for omega-regular games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8318
year: '2014'
...