---
_id: '3853'
abstract:
- lang: eng
text: 'Quantitative languages are an extension of boolean languages that assign
to each word a real number. Mean-payoff automata are finite automata with numerical
weights on transitions that assign to each infinite path the long-run average
of the transition weights. When the mode of branching of the automaton is deterministic,
nondeterministic, or alternating, the corresponding class of quantitative languages
is not robust as it is not closed under the pointwise operations of max, min,
sum, and numerical complement. Nondeterministic and alternating mean-payoff automata
are not decidable either, as the quantitative generalization of the problems of
universality and language inclusion is undecidable. We introduce a new class of
quantitative languages, defined by mean-payoff automaton expressions, which is
robust and decidable: it is closed under the four pointwise operations, and we
show that all decision problems are decidable for this class. Mean-payoff automaton
expressions subsume deterministic meanpayoff automata, and we show that they have
expressive power incomparable to nondeterministic and alternating mean-payoff
automata. We also present for the first time an algorithm to compute distance
between two quantitative languages, and in our case the quantitative languages
are given as mean-payoff automaton expressions.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- 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: Philippe
full_name: Rannou, Philippe
last_name: Rannou
citation:
ama: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. Mean-payoff
automaton expressions. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2010:269-283. doi:10.1007/978-3-642-15375-4_19'
apa: 'Chatterjee, K., Doyen, L., Edelsbrunner, H., Henzinger, T. A., & Rannou,
P. (2010). Mean-payoff automaton expressions (Vol. 6269, pp. 269–283). Presented
at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.1007/978-3-642-15375-4_19'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Herbert Edelsbrunner, Thomas A Henzinger,
and Philippe Rannou. “Mean-Payoff Automaton Expressions,” 6269:269–83. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_19.
ieee: 'K. Chatterjee, L. Doyen, H. Edelsbrunner, T. A. Henzinger, and P. Rannou,
“Mean-payoff automaton expressions,” presented at the CONCUR: Concurrency Theory,
Paris, France, 2010, vol. 6269, pp. 269–283.'
ista: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. 2010. Mean-payoff
automaton expressions. CONCUR: Concurrency Theory, LNCS, vol. 6269, 269–283.'
mla: Chatterjee, Krishnendu, et al. Mean-Payoff Automaton Expressions. Vol.
6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–83, doi:10.1007/978-3-642-15375-4_19.
short: K. Chatterjee, L. Doyen, H. Edelsbrunner, T.A. Henzinger, P. Rannou, in:,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–283.
conference:
end_date: 2010-09-03
location: Paris, France
name: 'CONCUR: Concurrency Theory'
start_date: 2010-08-31
date_created: 2018-12-11T12:05:31Z
date_published: 2010-11-18T00:00:00Z
date_updated: 2021-01-12T07:52:40Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: HeEd
- _id: ToHe
doi: 10.1007/978-3-642-15375-4_19
ec_funded: 1
file:
- access_level: open_access
checksum: 4f753ae99d076553fb8733e2c8b390e2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:41Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5163'
file_name: IST-2012-62-v1+1_Mean-payoff_automaton_expressions.pdf
file_size: 233260
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6269'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 269 - 283
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2328'
pubrep_id: '62'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mean-payoff automaton expressions
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...
---
_id: '3854'
abstract:
- lang: eng
text: 'Graph games of infinite length provide a natural model for open reactive
systems: one player (Eve) represents the controller and the other player (Adam)
represents the environment. The evolution of the system depends on the decisions
of both players. The specification for the system is usually given as an ω-regular
language L over paths and Eve’s goal is to ensure that the play belongs to L irrespective
of Adam’s behaviour. The classical notion of winning strategies fails to capture
several interesting scenarios. For example, strong fairness (Streett) conditions
are specified by a number of request-grant pairs and require every pair that is
requested infinitely often to be granted infinitely often: Eve might win just
by preventing Adam from making any new request, but a “better” strategy would
allow Adam to make as many requests as possible and still ensure fairness. To
address such questions, we introduce the notion of obliging games, where Eve has
to ensure a strong condition Φ, while always allowing Adam to satisfy a weak condition
Ψ. We present a linear time reduction of obliging games with two Muller conditions
Φ and Ψ to classical Muller games. We consider obliging Streett games and show
they are co-NP complete, and show a natural quantitative optimisation problem
for obliging Streett games is in FNP. We also show how obliging games can provide
new and interesting semantics for multi-player games.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Florian
full_name: Horn, Florian
id: 37327ACE-F248-11E8-B48F-1D18A9856A87
last_name: Horn
- first_name: Christof
full_name: Löding, Christof
last_name: Löding
citation:
ama: 'Chatterjee K, Horn F, Löding C. Obliging games. In: Vol 6269. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2010:284-296. doi:10.1007/978-3-642-15375-4_20'
apa: 'Chatterjee, K., Horn, F., & Löding, C. (2010). Obliging games (Vol. 6269,
pp. 284–296). Presented at the CONCUR: Concurrency Theory, Paris, France: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-642-15375-4_20'
chicago: Chatterjee, Krishnendu, Florian Horn, and Christof Löding. “Obliging Games,”
6269:284–96. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_20.
ieee: 'K. Chatterjee, F. Horn, and C. Löding, “Obliging games,” presented at the
CONCUR: Concurrency Theory, Paris, France, 2010, vol. 6269, pp. 284–296.'
ista: 'Chatterjee K, Horn F, Löding C. 2010. Obliging games. CONCUR: Concurrency
Theory, LNCS, vol. 6269, 284–296.'
mla: Chatterjee, Krishnendu, et al. Obliging Games. Vol. 6269, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2010, pp. 284–96, doi:10.1007/978-3-642-15375-4_20.
short: K. Chatterjee, F. Horn, C. Löding, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2010, pp. 284–296.
conference:
end_date: 2010-09-03
location: Paris, France
name: 'CONCUR: Concurrency Theory'
start_date: 2010-08-31
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-08T00:00:00Z
date_updated: 2021-01-12T07:52:41Z
day: '08'
department:
- _id: KrCh
doi: 10.1007/978-3-642-15375-4_20
intvolume: ' 6269'
language:
- iso: eng
month: '09'
oa_version: None
page: 284 - 296
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2327'
quality_controlled: '1'
scopus_import: 1
status: public
title: Obliging games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...
---
_id: '3855'
abstract:
- lang: eng
text: 'We study observation-based strategies for partially-observable Markov decision
processes (POMDPs) with parity objectives. An observation-based strategy relies
on partial information about the history of a play, namely, on the past sequence
of observations. We consider qualitative analysis problems: given a POMDP with
a parity objective, decide whether there exists an observation-based strategy
to achieve the objective with probability 1 (almost-sure winning), or with positive
probability (positive winning). Our main results are twofold. First, we present
a complete picture of the computational complexity of the qualitative analysis
problem for POMDPs with parity objectives and its subclasses: safety, reachability,
Büchi, and coBüchi objectives. We establish several upper and lower bounds that
were not known in the literature. Second, we give optimal bounds (matching upper
and lower bounds) for the memory required by pure and randomized observation-based
strategies for each class of objectives.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA. Qualitative analysis of partially-observable
Markov Decision Processes. In: Vol 6281. Springer; 2010:258-269. doi:10.1007/978-3-642-15155-2_24'
apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2010). Qualitative analysis
of partially-observable Markov Decision Processes (Vol. 6281, pp. 258–269). Presented
at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic:
Springer. https://doi.org/10.1007/978-3-642-15155-2_24'
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Qualitative
Analysis of Partially-Observable Markov Decision Processes,” 6281:258–69. Springer,
2010. https://doi.org/10.1007/978-3-642-15155-2_24.
ieee: 'K. Chatterjee, L. Doyen, and T. A. Henzinger, “Qualitative analysis of partially-observable
Markov Decision Processes,” presented at the MFCS: Mathematical Foundations of
Computer Science, Brno, Czech Republic, 2010, vol. 6281, pp. 258–269.'
ista: 'Chatterjee K, Doyen L, Henzinger TA. 2010. Qualitative analysis of partially-observable
Markov Decision Processes. MFCS: Mathematical Foundations of Computer Science,
LNCS, vol. 6281, 258–269.'
mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of Partially-Observable
Markov Decision Processes. Vol. 6281, Springer, 2010, pp. 258–69, doi:10.1007/978-3-642-15155-2_24.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2010, pp. 258–269.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:32Z
date_published: 2010-08-01T00:00:00Z
date_updated: 2023-02-23T12:24:22Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15155-2_24
ec_funded: 1
file:
- access_level: open_access
checksum: b6c82ec82f194e5b0ab7c1c3800e4580
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:51Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5038'
file_name: IST-2012-61-v1+1_Qualitative_analysis_of_partially-observable_Markov_Decision_Processes.pdf
file_size: 173948
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6281'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 258 - 269
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2326'
pubrep_id: '61'
quality_controlled: '1'
related_material:
record:
- id: '5395'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Qualitative analysis of partially-observable Markov Decision Processes
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3856'
abstract:
- lang: eng
text: 'We consider two-player zero-sum games on graphs. These games can be classified
on the basis of the information of the players and on the mode of interaction
between them. On the basis of information the classification is as follows: (a)
partial-observation (both players have partial view of the game); (b) one-sided
complete-observation (one player has complete observation); and (c) complete-observation
(both players have complete view of the game). On the basis of mode of interaction
we have the following classification: (a) concurrent (players interact simultaneously);
and (b) turn-based (players interact in turn). The two sources of randomness in
these games are randomness in transition function and randomness in strategies.
In general, randomized strategies are more powerful than deterministic strategies,
and randomness in transitions gives more general classes of games. We present
a complete characterization for the classes of games where randomness is not helpful
in: (a) the transition function (probabilistic transition can be simulated by
deterministic transition); and (b) strategies (pure strategies are as powerful
as randomized strategies). As consequence of our characterization we obtain new
undecidability results for these games. '
acknowledgement: This research was supported by the European Union project COMBEST
and the European Network of Excellence ArtistDesign.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Hugo
full_name: Gimbert, Hugo
last_name: Gimbert
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Doyen L, Gimbert H, Henzinger TA. Randomness for free. In: Vol
6281. Springer; 2010:246-257. doi:10.1007/978-3-642-15155-2_23'
apa: 'Chatterjee, K., Doyen, L., Gimbert, H., & Henzinger, T. A. (2010). Randomness
for free (Vol. 6281, pp. 246–257). Presented at the MFCS: Mathematical Foundations
of Computer Science, Brno, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-15155-2_23'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger.
“Randomness for Free,” 6281:246–57. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_23.
ieee: 'K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for
free,” presented at the MFCS: Mathematical Foundations of Computer Science, Brno,
Czech Republic, 2010, vol. 6281, pp. 246–257.'
ista: 'Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2010. Randomness for free.
MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6281, 246–257.'
mla: Chatterjee, Krishnendu, et al. Randomness for Free. Vol. 6281, Springer,
2010, pp. 246–57, doi:10.1007/978-3-642-15155-2_23.
short: K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, in:, Springer, 2010,
pp. 246–257.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-06T00:00:00Z
date_updated: 2023-02-23T10:12:00Z
day: '06'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15155-2_23
ec_funded: 1
intvolume: ' 6281'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1006.0673v1
month: '09'
oa: 1
oa_version: Preprint
page: 246 - 257
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2325'
pubrep_id: '60'
quality_controlled: '1'
related_material:
record:
- id: '1731'
relation: later_version
status: public
scopus_import: 1
status: public
title: Randomness for free
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3857'
abstract:
- lang: eng
text: We consider probabilistic automata on infinite words with acceptance defined
by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider
quantitative and qualitative decision problems. We present extensions and adaptations
of proofs for probabilistic finite automata and present an almost complete characterization
of the decidability and undecidability frontier of the quantitative and qualitative
decision problems for probabilistic automata on infinite words.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Henzinger TA. Probabilistic Automata on infinite words: decidability
and undecidability results. In: Vol 6252. Springer; 2010:1-16. doi:10.1007/978-3-642-15643-4_1'
apa: 'Chatterjee, K., & Henzinger, T. A. (2010). Probabilistic Automata on infinite
words: decidability and undecidability results (Vol. 6252, pp. 1–16). Presented
at the ATVA: Automated Technology for Verification and Analysis, Singapore, Singapore:
Springer. https://doi.org/10.1007/978-3-642-15643-4_1'
chicago: 'Chatterjee, Krishnendu, and Thomas A Henzinger. “Probabilistic Automata
on Infinite Words: Decidability and Undecidability Results,” 6252:1–16. Springer,
2010. https://doi.org/10.1007/978-3-642-15643-4_1.'
ieee: 'K. Chatterjee and T. A. Henzinger, “Probabilistic Automata on infinite words:
decidability and undecidability results,” presented at the ATVA: Automated Technology
for Verification and Analysis, Singapore, Singapore, 2010, vol. 6252, pp. 1–16.'
ista: 'Chatterjee K, Henzinger TA. 2010. Probabilistic Automata on infinite words:
decidability and undecidability results. ATVA: Automated Technology for Verification
and Analysis, LNCS, vol. 6252, 1–16.'
mla: 'Chatterjee, Krishnendu, and Thomas A. Henzinger. Probabilistic Automata
on Infinite Words: Decidability and Undecidability Results. Vol. 6252, Springer,
2010, pp. 1–16, doi:10.1007/978-3-642-15643-4_1.'
short: K. Chatterjee, T.A. Henzinger, in:, Springer, 2010, pp. 1–16.
conference:
end_date: 2010-09-24
location: Singapore, Singapore
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2010-09-21
date_created: 2018-12-11T12:05:33Z
date_published: 2010-10-12T00:00:00Z
date_updated: 2023-02-23T12:24:14Z
day: '12'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15643-4_1
ec_funded: 1
intvolume: ' 6252'
language:
- iso: eng
month: '10'
oa_version: None
page: 1 - 16
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2324'
pubrep_id: '28'
quality_controlled: '1'
related_material:
record:
- id: '5392'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Probabilistic Automata on infinite words: decidability and undecidability
results'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6252
year: '2010'
...
---
_id: '3858'
abstract:
- lang: eng
text: 'We consider two-player zero-sum games on graphs. On the basis of the information
available to the players these games can be classified as follows: (a) partial-observation
(both players have partial view of the game); (b) one-sided partial-observation
(one player has partial-observation and the other player has complete-observation);
and (c) complete-observation (both players have com- plete view of the game).
We survey the complexity results for the problem of de- ciding the winner in various
classes of partial-observation games with ω-regular winning conditions specified
as parity objectives. We present a reduction from the class of parity objectives
that depend on sequence of states of the game to the sub-class of parity objectives
that only depend on the sequence of observations. We also establish that partial-observation
acyclic games are PSPACE-complete.'
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
citation:
ama: 'Chatterjee K, Doyen L. The complexity of partial-observation parity games.
In: Vol 6397. Springer; 2010:1-14. doi:10.1007/978-3-642-16242-8_1'
apa: 'Chatterjee, K., & Doyen, L. (2010). The complexity of partial-observation
parity games (Vol. 6397, pp. 1–14). Presented at the LPAR: Logic for Programming,
Artificial Intelligence, and Reasoning, Yogyakarta, Indonesia: Springer. https://doi.org/10.1007/978-3-642-16242-8_1'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “The Complexity of Partial-Observation
Parity Games,” 6397:1–14. Springer, 2010. https://doi.org/10.1007/978-3-642-16242-8_1.
ieee: 'K. Chatterjee and L. Doyen, “The complexity of partial-observation parity
games,” presented at the LPAR: Logic for Programming, Artificial Intelligence,
and Reasoning, Yogyakarta, Indonesia, 2010, vol. 6397, pp. 1–14.'
ista: 'Chatterjee K, Doyen L. 2010. The complexity of partial-observation parity
games. LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, LNCS,
vol. 6397, 1–14.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. The Complexity of Partial-Observation
Parity Games. Vol. 6397, Springer, 2010, pp. 1–14, doi:10.1007/978-3-642-16242-8_1.
short: K. Chatterjee, L. Doyen, in:, Springer, 2010, pp. 1–14.
conference:
end_date: 2010-10-15
location: Yogyakarta, Indonesia
name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
start_date: 2010-10-10
date_created: 2018-12-11T12:05:33Z
date_published: 2010-12-09T00:00:00Z
date_updated: 2021-01-12T07:52:43Z
day: '09'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-642-16242-8_1
file:
- access_level: open_access
checksum: 770e86e5d78c56fddb4786a8da7ef126
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:29:04Z
date_updated: 2020-07-14T12:46:18Z
file_id: '7872'
file_name: 2010_LPAR_Chatterjee.pdf
file_size: 142836
relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: ' 6397'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 1 - 14
publication_status: published
publisher: Springer
publist_id: '2323'
quality_controlled: '1'
scopus_import: 1
status: public
title: The complexity of partial-observation parity games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6397
year: '2010'
...
---
_id: '3859'
abstract:
- lang: eng
text: This book constitutes the proceedings of the 8th International Conference
on Formal Modeling and Analysis of Timed Systems, FORMATS 2010, held in Klosterneuburg,
Austria in September 2010. The 14 papers presented were carefully reviewed and
selected from 31 submissions. In addition, the volume contains 3 invited talks
and 2 invited tutorials.The aim of FORMATS is to promote the study of fundamental
and practical aspects of timed systems, and to bring together researchers from
different disciplines that share an interest in the modeling and analysis of timed
systems. Typical topics include foundations and semantics, methods and tools,
and applications.
alternative_title:
- LNCS
citation:
ama: Chatterjee K, Henzinger TA, eds. Formal Modeling and Analysis of Timed Systems.
Vol 6246. Springer; 2010. doi:10.1007/978-3-642-15297-9
apa: 'Chatterjee, K., & Henzinger, T. A. (Eds.). (2010). Formal modeling
and analysis of timed systems (Vol. 6246). Presented at the FORMATS: Formal
Modeling and Analysis of Timed Systems, Klosterneuburg, Austria: Springer. https://doi.org/10.1007/978-3-642-15297-9'
chicago: Chatterjee, Krishnendu, and Thomas A Henzinger, eds. Formal Modeling
and Analysis of Timed Systems. Vol. 6246. Springer, 2010. https://doi.org/10.1007/978-3-642-15297-9.
ieee: K. Chatterjee and T. A. Henzinger, Eds., Formal modeling and analysis of
timed systems, vol. 6246. Springer, 2010.
ista: Chatterjee K, Henzinger TA eds. 2010. Formal modeling and analysis of timed
systems, Springer,p.
mla: Chatterjee, Krishnendu, and Thomas A. Henzinger, editors. Formal Modeling
and Analysis of Timed Systems. Vol. 6246, Springer, 2010, doi:10.1007/978-3-642-15297-9.
short: K. Chatterjee, T.A. Henzinger, eds., Formal Modeling and Analysis of Timed
Systems, Springer, 2010.
conference:
end_date: 2010-09-10
location: Klosterneuburg, Austria
name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
start_date: 2010-09-08
date_created: 2018-12-11T12:05:33Z
date_published: 2010-09-20T00:00:00Z
date_updated: 2019-11-14T08:42:42Z
day: '20'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15297-9
editor:
- 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
intvolume: ' 6246'
language:
- iso: eng
month: '09'
oa_version: None
publication_status: published
publisher: Springer
publist_id: '2322'
quality_controlled: '1'
related_material:
link:
- description: eBook available via IST BookList
relation: other
url: https://koha.app.ist.ac.at/cgi-bin/koha/opac-detail.pl?biblionumber=12721
status: public
title: Formal modeling and analysis of timed systems
type: conference_editor
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 6246
year: '2010'
...
---
_id: '3860'
abstract:
- lang: eng
text: 'In mean-payoff games, the objective of the protagonist is to ensure that
the limit average of an infinite sequence of numeric weights is nonnegative. In
energy games, the objective is to ensure that the running sum of weights is always
nonnegative. Generalized mean-payoff and energy games replace individual weights
by tuples, and the limit average (resp. running sum) of each coordinate must be
(resp. remain) nonnegative. These games have applications in the synthesis of
resource-bounded processes with multiple resources. We prove the finite-memory
determinacy of generalized energy games and show the inter- reducibility of generalized
mean-payoff and energy games for finite-memory strategies. We also improve the
computational complexity for solving both classes of games with finite-memory
strategies: while the previously best known upper bound was EXPSPACE, and no lower
bound was known, we give an optimal coNP-complete bound. For memoryless strategies,
we show that the problem of deciding the existence of a winning strategy for the
protagonist is NP-complete.'
alternative_title:
- LIPIcs
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: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. Generalized mean-payoff and
energy games. In: Vol 8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:505-516.
doi:10.4230/LIPIcs.FSTTCS.2010.505'
apa: 'Chatterjee, K., Doyen, L., Henzinger, T. A., & Raskin, J. (2010). Generalized
mean-payoff and energy games (Vol. 8, pp. 505–516). Presented at the FSTTCS: Foundations
of Software Technology and Theoretical Computer Science, Chennai, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.505'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin.
“Generalized Mean-Payoff and Energy Games,” 8:505–16. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2010. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.505.
ieee: 'K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Generalized mean-payoff
and energy games,” presented at the FSTTCS: Foundations of Software Technology
and Theoretical Computer Science, Chennai, India, 2010, vol. 8, pp. 505–516.'
ista: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2010. Generalized mean-payoff
and energy games. FSTTCS: Foundations of Software Technology and Theoretical Computer
Science, LIPIcs, vol. 8, 505–516.'
mla: Chatterjee, Krishnendu, et al. Generalized Mean-Payoff and Energy Games.
Vol. 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 505–16, doi:10.4230/LIPIcs.FSTTCS.2010.505.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, J. Raskin, in:, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2010, pp. 505–516.
conference:
end_date: 2010-12-18
location: Chennai, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2010-12-15
date_created: 2018-12-11T12:05:34Z
date_published: 2010-12-13T00:00:00Z
date_updated: 2021-01-12T07:52:44Z
day: '13'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.FSTTCS.2010.505
file:
- access_level: open_access
checksum: 1caabd6319b979927208117a41192637
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:27Z
date_updated: 2020-07-14T12:46:18Z
file_id: '5147'
file_name: IST-2012-59-v1+1_Generalized_mean-payoff_and_energy_games.pdf
file_size: 178278
relation: main_file
- access_level: open_access
checksum: 3a59759ceeacdb5b578f3803d5e6769b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:28Z
date_updated: 2020-07-14T12:46:18Z
file_id: '5148'
file_name: IST-2016-59-v2+1_2_1_.pdf
file_size: 477976
relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 505 - 516
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2321'
pubrep_id: '59'
quality_controlled: '1'
scopus_import: 1
status: public
title: Generalized mean-payoff and energy games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8
year: '2010'
...
---
_id: '3861'
abstract:
- lang: eng
text: We introduce strategy logic, a logic that treats strategies in two-player
games as explicit first-order objects. The explicit treatment of strategies allows
us to specify properties of nonzero-sum games in a simple and natural way. We
show that the one-alternation fragment of strategy logic is strong enough to express
the existence of Nash equilibria and secure equilibria, and subsumes other logics
that were introduced to reason about games, such as ATL, ATL*, and game logic.
We show that strategy logic is decidable, by constructing tree automata that recognize
sets of strategies. While for the general logic, our decision procedure is nonelementary,
for the simple fragment that is used above we show that the complexity is polynomial
in the size of the game graph and optimal in the size of the formula (ranging
from polynomial to 2EXPTIME depending on the form of the formula).
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: Nir
full_name: Piterman, Nir
last_name: Piterman
citation:
ama: Chatterjee K, Henzinger TA, Piterman N. Strategy logic. Information and
Computation. 2010;208(6):677-693. doi:10.1016/j.ic.2009.07.004
apa: Chatterjee, K., Henzinger, T. A., & Piterman, N. (2010). Strategy logic.
Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2009.07.004
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “Strategy
Logic.” Information and Computation. Elsevier, 2010. https://doi.org/10.1016/j.ic.2009.07.004.
ieee: K. Chatterjee, T. A. Henzinger, and N. Piterman, “Strategy logic,” Information
and Computation, vol. 208, no. 6. Elsevier, pp. 677–693, 2010.
ista: Chatterjee K, Henzinger TA, Piterman N. 2010. Strategy logic. Information
and Computation. 208(6), 677–693.
mla: Chatterjee, Krishnendu, et al. “Strategy Logic.” Information and Computation,
vol. 208, no. 6, Elsevier, 2010, pp. 677–93, doi:10.1016/j.ic.2009.07.004.
short: K. Chatterjee, T.A. Henzinger, N. Piterman, Information and Computation 208
(2010) 677–693.
date_created: 2018-12-11T12:05:34Z
date_published: 2010-06-01T00:00:00Z
date_updated: 2023-02-23T11:46:57Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.ic.2009.07.004
file:
- access_level: open_access
checksum: 13bff93f3c2a014e2908145a4517f177
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:54Z
date_updated: 2020-07-14T12:46:18Z
file_id: '4911'
file_name: IST-2012-56-v1+1_Strategy_logic.pdf
file_size: 189120
relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: ' 208'
issue: '6'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 677 - 693
publication: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '2317'
pubrep_id: '56'
quality_controlled: '1'
related_material:
record:
- id: '3884'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Strategy logic
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 208
year: '2010'
...
---
_id: '3863'
abstract:
- lang: eng
text: 'We consider two-player parity games with imperfect information in which strategies
rely on observations that provide imperfect information about the history of a
play. To solve such games, i.e., to determine the winning regions of players and
corresponding winning strategies, one can use the subset construction to build
an equivalent perfect-information game. Recently, an algorithm that avoids the
inefficient subset construction has been proposed. The algorithm performs a fixed-point
computation in a lattice of antichains, thus maintaining a succinct representation
of state sets. However, this representation does not allow to recover winning
strategies. In this paper, we build on the antichain approach to develop an algorithm
for constructing the winning strategies in parity games of imperfect information.
One major obstacle in adapting the classical procedure is that the complementation
of attractor sets would break the invariant of downward-closedness on which the
antichain representation relies. We overcome this difficulty by decomposing problem
instances recursively into games with a combination of reachability, safety, and
simpler parity conditions. We also report on an experimental implementation of
our algorithm: to our knowledge, this is the first implementation of a procedure
for solving imperfect-information parity games on graphs.'
author:
- first_name: Dietmar
full_name: Berwanger, Dietmar
last_name: Berwanger
- 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: De Wulf, Martin
last_name: De Wulf
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. Strategy construction
for parity games with imperfect information. Information and Computation.
2010;208(10):1206-1220. doi:10.1016/j.ic.2009.09.006
apa: Berwanger, D., Chatterjee, K., De Wulf, M., Doyen, L., & Henzinger, T.
A. (2010). Strategy construction for parity games with imperfect information.
Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2009.09.006
chicago: Berwanger, Dietmar, Krishnendu Chatterjee, Martin De Wulf, Laurent Doyen,
and Thomas A Henzinger. “Strategy Construction for Parity Games with Imperfect
Information.” Information and Computation. Elsevier, 2010. https://doi.org/10.1016/j.ic.2009.09.006.
ieee: D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, and T. A. Henzinger, “Strategy
construction for parity games with imperfect information,” Information and
Computation, vol. 208, no. 10. Elsevier, pp. 1206–1220, 2010.
ista: Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. 2010. Strategy
construction for parity games with imperfect information. Information and Computation.
208(10), 1206–1220.
mla: Berwanger, Dietmar, et al. “Strategy Construction for Parity Games with Imperfect
Information.” Information and Computation, vol. 208, no. 10, Elsevier,
2010, pp. 1206–20, doi:10.1016/j.ic.2009.09.006.
short: D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, T.A. Henzinger, Information
and Computation 208 (2010) 1206–1220.
date_created: 2018-12-11T12:05:35Z
date_published: 2010-10-01T00:00:00Z
date_updated: 2023-02-23T11:46:47Z
day: '01'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.ic.2009.09.006
ec_funded: 1
file:
- access_level: open_access
checksum: 29d146e4f8049dbb7f80bbf7ea3700ed
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:44Z
date_updated: 2020-07-14T12:46:18Z
file_id: '5300'
file_name: IST-2012-58-v1+1_Strategy_construction_for_parity_games_with_imperfect_information.pdf
file_size: 287496
relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: ' 208'
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1206 - 1220
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
publication: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '2319'
pubrep_id: '58'
quality_controlled: '1'
related_material:
record:
- id: '3880'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Strategy construction for parity games with imperfect information
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 208
year: '2010'
...
---
_id: '3864'
abstract:
- lang: eng
text: 'Often one has a preference order among the different systems that satisfy
a given specification. Under a probabilistic assumption about the possible inputs,
such a preference order is naturally expressed by a weighted automaton, which
assigns to each word a value, such that a system is preferred if it generates
a higher expected value. We solve the following optimal-synthesis problem: given
an omega-regular specification, a Markov chain that describes the distribution
of inputs, and a weighted automaton that measures how well a system satisfies
the given specification tinder the given input assumption, synthesize a system
that optimizes the measured value. For safety specifications and measures that
are defined by mean-payoff automata, the optimal-synthesis problem amounts to
finding a strategy in a Markov decision process (MDP) that is optimal for a long-run
average reward objective, which can be done in polynomial time. For general omega-regular
specifications, the solution rests on a new, polynomial-time algorithm for computing
optimal strategies in MDPs with mean-payoff parity objectives. We present some
experimental results showing optimal systems that were automatically generated
in this way.'
acknowledgement: This research was supported by the European Union project COMBEST
and the European Network of Excellence ArtistDesign.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
- first_name: Rohit
full_name: Singh, Rohit
last_name: Singh
citation:
ama: 'Chatterjee K, Henzinger TA, Jobstmann B, Singh R. Measuring and synthesizing
systems in probabilistic environments. In: Vol 6174. Springer; 2010:380-395. doi:10.1007/978-3-642-14295-6_34'
apa: 'Chatterjee, K., Henzinger, T. A., Jobstmann, B., & Singh, R. (2010). Measuring
and synthesizing systems in probabilistic environments (Vol. 6174, pp. 380–395).
Presented at the CAV: Computer Aided Verification, Edinburgh, United Kingdom:
Springer. https://doi.org/10.1007/978-3-642-14295-6_34'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Barbara Jobstmann, and Rohit
Singh. “Measuring and Synthesizing Systems in Probabilistic Environments,” 6174:380–95.
Springer, 2010. https://doi.org/10.1007/978-3-642-14295-6_34.
ieee: 'K. Chatterjee, T. A. Henzinger, B. Jobstmann, and R. Singh, “Measuring and
synthesizing systems in probabilistic environments,” presented at the CAV: Computer
Aided Verification, Edinburgh, United Kingdom, 2010, vol. 6174, pp. 380–395.'
ista: 'Chatterjee K, Henzinger TA, Jobstmann B, Singh R. 2010. Measuring and synthesizing
systems in probabilistic environments. CAV: Computer Aided Verification, LNCS,
vol. 6174, 380–395.'
mla: Chatterjee, Krishnendu, et al. Measuring and Synthesizing Systems in Probabilistic
Environments. Vol. 6174, Springer, 2010, pp. 380–95, doi:10.1007/978-3-642-14295-6_34.
short: K. Chatterjee, T.A. Henzinger, B. Jobstmann, R. Singh, in:, Springer, 2010,
pp. 380–395.
conference:
end_date: 2010-07-19
location: Edinburgh, United Kingdom
name: 'CAV: Computer Aided Verification'
start_date: 201-07-15
date_created: 2018-12-11T12:05:35Z
date_published: 2010-07-09T00:00:00Z
date_updated: 2023-02-23T10:17:28Z
day: '09'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-14295-6_34
intvolume: ' 6174'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1004.0739
month: '07'
oa: 1
oa_version: Preprint
page: 380 - 395
publication_status: published
publisher: Springer
publist_id: '2313'
quality_controlled: '1'
related_material:
record:
- id: '1856'
relation: later_version
status: public
scopus_import: 1
status: public
title: Measuring and synthesizing systems in probabilistic environments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6174
year: '2010'
...
---
_id: '3865'
abstract:
- lang: eng
text: We introduce a technique for debugging multi-threaded C programs and analyzing
the impact of source code changes, and its implementation in the prototype tool
DIRECT. Our approach uses a combination of source code instrumentation and runtime
management. The source code along with a test harness is instrumented to monitor
Operating System (OS) and user defined function calls. DIRECT tracks all concurrency
control primitives and, optionally, data from the program. DIRECT maintains an
abstract global state that combines information from every thread, including the
sequence of function calls and concurrency primitives executed. The runtime manager
can insert delays, provoking thread inter-leavings that may exhibit bugs that
are difficult to reach otherwise. The runtime manager collects an approximation
of the reachable state space and uses this approximation to assess the impact
of change in a new version of the program.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Vishwanath
full_name: Raman, Vishwanath
last_name: Raman
- first_name: César
full_name: Sánchez, César
last_name: Sánchez
citation:
ama: 'Chatterjee K, De Alfaro L, Raman V, Sánchez C. Analyzing the impact of change
in multi-threaded programs. In: Rosenblum D, Taenzer G, eds. Vol 6013. Springer;
2010:293-307. doi:10.1007/978-3-642-12029-9_21'
apa: 'Chatterjee, K., De Alfaro, L., Raman, V., & Sánchez, C. (2010). Analyzing
the impact of change in multi-threaded programs. In D. Rosenblum & G. Taenzer
(Eds.) (Vol. 6013, pp. 293–307). Presented at the FASE: Fundamental Approaches
To Software Engineering, Paphos, Cyprus: Springer. https://doi.org/10.1007/978-3-642-12029-9_21'
chicago: Chatterjee, Krishnendu, Luca De Alfaro, Vishwanath Raman, and César Sánchez.
“Analyzing the Impact of Change in Multi-Threaded Programs.” edited by David Rosenblum
and Gabriele Taenzer, 6013:293–307. Springer, 2010. https://doi.org/10.1007/978-3-642-12029-9_21.
ieee: 'K. Chatterjee, L. De Alfaro, V. Raman, and C. Sánchez, “Analyzing the impact
of change in multi-threaded programs,” presented at the FASE: Fundamental Approaches
To Software Engineering, Paphos, Cyprus, 2010, vol. 6013, pp. 293–307.'
ista: 'Chatterjee K, De Alfaro L, Raman V, Sánchez C. 2010. Analyzing the impact
of change in multi-threaded programs. FASE: Fundamental Approaches To Software
Engineering, LNCS, vol. 6013, 293–307.'
mla: Chatterjee, Krishnendu, et al. Analyzing the Impact of Change in Multi-Threaded
Programs. Edited by David Rosenblum and Gabriele Taenzer, vol. 6013, Springer,
2010, pp. 293–307, doi:10.1007/978-3-642-12029-9_21.
short: K. Chatterjee, L. De Alfaro, V. Raman, C. Sánchez, in:, D. Rosenblum, G.
Taenzer (Eds.), Springer, 2010, pp. 293–307.
conference:
end_date: 2010-03-28
location: Paphos, Cyprus
name: 'FASE: Fundamental Approaches To Software Engineering'
start_date: 2010-03-20
date_created: 2018-12-11T12:05:35Z
date_published: 2010-04-21T00:00:00Z
date_updated: 2021-01-12T07:52:47Z
day: '21'
department:
- _id: KrCh
doi: 10.1007/978-3-642-12029-9_21
editor:
- first_name: David
full_name: Rosenblum, David
last_name: Rosenblum
- first_name: Gabriele
full_name: Taenzer, Gabriele
last_name: Taenzer
intvolume: ' 6013'
language:
- iso: eng
month: '04'
oa_version: None
page: 293 - 307
publication_status: published
publisher: Springer
publist_id: '2315'
quality_controlled: '1'
scopus_import: 1
status: public
title: Analyzing the impact of change in multi-threaded programs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6013
year: '2010'
...
---
_id: '3866'
abstract:
- lang: eng
text: Systems ought to behave reasonably even in circumstances that are not anticipated
in their specifications. We propose a definition of robustness for liveness specifications
which prescribes, for any number of environment assumptions that are violated,
a minimal number of system guarantees that must still be fulfilled. This notion
of robustness can be formulated and realized using a Generalized Reactivity formula.
We present an algorithm for synthesizing robust systems from such formulas. For
the important special case of Generalized Reactivity formulas of rank 1, our algorithm
improves the complexity of [PPS06] for large specifications with a small number
of assumptions and guarantees.
alternative_title:
- LNCS
author:
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Karin
full_name: Greimel, Karin
last_name: Greimel
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
citation:
ama: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. Robustness in
the presence of liveness. In: Touili T, Cook B, Jackson P, eds. Vol 6174. Springer;
2010:410-424. doi:10.1007/978-3-642-14295-6_36'
apa: 'Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., & Jobstmann,
B. (2010). Robustness in the presence of liveness. In T. Touili, B. Cook, &
P. Jackson (Eds.) (Vol. 6174, pp. 410–424). Presented at the CAV: Computer Aided
Verification, Edinburgh, UK: Springer. https://doi.org/10.1007/978-3-642-14295-6_36'
chicago: Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger,
and Barbara Jobstmann. “Robustness in the Presence of Liveness.” edited by Tayssir
Touili, Byron Cook, and Paul Jackson, 6174:410–24. Springer, 2010. https://doi.org/10.1007/978-3-642-14295-6_36.
ieee: 'R. Bloem, K. Chatterjee, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Robustness
in the presence of liveness,” presented at the CAV: Computer Aided Verification,
Edinburgh, UK, 2010, vol. 6174, pp. 410–424.'
ista: 'Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. 2010. Robustness
in the presence of liveness. CAV: Computer Aided Verification, LNCS, vol. 6174,
410–424.'
mla: Bloem, Roderick, et al. Robustness in the Presence of Liveness. Edited
by Tayssir Touili et al., vol. 6174, Springer, 2010, pp. 410–24, doi:10.1007/978-3-642-14295-6_36.
short: R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, B. Jobstmann, in:, T.
Touili, B. Cook, P. Jackson (Eds.), Springer, 2010, pp. 410–424.
conference:
end_date: 2010-07-19
location: Edinburgh, UK
name: 'CAV: Computer Aided Verification'
start_date: 2010-07-15
date_created: 2018-12-11T12:05:36Z
date_published: 2010-07-01T00:00:00Z
date_updated: 2021-01-12T07:52:47Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-14295-6_36
ec_funded: 1
editor:
- first_name: Tayssir
full_name: Touili, Tayssir
last_name: Touili
- first_name: Byron
full_name: Cook, Byron
last_name: Cook
- first_name: Paul
full_name: Jackson, Paul
last_name: Jackson
file:
- access_level: open_access
checksum: 9d204611c8d7855bed8134f8708a0010
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:52Z
date_updated: 2020-07-14T12:46:19Z
file_id: '5243'
file_name: IST-2012-54-v1+1_Robustness_in_the_presence_of_liveness.pdf
file_size: 213083
relation: main_file
file_date_updated: 2020-07-14T12:46:19Z
has_accepted_license: '1'
intvolume: ' 6174'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 410 - 424
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2310'
pubrep_id: '54'
quality_controlled: '1'
scopus_import: 1
status: public
title: Robustness in the presence of liveness
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6174
year: '2010'
...
---
_id: '3867'
abstract:
- lang: eng
text: Weighted automata are nondeterministic automata with numerical weights on
transitions. They can define quantitative languages L that assign to each word
w a real number L(w). In the case of infinite words, the value of a run is naturally
computed as the maximum, limsup, liminf, limit-average, or discounted-sum of the
transition weights. The value of a word w is the supremum of the values of the
runs over w. We study expressiveness and closure questions about these quantitative
languages. We first show that the set of words with value greater than a threshold
can be omega-regular for deterministic limit-average and discounted-sum automata,
while this set is always omega-regular when the threshold is isolated (i.e., some
neighborhood around the threshold contains no word). In the latter case, we prove
that the omega-regular language is robust against small perturbations of the transition
weights. We next consider automata with transition weights 0 or 1 and show that
they are as expressive as general weighted automata in the limit-average case,
but not in the discounted-sum case. Third, for quantitative languages L-1 and
L-2, we consider the operations max(L-1, L-2), min(L-1, L-2), and 1 - L-1, which
generalize the boolean operations on languages, as well as the sum L-1 + L-2.
We establish the closure properties of all classes of quantitative languages with
respect to these four operations.
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: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Chatterjee K, Doyen L, Henzinger TA. Expressiveness and closure properties
for quantitative languages. Logical Methods in Computer Science. 2010;6(3):1-23.
doi:10.2168/LMCS-6(3:10)2010
apa: Chatterjee, K., Doyen, L., & Henzinger, T. A. (2010). Expressiveness and
closure properties for quantitative languages. Logical Methods in Computer
Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-6(3:10)2010
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Expressiveness
and Closure Properties for Quantitative Languages.” Logical Methods in Computer
Science. International Federation of Computational Logic, 2010. https://doi.org/10.2168/LMCS-6(3:10)2010.
ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, “Expressiveness and closure
properties for quantitative languages,” Logical Methods in Computer Science,
vol. 6, no. 3. International Federation of Computational Logic, pp. 1–23, 2010.
ista: Chatterjee K, Doyen L, Henzinger TA. 2010. Expressiveness and closure properties
for quantitative languages. Logical Methods in Computer Science. 6(3), 1–23.
mla: Chatterjee, Krishnendu, et al. “Expressiveness and Closure Properties for Quantitative
Languages.” Logical Methods in Computer Science, vol. 6, no. 3, International
Federation of Computational Logic, 2010, pp. 1–23, doi:10.2168/LMCS-6(3:10)2010.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, Logical Methods in Computer Science
6 (2010) 1–23.
date_created: 2018-12-11T12:05:36Z
date_published: 2010-08-30T00:00:00Z
date_updated: 2023-02-23T12:15:42Z
day: '30'
ddc:
- '000'
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.2168/LMCS-6(3:10)2010
ec_funded: 1
file:
- access_level: open_access
checksum: 0243da726476817f2ea33b48b78be696
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:54Z
date_updated: 2020-07-14T12:46:19Z
file_id: '5312'
file_name: IST-2012-55-v1+1_Expressiveness_Closure_Properties_Quantitative_Languages.pdf
file_size: 216598
relation: main_file
- access_level: open_access
checksum: 5e512b8503a9cb263de26331c4ee9cf2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:55Z
date_updated: 2020-07-14T12:46:19Z
file_id: '5313'
file_name: IST-2016-55-v2+1_1007.4018.pdf
file_size: 302416
relation: main_file
file_date_updated: 2020-07-14T12:46:19Z
has_accepted_license: '1'
intvolume: ' 6'
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '08'
oa: 1
oa_version: Published Version
page: 1 - 23
project:
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '2311'
pubrep_id: '504'
quality_controlled: '1'
related_material:
record:
- id: '4540'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Expressiveness and closure properties for quantitative languages
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2010'
...
---
_id: '3868'
abstract:
- lang: eng
text: Simulation and bisimulation metrics for stochastic systems provide a quantitative
generalization of the classical simulation and bisimulation relations. These metrics
capture the similarity of states with respect to quantitative specifications written
in the quantitative mu-calculus and related probabilistic logics. We first show
that the metrics provide a bound for the difference in long-run average and discounted
average behavior across states, indicating that the metrics can be used both in
system verification, and in performance evaluation. For turn-based games and MDPs,
we provide a polynomial-time algorithm for the computation of the one-step metric
distance between states. The algorithm is based on linear programming; it improves
on the previous known exponential-time algorithm based on a reduction to the theory
of reals. We then present PSPACE algorithms for both the decision problem and
the problem of approximating the metric distance between two states, matching
the best known algorithms for Markov chains. For the bisimulation kernel of the
metric our algorithm works in time O(n(4)) for both turn-based games and MDPs;
improving the previously best known O(n(9).log(n)) time algorithm for MDPs. For
a concurrent game G, we show that computing the exact distance be tween states
is at least as hard as computing the value of concurrent reachability games and
the square-root-sum problem in computational geometry. We show that checking whether
the metric distance is bounded by a rational r, can be done via a reduction to
the theory of real closed fields, involving a formula with three quantifier alternations,
yielding O(vertical bar G vertical bar(O(vertical bar G vertical bar 5))) time
complexity, improving the previously known reduction, which yielded O(vertical
bar G vertical bar(O(vertical bar G vertical bar 7))) time complexity. These algorithms
can be iterated to approximate the metrics using binary search
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Vishwanath
full_name: Raman, Vishwanath
last_name: Raman
citation:
ama: Chatterjee K, De Alfaro L, Majumdar R, Raman V. Algorithms for game metrics.
Logical Methods in Computer Science. 2010;6(3):1-27. doi:10.2168/LMCS-6(3:13)2010
apa: Chatterjee, K., De Alfaro, L., Majumdar, R., & Raman, V. (2010). Algorithms
for game metrics. Logical Methods in Computer Science. International Federation
of Computational Logic. https://doi.org/10.2168/LMCS-6(3:13)2010
chicago: Chatterjee, Krishnendu, Luca De Alfaro, Ritankar Majumdar, and Vishwanath
Raman. “Algorithms for Game Metrics.” Logical Methods in Computer Science.
International Federation of Computational Logic, 2010. https://doi.org/10.2168/LMCS-6(3:13)2010.
ieee: K. Chatterjee, L. De Alfaro, R. Majumdar, and V. Raman, “Algorithms for game
metrics,” Logical Methods in Computer Science, vol. 6, no. 3. International
Federation of Computational Logic, pp. 1–27, 2010.
ista: Chatterjee K, De Alfaro L, Majumdar R, Raman V. 2010. Algorithms for game
metrics. Logical Methods in Computer Science. 6(3), 1–27.
mla: Chatterjee, Krishnendu, et al. “Algorithms for Game Metrics.” Logical Methods
in Computer Science, vol. 6, no. 3, International Federation of Computational
Logic, 2010, pp. 1–27, doi:10.2168/LMCS-6(3:13)2010.
short: K. Chatterjee, L. De Alfaro, R. Majumdar, V. Raman, Logical Methods in Computer
Science 6 (2010) 1–27.
date_created: 2018-12-11T12:05:36Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2023-02-23T11:30:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.2168/LMCS-6(3:13)2010
file:
- access_level: open_access
checksum: a18988135fef3016c93808ecb15b55f5
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:11Z
date_updated: 2020-07-14T12:46:19Z
file_id: '4671'
file_name: IST-2015-370-v1+1_0809.4326.pdf
file_size: 346527
relation: main_file
file_date_updated: 2020-07-14T12:46:19Z
has_accepted_license: '1'
intvolume: ' 6'
issue: '3'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 1 - 27
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '2312'
pubrep_id: '370'
quality_controlled: '1'
related_material:
record:
- id: '3504'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Algorithms for game metrics
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2010'
...
---
_id: '3901'
abstract:
- lang: eng
text: We are interested in 3-dimensional images given as arrays of voxels with intensity
values. Extending these values to acontinuous function, we study the robustness
of homology classes in its level and interlevel sets, that is, the amount of perturbationneeded
to destroy these classes. The structure of the homology classes and their robustness,
over all level and interlevel sets, can bevisualized by a triangular diagram of
dots obtained by computing the extended persistence of the function. We give a
fast hierarchicalalgorithm using the dual complexes of oct-tree approximations
of the function. In addition, we show that for balanced oct-trees, thedual complexes
are geometrically realized in $R^3$ and can thus be used to construct level and
interlevel sets. We apply these tools tostudy 3-dimensional images of plant root
systems.
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: Bendich P, Edelsbrunner H, Kerber M. Computing robustness and persistence for
images. IEEE Transactions of Visualization and Computer Graphics. 2010;16(6):1251-1260.
doi:10.1109/TVCG.2010.139
apa: Bendich, P., Edelsbrunner, H., & Kerber, M. (2010). Computing robustness
and persistence for images. IEEE Transactions of Visualization and Computer
Graphics. IEEE. https://doi.org/10.1109/TVCG.2010.139
chicago: Bendich, Paul, Herbert Edelsbrunner, and Michael Kerber. “Computing Robustness
and Persistence for Images.” IEEE Transactions of Visualization and Computer
Graphics. IEEE, 2010. https://doi.org/10.1109/TVCG.2010.139.
ieee: P. Bendich, H. Edelsbrunner, and M. Kerber, “Computing robustness and persistence
for images,” IEEE Transactions of Visualization and Computer Graphics,
vol. 16, no. 6. IEEE, pp. 1251–1260, 2010.
ista: Bendich P, Edelsbrunner H, Kerber M. 2010. Computing robustness and persistence
for images. IEEE Transactions of Visualization and Computer Graphics. 16(6), 1251–1260.
mla: Bendich, Paul, et al. “Computing Robustness and Persistence for Images.” IEEE
Transactions of Visualization and Computer Graphics, vol. 16, no. 6, IEEE,
2010, pp. 1251–60, doi:10.1109/TVCG.2010.139.
short: P. Bendich, H. Edelsbrunner, M. Kerber, IEEE Transactions of Visualization
and Computer Graphics 16 (2010) 1251–1260.
date_created: 2018-12-11T12:05:47Z
date_published: 2010-10-28T00:00:00Z
date_updated: 2021-01-12T07:53:04Z
day: '28'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/TVCG.2010.139
file:
- access_level: open_access
checksum: f6d813c04f4b46023cec6b9a17f15472
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:10Z
date_updated: 2020-07-14T12:46:21Z
file_id: '5262'
file_name: IST-2016-536-v1+1_2010-J-02-PersistenceforImages.pdf
file_size: 721994
relation: main_file
file_date_updated: 2020-07-14T12:46:21Z
has_accepted_license: '1'
intvolume: ' 16'
issue: '6'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1251 - 1260
publication: IEEE Transactions of Visualization and Computer Graphics
publication_status: published
publisher: IEEE
publist_id: '2253'
pubrep_id: '536'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing robustness and persistence for images
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2010'
...
---
_id: '3962'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Holger
full_name: Pflicke, Holger
id: CAA57A9A-5B61-11E9-B130-E0C1E1F2C83D
last_name: Pflicke
citation:
ama: Pflicke H. Dendritic cell migration across basement membranes in the skin.
2010.
apa: Pflicke, H. (2010). Dendritic cell migration across basement membranes
in the skin. Institute of Science and Technology Austria.
chicago: Pflicke, Holger. “ Dendritic Cell Migration across Basement Membranes
in the Skin.” Institute of Science and Technology Austria, 2010.
ieee: H. Pflicke, “ Dendritic cell migration across basement membranes in the skin,”
Institute of Science and Technology Austria, 2010.
ista: Pflicke H. 2010. Dendritic cell migration across basement membranes in the
skin. Institute of Science and Technology Austria.
mla: Pflicke, Holger. Dendritic Cell Migration across Basement Membranes in
the Skin. Institute of Science and Technology Austria, 2010.
short: H. Pflicke, Dendritic Cell Migration across Basement Membranes in the Skin,
Institute of Science and Technology Austria, 2010.
date_created: 2018-12-11T12:06:08Z
date_published: 2010-07-01T00:00:00Z
date_updated: 2023-09-07T11:28:47Z
day: '01'
degree_awarded: PhD
department:
- _id: CaHe
- _id: GradSch
language:
- iso: eng
month: '07'
oa_version: None
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '2165'
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: "\uFEFF\uFEFFDendritic cell migration across basement membranes in the skin"
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2010'
...
---
_id: '4134'
abstract:
- lang: eng
text: 'All species are restricted in their distribution. Currently, ecological models
can only explain such limits if patches vary in quality, leading to asymmetrical
dispersal, or if genetic variation is too low at the margins for adaptation. However,
population genetic models suggest that the increase in genetic variance resulting
from dispersal should allow adaptation to almost any ecological gradient. Clearly
therefore, these models miss something that prevents evolution in natural populations.
We developed an individual-based simulation to explore stochastic effects in these
models. At high carrying capacities, our simulations largely agree with deterministic
predictions. However, when carrying capacity is low, the population fails to establish
for a wide range of parameter values where adaptation was expected from previous
models. Stochastic or transient effects appear critical around the boundaries
in parameter space between simulation behaviours. Dispersal, gradient steepness,
and population density emerge as key factors determining adaptation on an ecological
gradient. '
acknowledgement: We are very grateful to Nick Barton.
author:
- first_name: Jon
full_name: Bridle, Jon
last_name: Bridle
- first_name: Jitka
full_name: Polechova, Jitka
id: 3BBFB084-F248-11E8-B48F-1D18A9856A87
last_name: Polechova
orcid: 0000-0003-0951-3112
- first_name: Masakado
full_name: Kawata, Masakado
last_name: Kawata
- first_name: Roger
full_name: Butlin, Roger
last_name: Butlin
citation:
ama: Bridle J, Polechova J, Kawata M, Butlin R. Why is adaptation prevented at ecological
margins? New insights from individual-based simulations. Ecology Letters.
2010;13(4):485-494. doi:10.1111/j.1461-0248.2010.01442.x
apa: Bridle, J., Polechova, J., Kawata, M., & Butlin, R. (2010). Why is adaptation
prevented at ecological margins? New insights from individual-based simulations.
Ecology Letters. Wiley-Blackwell. https://doi.org/10.1111/j.1461-0248.2010.01442.x
chicago: Bridle, Jon, Jitka Polechova, Masakado Kawata, and Roger Butlin. “Why Is
Adaptation Prevented at Ecological Margins? New Insights from Individual-Based
Simulations.” Ecology Letters. Wiley-Blackwell, 2010. https://doi.org/10.1111/j.1461-0248.2010.01442.x.
ieee: J. Bridle, J. Polechova, M. Kawata, and R. Butlin, “Why is adaptation prevented
at ecological margins? New insights from individual-based simulations,” Ecology
Letters, vol. 13, no. 4. Wiley-Blackwell, pp. 485–494, 2010.
ista: Bridle J, Polechova J, Kawata M, Butlin R. 2010. Why is adaptation prevented
at ecological margins? New insights from individual-based simulations. Ecology
Letters. 13(4), 485–494.
mla: Bridle, Jon, et al. “Why Is Adaptation Prevented at Ecological Margins? New
Insights from Individual-Based Simulations.” Ecology Letters, vol. 13,
no. 4, Wiley-Blackwell, 2010, pp. 485–94, doi:10.1111/j.1461-0248.2010.01442.x.
short: J. Bridle, J. Polechova, M. Kawata, R. Butlin, Ecology Letters 13 (2010)
485–494.
date_created: 2018-12-11T12:07:08Z
date_published: 2010-03-15T00:00:00Z
date_updated: 2021-01-12T07:54:45Z
day: '15'
department:
- _id: NiBa
doi: 10.1111/j.1461-0248.2010.01442.x
ec_funded: 1
intvolume: ' 13'
issue: '4'
language:
- iso: eng
month: '03'
oa_version: None
page: 485 - 494
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Ecology Letters
publication_status: published
publisher: Wiley-Blackwell
publist_id: '1987'
quality_controlled: '1'
scopus_import: 1
status: public
title: Why is adaptation prevented at ecological margins? New insights from individual-based
simulations
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2010'
...
---
_id: '4157'
abstract:
- lang: eng
text: Integrin- and cadherin-mediated adhesion is central for cell and tissue morphogenesis,
allowing cells and tissues to change shape without loosing integrity. Studies
predominantly in cell culture showed that mechanosensation through adhesion structures
is achieved by force-mediated modulation of their molecular composition. The specific
molecular composition of adhesion sites in turn determines their signalling activity
and dynamic reorganization. Here, we will review how adhesion sites respond to
mecanical stimuli, and how spatially and temporally regulated signalling from
different adhesion sites controls cell migration and tissue morphogenesis.
acknowledged_ssus:
- _id: Bio
author:
- first_name: Ekaterina
full_name: Papusheva, Ekaterina
id: 41DB591E-F248-11E8-B48F-1D18A9856A87
last_name: Papusheva
- 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
citation:
ama: 'Papusheva E, Heisenberg C-PJ. Spatial organization of adhesion: force-dependent
regulation and function in tissue morphogenesis. EMBO Journal. 2010;29(16):2753-2768.
doi:10.1038/emboj.2010.182'
apa: 'Papusheva, E., & Heisenberg, C.-P. J. (2010). Spatial organization of
adhesion: force-dependent regulation and function in tissue morphogenesis. EMBO
Journal. Wiley-Blackwell. https://doi.org/10.1038/emboj.2010.182'
chicago: 'Papusheva, Ekaterina, and Carl-Philipp J Heisenberg. “Spatial Organization
of Adhesion: Force-Dependent Regulation and Function in Tissue Morphogenesis.”
EMBO Journal. Wiley-Blackwell, 2010. https://doi.org/10.1038/emboj.2010.182.'
ieee: 'E. Papusheva and C.-P. J. Heisenberg, “Spatial organization of adhesion:
force-dependent regulation and function in tissue morphogenesis,” EMBO Journal,
vol. 29, no. 16. Wiley-Blackwell, pp. 2753–2768, 2010.'
ista: 'Papusheva E, Heisenberg C-PJ. 2010. Spatial organization of adhesion: force-dependent
regulation and function in tissue morphogenesis. EMBO Journal. 29(16), 2753–2768.'
mla: 'Papusheva, Ekaterina, and Carl-Philipp J. Heisenberg. “Spatial Organization
of Adhesion: Force-Dependent Regulation and Function in Tissue Morphogenesis.”
EMBO Journal, vol. 29, no. 16, Wiley-Blackwell, 2010, pp. 2753–68, doi:10.1038/emboj.2010.182.'
short: E. Papusheva, C.-P.J. Heisenberg, EMBO Journal 29 (2010) 2753–2768.
date_created: 2018-12-11T12:07:17Z
date_published: 2010-08-18T00:00:00Z
date_updated: 2021-01-12T07:54:55Z
day: '18'
department:
- _id: Bio
- _id: CaHe
doi: 10.1038/emboj.2010.182
external_id:
pmid:
- '20717145'
intvolume: ' 29'
issue: '16'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2924654/
month: '08'
oa: 1
oa_version: Submitted Version
page: 2753 - 2768
pmid: 1
publication: EMBO Journal
publication_status: published
publisher: Wiley-Blackwell
publist_id: '1962'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Spatial organization of adhesion: force-dependent regulation and function
in tissue morphogenesis'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2010'
...
---
_id: '4243'
abstract:
- lang: eng
text: We investigate a new model for populations evolving in a spatial continuum.
This model can be thought of as a spatial version of the Lambda-Fleming-Viot process.
It explicitly incorporates both small scale reproduction events and large scale
extinction-recolonisation events. The lineages ancestral to a sample from a population
evolving according to this model can be described in terms of a spatial version
of the Lambda-coalescent. Using a technique of Evans (1997), we prove existence
and uniqueness in law for the model. We then investigate the asymptotic behaviour
of the genealogy of a finite number of individuals sampled uniformly at random
(or more generally `far enough apart') from a two-dimensional torus of sidelength
L as L tends to infinity. Under appropriate conditions (and on a suitable timescale)
we can obtain as limiting genealogical processes a Kingman coalescent, a more
general Lambda-coalescent or a system of coalescing Brownian motions (with a non-local
coalescence mechanism).
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Alison
full_name: Etheridge, Alison
last_name: Etheridge
- first_name: Amandine
full_name: Véber, Amandine
last_name: Véber
citation:
ama: Barton NH, Etheridge A, Véber A. A new model for evolution in a spatial continuum.
Electronic Journal of Probability. 2010;15(7):162-216. doi:10.1214/EJP.v15-741
apa: Barton, N. H., Etheridge, A., & Véber, A. (2010). A new model for evolution
in a spatial continuum. Electronic Journal of Probability. Institute of
Mathematical Statistics. https://doi.org/10.1214/EJP.v15-741
chicago: Barton, Nicholas H, Alison Etheridge, and Amandine Véber. “A New Model
for Evolution in a Spatial Continuum.” Electronic Journal of Probability.
Institute of Mathematical Statistics, 2010. https://doi.org/10.1214/EJP.v15-741.
ieee: N. H. Barton, A. Etheridge, and A. Véber, “A new model for evolution in a
spatial continuum,” Electronic Journal of Probability, vol. 15, no. 7.
Institute of Mathematical Statistics, pp. 162–216, 2010.
ista: Barton NH, Etheridge A, Véber A. 2010. A new model for evolution in a spatial
continuum. Electronic Journal of Probability. 15(7), 162–216.
mla: Barton, Nicholas H., et al. “A New Model for Evolution in a Spatial Continuum.”
Electronic Journal of Probability, vol. 15, no. 7, Institute of Mathematical
Statistics, 2010, pp. 162–216, doi:10.1214/EJP.v15-741.
short: N.H. Barton, A. Etheridge, A. Véber, Electronic Journal of Probability 15
(2010) 162–216.
date_created: 2018-12-11T12:07:48Z
date_published: 2010-02-03T00:00:00Z
date_updated: 2021-01-12T07:55:34Z
day: '03'
ddc:
- '576'
department:
- _id: NiBa
doi: 10.1214/EJP.v15-741
file:
- access_level: open_access
checksum: bab577546dd4e8f882e9a9dd645cd01e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:21Z
date_updated: 2020-07-14T12:46:26Z
file_id: '5140'
file_name: IST-2015-369-v1+1_741-2535-1-PB.pdf
file_size: 450171
relation: main_file
file_date_updated: 2020-07-14T12:46:26Z
has_accepted_license: '1'
intvolume: ' 15'
issue: '7'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 162 - 216
publication: Electronic Journal of Probability
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '1863'
pubrep_id: '369'
quality_controlled: '1'
scopus_import: 1
status: public
title: A new model for evolution in a spatial continuum
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2010'
...