---
_id: '1395'
abstract:
- lang: eng
text: In this thesis I studied various individual and social immune defences employed
by the invasive garden ant Lasius neglectus mostly against entomopathogenic fungi. The
first two chapters of this thesis address the phenomenon of 'social immunisation'.
Social immunisation, that is the immunological protection of group members due
to social contact to a pathogen-exposed nestmate, has been described in various
social insect species against different types of pathogens. However, in the case
of entomopathogenic fungi it has, so far, only been demonstrated that social immunisation
exists at all. Its underlying mechanisms r any other properties were, however,
unknown. In the first chapter of this thesis I identified the mechanistic basis
of social immunisation in L. neglectus against the entomopathogenous fungus Metarhizium.
I could show that nestmates of a pathogen-exposed individual contract low-level
infections due to social interactions. These low-level infections are, however,
non-lethal and cause an active stimulation of the immune system, which protects
the nestmates upon subsequent pathogen encounters. In the second chapter of this
thesis I investigated the specificity and colony level effects of social immunisation.
I demonstrated that the protection conferred by social immunisation is highly
specific, protecting ants only against the same pathogen strain. In addition,
depending on the respective context, social immunisation may even cause fitness
costs. I further showed that social immunisation crucially affects sanitary behaviour
and disease dynamics within ant groups. In the third chapter of this thesis I
studied the effects of the ectosymbiotic fungus Laboulbenia formicarum on its
host L. neglectus. Although Laboulbeniales are the largest order of insect-parasitic
fungi, research concerning host fitness consequence is sparse. I showed that highly
Laboulbenia-infected ants sustain fitness costs under resource limitation, however,
gain fitness benefits when exposed to an entomopathogenus fungus. These effects
are probably cause by a prophylactic upregulation of behavioural as well as physiological
immune defences in highly infected ants.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Matthias
full_name: Konrad, Matthias
id: 46528076-F248-11E8-B48F-1D18A9856A87
last_name: Konrad
citation:
ama: 'Konrad M. Immune defences in ants: Effects of social immunisation and a fungal
ectosymbiont in the ant Lasius neglectus. 2014.'
apa: 'Konrad, M. (2014). Immune defences in ants: Effects of social immunisation
and a fungal ectosymbiont in the ant Lasius neglectus. Institute of Science
and Technology Austria.'
chicago: 'Konrad, Matthias. “Immune Defences in Ants: Effects of Social Immunisation
and a Fungal Ectosymbiont in the Ant Lasius Neglectus.” Institute of Science and
Technology Austria, 2014.'
ieee: 'M. Konrad, “Immune defences in ants: Effects of social immunisation and a
fungal ectosymbiont in the ant Lasius neglectus,” Institute of Science and Technology
Austria, 2014.'
ista: 'Konrad M. 2014. Immune defences in ants: Effects of social immunisation and
a fungal ectosymbiont in the ant Lasius neglectus. Institute of Science and Technology
Austria.'
mla: 'Konrad, Matthias. Immune Defences in Ants: Effects of Social Immunisation
and a Fungal Ectosymbiont in the Ant Lasius Neglectus. Institute of Science
and Technology Austria, 2014.'
short: 'M. Konrad, Immune Defences in Ants: Effects of Social Immunisation and a
Fungal Ectosymbiont in the Ant Lasius Neglectus, Institute of Science and Technology
Austria, 2014.'
date_created: 2018-12-11T11:51:46Z
date_published: 2014-02-01T00:00:00Z
date_updated: 2023-09-07T11:38:56Z
day: '01'
degree_awarded: PhD
department:
- _id: SyCr
language:
- iso: eng
month: '02'
oa_version: None
page: '131'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '5814'
status: public
supervisor:
- first_name: Sylvia M
full_name: Cremer, Sylvia M
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
title: 'Immune defences in ants: Effects of social immunisation and a fungal ectosymbiont
in the ant Lasius neglectus'
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2014'
...
---
_id: '1402'
abstract:
- lang: eng
text: Phosphatidylinositol (Ptdlns) is a structural phospholipid that can be phosphorylated
into various lipid signaling molecules, designated polyphosphoinositides (PPIs).
The reversible phosphorylation of PPIs on the 3, 4, or 5 position of inositol
is performed by a set of organelle-specific kinases and phosphatases, and the
characteristic head groups make these molecules ideal for regulating biological
processes in time and space. In yeast and mammals, Ptdlns3P and Ptdlns(3,5)P2
play crucial roles in trafficking toward the lytic compartments, whereas the role
in plants is not yet fully understood. Here we identified the role of a land plant-specific
subgroup of PPI phosphatases, the suppressor of actin 2 (SAC2) to SAC5, during
vauolar trafficking and morphogenesis in Arabidopsis thaliana. SAC2-SAC5 localize
to the tonoplast along with Ptdlns3P, the presumable product of their activity.
in SAC gain- and loss-of-function mutants, the levels of Ptdlns monophosphates
and bisphosphates were changed, with opposite effects on the morphology of storage
and lytic vacuoles, and the trafficking toward the vacuoles was defective. Moreover,
multiple sac knockout mutants had an increased number of smaller storage and lytic
vacuoles, whereas extralarge vacuoles were observed in the overexpression lines,
correlating with various growth and developmental defects. The fragmented vacuolar
phenotype of sac mutants could be mimicked by treating wild-type seedlings with
Ptdlns(3,5)P2, corroborating that this PPI is important for vacuole morphology.
Taken together, these results provide evidence that PPIs, together with their
metabolic enzymes SAC2-SAC5, are crucial for vacuolar trafficking and for vacuolar
morphology and function in plants.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Petra
full_name: Marhavá, Petra
id: 44E59624-F248-11E8-B48F-1D18A9856A87
last_name: Marhavá
citation:
ama: Marhavá P. Molecular mechanisms of patterning and subcellular trafficking in
Arabidopsis thaliana. 2014.
apa: Marhavá, P. (2014). Molecular mechanisms of patterning and subcellular trafficking
in Arabidopsis thaliana. Institute of Science and Technology Austria.
chicago: Marhavá, Petra. “Molecular Mechanisms of Patterning and Subcellular Trafficking
in Arabidopsis Thaliana.” Institute of Science and Technology Austria, 2014.
ieee: P. Marhavá, “Molecular mechanisms of patterning and subcellular trafficking
in Arabidopsis thaliana,” Institute of Science and Technology Austria, 2014.
ista: Marhavá P. 2014. Molecular mechanisms of patterning and subcellular trafficking
in Arabidopsis thaliana. Institute of Science and Technology Austria.
mla: Marhavá, Petra. Molecular Mechanisms of Patterning and Subcellular Trafficking
in Arabidopsis Thaliana. Institute of Science and Technology Austria, 2014.
short: P. Marhavá, Molecular Mechanisms of Patterning and Subcellular Trafficking
in Arabidopsis Thaliana, Institute of Science and Technology Austria, 2014.
date_created: 2018-12-11T11:51:49Z
date_published: 2014-12-01T00:00:00Z
date_updated: 2023-09-07T11:39:38Z
day: '01'
degree_awarded: PhD
department:
- _id: JiFr
language:
- iso: eng
month: '12'
oa_version: None
page: '90'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '5805'
status: public
supervisor:
- first_name: Jiří
full_name: Friml, Jiří
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
title: Molecular mechanisms of patterning and subcellular trafficking in Arabidopsis
thaliana
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2014'
...
---
_id: '1403'
abstract:
- lang: eng
text: A variety of developmental and disease related processes depend on epithelial
cell sheet spreading. In order to gain insight into the biophysical mechanism(s)
underlying the tissue morphogenesis we studied the spreading of an epithelium
during the early development of the zebrafish embryo. In zebrafish epiboly the
enveloping cell layer (EVL), a simple squamous epithelium, spreads over the yolk
cell to completely engulf it at the end of gastrulation. Previous studies have
proposed that an actomyosin ring forming within the yolk syncytial layer (YSL)
acts as purse string that through constriction along its circumference pulls on
the margin of the EVL. Direct biophysical evidence for this hypothesis has however
been missing. The aim of the thesis was to understand how the actomyosin ring
may generate pulling forces onto the EVL and what cellular mechanism(s) may facilitate
the spreading of the epithelium. Using laser ablation to measure cortical tension
within the actomyosin ring we found an anisotropic tension distribution, which
was highest along the circumference of the ring. However the low degree of anisotropy
was incompatible with the actomyosin ring functioning as a purse string only.
Additionally, we observed retrograde cortical flow from vegetal parts of the ring
into the EVL margin. Interpreting the experimental data using a theoretical distribution
that models the tissues as active viscous gels led us to proposen that the actomyosin
ring has a twofold contribution to EVL epiboly. It not only acts as a purse string
through constriction along its circumference, but in addition constriction along
the width of the ring generates pulling forces through friction-resisted cortical
flow. Moreover, when rendering the purse string mechanism unproductive EVL epiboly
proceeded normally indicating that the flow-friction mechanism is sufficient to
drive the process. Aiming to understand what cellular mechanism(s) may facilitate
the spreading of the epithelium we found that tension-oriented EVL cell divisions
limit tissue anisotropy by releasing tension along the division axis and promote
epithelial spreading. Notably, EVL cells undergo ectopic cell fusion in conditions
in which oriented-cell division is impaired or the epithelium is mechanically
challenged. Taken together our study of EVL epiboly suggests a novel mechanism
of force generation for actomyosin rings through friction-resisted cortical flow
and highlights the importance of tension-oriented cell divisions in epithelial
morphogenesis.
acknowledged_ssus:
- _id: SSU
alternative_title:
- IST Austria Thesis
author:
- first_name: Martin
full_name: Behrndt, Martin
id: 3ECECA3A-F248-11E8-B48F-1D18A9856A87
last_name: Behrndt
citation:
ama: Behrndt M. Forces driving epithelial spreading in zebrafish epiboly. 2014.
apa: Behrndt, M. (2014). Forces driving epithelial spreading in zebrafish epiboly.
IST Austria.
chicago: Behrndt, Martin. “Forces Driving Epithelial Spreading in Zebrafish Epiboly.”
IST Austria, 2014.
ieee: M. Behrndt, “Forces driving epithelial spreading in zebrafish epiboly,” IST
Austria, 2014.
ista: Behrndt M. 2014. Forces driving epithelial spreading in zebrafish epiboly.
IST Austria.
mla: Behrndt, Martin. Forces Driving Epithelial Spreading in Zebrafish Epiboly.
IST Austria, 2014.
short: M. Behrndt, Forces Driving Epithelial Spreading in Zebrafish Epiboly, IST
Austria, 2014.
date_created: 2018-12-11T11:51:49Z
date_published: 2014-08-01T00:00:00Z
date_updated: 2023-10-17T12:16:58Z
day: '01'
department:
- _id: CaHe
language:
- iso: eng
month: '08'
oa_version: None
page: '91'
publication_status: published
publisher: IST Austria
publist_id: '5804'
related_material:
record:
- id: '2282'
relation: part_of_dissertation
status: public
- id: '2950'
relation: part_of_dissertation
status: public
- id: '3373'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
title: Forces driving epithelial spreading in zebrafish epiboly
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '1404'
abstract:
- lang: eng
text: "The co-evolution of hosts and pathogens is characterized by continuous adaptations
of both parties. Pathogens of social insects need to adapt towards disease defences
at two levels: 1) individual immunity of each colony member consisting of behavioural
defence strategies as well as humoral and cellular immune responses and 2) social
immunity that is collectively performed by all group members comprising behavioural,
physiological and organisational defence strategies.\r\n\r\nTo disentangle the
selection pressure on pathogens by the collective versus individual level of disease
defence in social insects, we performed an evolution experiment using the Argentine
Ant, Linepithema humile, as a host and a mixture of the general insect pathogenic
fungus Metarhizium spp. (6 strains) as a pathogen. We allowed pathogen evolution
over 10 serial host passages to two different evolution host treatments: (1) only
individual host immunity in a single host treatment, and (2) simultaneously acting
individual and social immunity in a social host treatment, in which an exposed
ant was accompanied by two untreated nestmates.\r\n\r\nBefore starting the pathogen
evolution experiment, the 6 Metarhizium spp. strains were characterised concerning
conidiospore size killing rates in singly and socially reared ants, their competitiveness
under coinfecting conditions and their influence on ant behaviour. We analysed
how the ancestral atrain mixture changed in conidiospere size, killing rate and
strain composition dependent on host treatment (single or social hosts) during
10 passages and found that killing rate and conidiospere size of the pathogen
increased under both evolution regimes, but different depending on host treatment.\r\n\r\nTesting
the evolved strain mixtures that evolved under either the single or social host
treatment under both single and social current rearing conditions in a full factorial
design experiment revealed that the additional collective defences in insect societies
add new selection pressure for their coevolving pathogens that compromise their
ability to adapt to its host at the group level. To our knowledge, this is the
first study directly measuring the influence of social immunity on pathogen evolution."
acknowledgement: This work was funded by the DFG and the ERC.
alternative_title:
- IST Austria Thesis
author:
- first_name: Miriam
full_name: Stock, Miriam
id: 42462816-F248-11E8-B48F-1D18A9856A87
last_name: Stock
citation:
ama: Stock M. Evolution of a fungal pathogen towards individual versus social immunity
in ants. 2014.
apa: Stock, M. (2014). Evolution of a fungal pathogen towards individual versus
social immunity in ants. IST Austria.
chicago: Stock, Miriam. “Evolution of a Fungal Pathogen towards Individual versus
Social Immunity in Ants.” IST Austria, 2014.
ieee: M. Stock, “Evolution of a fungal pathogen towards individual versus social
immunity in ants,” IST Austria, 2014.
ista: Stock M. 2014. Evolution of a fungal pathogen towards individual versus social
immunity in ants. IST Austria.
mla: Stock, Miriam. Evolution of a Fungal Pathogen towards Individual versus
Social Immunity in Ants. IST Austria, 2014.
short: M. Stock, Evolution of a Fungal Pathogen towards Individual versus Social
Immunity in Ants, IST Austria, 2014.
date_created: 2018-12-11T11:51:49Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2021-01-12T06:50:30Z
day: '01'
department:
- _id: SyCr
language:
- iso: eng
month: '04'
oa_version: None
page: '101'
publication_status: published
publisher: IST Austria
publist_id: '5803'
status: public
supervisor:
- first_name: Sylvia M
full_name: Cremer, Sylvia M
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
title: Evolution of a fungal pathogen towards individual versus social immunity in
ants
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5411'
abstract:
- lang: eng
text: "Model-based testing is a promising technology for black-box software and
hardware testing, in which test cases are generated automatically from high-level
specifications. Nowadays, systems typically consist of multiple interacting components
and, due to their complexity, testing presents a considerable portion of the effort
and cost in the design process. Exploiting the compositional structure of system
specifications can considerably reduce the effort in model-based testing. Moreover,
inferring properties about the system from testing its individual components allows
the designer to reduce the amount of integration testing.\r\nIn this paper, we
study compositional properties of the IOCO-testing theory. We propose a new approach
to composition and hiding operations, inspired by contract-based design and interface
theories. These operations preserve behaviors that are compatible under composition
and hiding, and prune away incompatible ones. The resulting specification characterizes
the input sequences for which the unit testing of components is sufficient to
infer the correctness of component integration without the need for further tests.
We provide a methodology that uses these results to minimize integration testing
effort, but also to detect potential weaknesses in specifications. While we focus
on asynchronous models and the IOCO conformance relation, the resulting methodology
can be applied to a broader class of systems."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Willibald
full_name: Krenn, Willibald
last_name: Krenn
- first_name: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
citation:
ama: Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional Specifications
for IOCO Testing. IST Austria; 2014. doi:10.15479/AT:IST-2014-148-v2-1
apa: Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional
specifications for IOCO testing. IST Austria. https://doi.org/10.15479/AT:IST-2014-148-v2-1
chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic.
Compositional Specifications for IOCO Testing. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-148-v2-1.
ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, Compositional specifications
for IOCO testing. IST Austria, 2014.
ista: Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications
for IOCO testing, IST Austria, 20p.
mla: Daca, Przemyslaw, et al. Compositional Specifications for IOCO Testing.
IST Austria, 2014, doi:10.15479/AT:IST-2014-148-v2-1.
short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications
for IOCO Testing, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-01-28T00:00:00Z
date_updated: 2023-02-23T10:31:07Z
day: '28'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-148-v2-1
file:
- access_level: open_access
checksum: 0e03aba625cc334141a3148432aa5760
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:21Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5543'
file_name: IST-2014-148-v2+1_main_tr.pdf
file_size: 534732
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '152'
related_material:
record:
- id: '2167'
relation: later_version
status: public
status: public
title: Compositional specifications for IOCO testing
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '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: 2023-02-23T12:25:18Z
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: '5413'
relation: later_version
status: public
- id: '5414'
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: 2023-02-23T12:25:18Z
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: '5412'
relation: earlier_version
status: public
- id: '5414'
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: '5414'
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.
\r\nWe 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-v3-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-v3-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-v3-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, 33p.
mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v3-1.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-07T00:00:00Z
date_updated: 2023-02-23T12:25:15Z
day: '07'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v3-1
file:
- access_level: open_access
checksum: 87b93fe9af71fc5c94b0eb6151537e11
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:03Z
date_updated: 2020-07-14T12:46:48Z
file_id: '5464'
file_name: IST-2014-153-v3+1_main.pdf
file_size: 606227
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: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '165'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5412'
relation: earlier_version
status: public
- id: '5413'
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'
...
---
_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: '5416'
abstract:
- lang: eng
text: As hybrid systems involve continuous behaviors, they should be evaluated by
quantitative methods, rather than qualitative methods. In this paper we adapt
a quantitative framework, called model measuring, to the hybrid systems domain.
The model-measuring problem asks, given a model M and a specification, what is
the maximal distance such that all models within that distance from M satisfy
(or violate) the specification. A distance function on models is given as part
of the input of the problem. Distances, especially related to continuous behaviors
are more natural in the hybrid case than the discrete case. We are interested
in distances represented by monotonic hybrid automata, a hybrid counterpart of
(discrete) weighted automata, whose recognized timed languages are monotone (w.r.t.
inclusion) in the values of parameters.The contributions of this paper are twofold.
First, we give sufficient conditions under which the model-measuring problem can
be solved. Second, we discuss the modeling of distances and applications of the
model-measuring problem.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Henzinger TA, Otop J. Model Measuring for Hybrid Systems. IST Austria;
2014. doi:10.15479/AT:IST-2014-171-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems.
IST Austria. https://doi.org/10.15479/AT:IST-2014-171-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-171-v1-1.
ieee: T. A. Henzinger and J. Otop, Model measuring for hybrid systems. IST
Austria, 2014.
ista: Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria,
22p.
mla: Henzinger, Thomas A., and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014, doi:10.15479/AT:IST-2014-171-v1-1.
short: T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria,
2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:33:21Z
day: '19'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-171-v1-1
file:
- access_level: open_access
checksum: 445456d22371e4e49aad2b9a0c13bf80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:32Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5492'
file_name: IST-2014-171-v1+1_report.pdf
file_size: 712077
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '171'
related_material:
record:
- id: '2217'
relation: later_version
status: public
status: public
title: Model measuring for hybrid systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5417'
abstract:
- lang: eng
text: "We define the model-measuring problem: given a model M and specification
φ, what is the maximal distance ρ such that all models M'within distance ρ from
M satisfy (or violate)φ. The model measuring problem presupposes a distance function
on models. We concentrate on automatic distance functions, which are defined by
weighted automata.\r\nThe model-measuring problem subsumes several generalizations
of the classical model-checking problem, in particular, quantitative model-checking
problems that measure the degree of satisfaction of a specification, and robustness
problems that measure how much a model can be perturbed without violating the
specification.\r\nWe show that for automatic distance functions, and ω-regular
linear-time and branching-time specifications, the model-measuring problem can
be solved.\r\nWe use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for standard word and tree automata by the optimal-weight
question for the weighted versions of these automata. We consider weighted automata
that accumulate weights by maximizing, summing, discounting, and limit averaging.
\r\nWe give several examples of using the model-measuring problem to compute various
notions of robustness and quantitative satisfaction for temporal specifications."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Henzinger TA, Otop J. From Model Checking to Model Measuring. IST Austria;
2014. doi:10.15479/AT:IST-2014-172-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). From model checking to model measuring.
IST Austria. https://doi.org/10.15479/AT:IST-2014-172-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-172-v1-1.
ieee: T. A. Henzinger and J. Otop, From model checking to model measuring.
IST Austria, 2014.
ista: Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria,
14p.
mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014, doi:10.15479/AT:IST-2014-172-v1-1.
short: T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria,
2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:38:10Z
day: '19'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-172-v1-1
file:
- access_level: open_access
checksum: fcc3eab903cfcd3778b338d2d0d44d18
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:20Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5481'
file_name: IST-2014-172-v1+1_report.pdf
file_size: 383052
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '14'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '175'
related_material:
record:
- id: '2327'
relation: later_version
status: public
status: public
title: From model checking to model measuring
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '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: '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: '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: '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: '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: '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: '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: '5428'
abstract:
- lang: eng
text: "Simulation is an attractive alternative for language inclusion for automata
as it is an under-approximation of language inclusion, but usually has much lower
complexity. For non-deterministic automata, while language inclusion is PSPACE-complete,
simulation can be computed in polynomial time. Simulation has also been extended
in two orthogonal directions, namely, (1) fair simulation, for simulation over
specified set of infinite runs; and (2) quantitative simulation, for simulation
between weighted automata. Again, while fair trace inclusion is PSPACE-complete,
fair simulation can be computed in polynomial time. For weighted automata, the
(quantitative) language inclusion problem is undecidable for mean-payoff automata
and the decidability is open for discounted-sum automata, whereas the (quantitative)
simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial
time algorithms.\r\n\r\nIn this work, we study (quantitative) simulation for weighted
automata with Büchi acceptance conditions, i.e., we generalize fair simulation
from non-weighted automata to weighted automata. We show that imposing Büchi acceptance
conditions on weighted automata changes many fundamental properties of the simulation
games. For example, whereas for mean-payoff and discounted-sum games, the players
do not need memory to play optimally; we show in contrast that for simulation
games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal
strategies for both players require infinite memory in general, and (ii) for discounted-sum
objectives, optimal strategies need not exist for both players. While the simulation
games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory
requirements for mean-payoff objectives) as compared to their counterpart without
Büchi acceptance conditions, we still present pseudo-polynomial time algorithms
to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff
and weighted discounted-sum automata."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: Chatterjee K, Henzinger TA, Otop J, Velner Y. Quantitative Fair Simulation
Games. IST Austria; 2014. doi:10.15479/AT:IST-2014-315-v1-1
apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Velner, Y. (2014). Quantitative
fair simulation games. IST Austria. https://doi.org/10.15479/AT:IST-2014-315-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner.
Quantitative Fair Simulation Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-315-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, Quantitative fair
simulation games. IST Austria, 2014.
ista: Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation
games, IST Austria, 26p.
mla: Chatterjee, Krishnendu, et al. Quantitative Fair Simulation Games. IST
Austria, 2014, doi:10.15479/AT:IST-2014-315-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation
Games, IST Austria, 2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-12-05T00:00:00Z
date_updated: 2023-09-20T12:07:48Z
day: '05'
ddc:
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.15479/AT:IST-2014-315-v1-1
file:
- access_level: open_access
checksum: b1d573bc04365625ff9974880c0aa807
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:59Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5521'
file_name: IST-2014-315-v1+1_report.pdf
file_size: 531046
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '26'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '315'
related_material:
record:
- id: '1066'
relation: later_version
status: public
status: public
title: Quantitative fair simulation games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...