---
_id: '5380'
abstract:
- lang: eng
text: 'We consider 2-player games played on a finite state space for an infinite
number of rounds. The games are concurrent: in each round, the two players (player
1 and player 2) choose their moves independently and simultaneously; the current
state and the two moves determine the successor state. We study concurrent games
with ω-regular winning conditions specified as parity objectives. We consider
the qualitative analysis problems: the computation of the almost-sure and limit-sure
winning set of states, where player 1 can ensure to win with probability 1 and
with probability arbitrarily close to 1, respectively. In general the almost-sure
and limit-sure winning strategies require both infinite-memory as well as infinite-precision
(to describe probabilities). We study the bounded-rationality problem for qualitative
analysis of concurrent parity games, where the strategy set for player 1 is restricted
to bounded-resource strategies. In terms of precision, strategies can be deterministic,
uniform, finite-precision or infinite-precision; and in terms of memory, strategies
can be memoryless, finite-memory or infinite-memory. We present a precise and
complete characterization of the qualitative winning sets for all combinations
of classes of strategies. In particular, we show that uniform memoryless strategies
are as powerful as finite-precision infinite-memory strategies, and infinite-precision
memoryless strategies are as powerful as infinite-precision finite-memory strategies. We
show that the winning sets can be computed in O(n2d+3) time, where n is the size
of the game structure and 2d is the number of priorities (or colors), and our
algorithms are symbolic. The membership problem of whether a state belongs to
a winning set can be decided in NP ∩ coNP. While this complexity is the same as
for the simpler class of turn-based parity games, where in each state only one
of the two players has a choice of moves, our algorithms,that are obtained by
characterization of the winning sets as μ-calculus formulas, are considerably
more involved than those for turn-based games.'
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
citation:
ama: Chatterjee K. Bounded Rationality in Concurrent Parity Games. IST Austria;
2011. doi:10.15479/AT:IST-2011-0008
apa: Chatterjee, K. (2011). Bounded rationality in concurrent parity games.
IST Austria. https://doi.org/10.15479/AT:IST-2011-0008
chicago: Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games.
IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0008.
ieee: K. Chatterjee, Bounded rationality in concurrent parity games. IST
Austria, 2011.
ista: Chatterjee K. 2011. Bounded rationality in concurrent parity games, IST Austria,
53p.
mla: Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games.
IST Austria, 2011, doi:10.15479/AT:IST-2011-0008.
short: K. Chatterjee, Bounded Rationality in Concurrent Parity Games, IST Austria,
2011.
date_created: 2018-12-12T11:39:00Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2023-02-23T11:22:53Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0008
file:
- access_level: open_access
checksum: 0fd38186409be819a911c4990fa79d1f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:22Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5544'
file_name: IST-2011-0008_IST-2011-0008.pdf
file_size: 500399
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '53'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '16'
related_material:
record:
- id: '3338'
relation: later_version
status: public
status: public
title: Bounded rationality in concurrent parity games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5381'
abstract:
- lang: eng
text: "In two-player finite-state stochastic games of partial obser- vation on graphs,
in every state of the graph, the players simultaneously choose an action, and
their joint actions determine a probability distri- bution over the successor
states. The game is played for infinitely many rounds and thus the players construct
an infinite path in the graph. We consider reachability objectives where the first
player tries to ensure a target state to be visited almost-surely (i.e., with
probability 1) or pos- itively (i.e., with positive probability), no matter the
strategy of the second player.\r\n\r\nWe classify such games according to the
information and to the power of randomization available to the players. On the
basis of information, the game can be one-sided with either (a) player 1, or (b)
player 2 having partial observation (and the other player has perfect observation),
or two- sided with (c) both players having partial observation. On the basis of
randomization, (a) the players may not be allowed to use randomization (pure strategies),
or (b) they may choose a probability distribution over actions but the actual
random choice is external and not visible to the player (actions invisible), or
(c) they may use full randomization.\r\n\r\nOur main results for pure strategies
are as follows: (1) For one-sided games with player 2 perfect observation we show
that (in contrast to full randomized strategies) belief-based (subset-construction
based) strate- gies are not sufficient, and present an exponential upper bound
on mem- ory both for almost-sure and positive winning strategies; we show that
the problem of deciding the existence of almost-sure and positive winning strategies
for player 1 is EXPTIME-complete and present symbolic algo- rithms that avoid
the explicit exponential construction. (2) For one-sided games with player 1 perfect
observation we show that non-elementary memory is both necessary and sufficient
for both almost-sure and posi- tive winning strategies. (3) We show that for the
general (two-sided) case finite-memory strategies are sufficient for both positive
and almost-sure winning, and at least non-elementary memory is required. We establish
the equivalence of the almost-sure winning problems for pure strategies and for
randomized strategies with actions invisible. Our equivalence re- sult exhibit
serious flaws in previous results in the literature: we show a non-elementary
memory lower bound for almost-sure winning whereas an exponential upper bound
was previously claimed."
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. Partial-Observation Stochastic Games: How to Win
When Belief Fails. IST Austria; 2011. doi:10.15479/AT:IST-2011-0007'
apa: 'Chatterjee, K., & Doyen, L. (2011). Partial-observation stochastic
games: How to win when belief fails. IST Austria. https://doi.org/10.15479/AT:IST-2011-0007'
chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. Partial-Observation Stochastic
Games: How to Win When Belief Fails. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0007.'
ieee: 'K. Chatterjee and L. Doyen, Partial-observation stochastic games: How
to win when belief fails. IST Austria, 2011.'
ista: 'Chatterjee K, Doyen L. 2011. Partial-observation stochastic games: How to
win when belief fails, IST Austria, 43p.'
mla: 'Chatterjee, Krishnendu, and Laurent Doyen. Partial-Observation Stochastic
Games: How to Win When Belief Fails. IST Austria, 2011, doi:10.15479/AT:IST-2011-0007.'
short: 'K. Chatterjee, L. Doyen, Partial-Observation Stochastic Games: How to Win
When Belief Fails, IST Austria, 2011.'
date_created: 2018-12-12T11:39:00Z
date_published: 2011-07-05T00:00:00Z
date_updated: 2023-02-23T11:05:48Z
day: '05'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0007
file:
- access_level: open_access
checksum: 06bf6dfc97f6006e3fd0e9a3f31bc961
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:27Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5488'
file_name: IST-2011-0007_IST-2011-0007.pdf
file_size: 574055
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '43'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '17'
related_material:
record:
- id: '1903'
relation: later_version
status: public
- id: '2211'
relation: later_version
status: public
- id: '2955'
relation: later_version
status: public
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5382'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on a finite state space for
an infinite num- ber of rounds. The games are concurrent: in each round, the two
players (player 1 and player 2) choose their moves independently and simultaneously;
the current state and the two moves determine a probability distribution over
the successor states. We also consider the important special case of turn-based
stochastic games where players make moves in turns, rather than concurrently.
We study concurrent games with ω-regular winning conditions specified as parity
objectives. The value for player 1 for a parity objective is the maximal probability
with which the player can guarantee the satisfaction of the objective against
all strategies of the opponent. We study the problem of continuity and robustness
of the value function in concurrent and turn-based stochastic parity games with
respect to imprecision in the transition probabilities. We present quantitative
bounds on the difference of the value function (in terms of the imprecision of
the transition probabilities) and show the value continuity for structurally equivalent
concurrent games (two games are structurally equivalent if the support of the
transition func- tion is same and the probabilities differ). We also show robustness
of optimal strategies for structurally equivalent turn-based stochastic parity
games. Finally we show that the value continuity property breaks without the structurally
equivalent assumption (even for Markov chains) and show that our quantitative
bound is asymptotically optimal. Hence our results are tight (the assumption is
both necessary and sufficient) and optimal (our quantitative bound is asymptotically
optimal).'
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
citation:
ama: Chatterjee K. Robustness of Structurally Equivalent Concurrent Parity Games.
IST Austria; 2011. doi:10.15479/AT:IST-2011-0006
apa: Chatterjee, K. (2011). Robustness of structurally equivalent concurrent
parity games. IST Austria. https://doi.org/10.15479/AT:IST-2011-0006
chicago: Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent
Parity Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0006.
ieee: K. Chatterjee, Robustness of structurally equivalent concurrent parity
games. IST Austria, 2011.
ista: Chatterjee K. 2011. Robustness of structurally equivalent concurrent parity
games, IST Austria, 18p.
mla: Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent
Parity Games. IST Austria, 2011, doi:10.15479/AT:IST-2011-0006.
short: K. Chatterjee, Robustness of Structurally Equivalent Concurrent Parity Games,
IST Austria, 2011.
date_created: 2018-12-12T11:39:00Z
date_published: 2011-06-27T00:00:00Z
date_updated: 2023-02-23T11:23:01Z
day: '27'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0006
file:
- access_level: open_access
checksum: 1322b652d6ab07eb5248298a3f91c1cf
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:24Z
date_updated: 2020-07-14T12:46:40Z
file_id: '5546'
file_name: IST-2011-0006_IST-2011-0006.pdf
file_size: 335997
relation: main_file
file_date_updated: 2020-07-14T12:46:40Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '18'
related_material:
record:
- id: '3341'
relation: later_version
status: public
status: public
title: Robustness of structurally equivalent concurrent parity games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5383'
abstract:
- lang: eng
text: We present a new decidable logic called TREX for expressing constraints about
imperative tree data structures. In particular, TREX supports a transitive closure
operator that can express reachability constraints, which often appear in data
structure invariants. We show that our logic is closed under weakest precondition
computation, which enables its use for automated software verification. We further
show that satisfiability of formulas in TREX is decidable in NP. The low complexity
makes it an attractive alternative to more expensive logics such as monadic second-order
logic (MSOL) over trees, which have been traditionally used for reasoning about
tree data structures.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
- first_name: Marco
full_name: Muñiz, Marco
last_name: Muñiz
- first_name: Viktor
full_name: Kuncak, Viktor
last_name: Kuncak
citation:
ama: Wies T, Muñiz M, Kuncak V. On an Efficient Decision Procedure for Imperative
Tree Data Structures. IST Austria; 2011. doi:10.15479/AT:IST-2011-0005
apa: Wies, T., Muñiz, M., & Kuncak, V. (2011). On an efficient decision procedure
for imperative tree data structures. IST Austria. https://doi.org/10.15479/AT:IST-2011-0005
chicago: Wies, Thomas, Marco Muñiz, and Viktor Kuncak. On an Efficient Decision
Procedure for Imperative Tree Data Structures. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0005.
ieee: T. Wies, M. Muñiz, and V. Kuncak, On an efficient decision procedure for
imperative tree data structures. IST Austria, 2011.
ista: Wies T, Muñiz M, Kuncak V. 2011. On an efficient decision procedure for imperative
tree data structures, IST Austria, 25p.
mla: Wies, Thomas, et al. On an Efficient Decision Procedure for Imperative Tree
Data Structures. IST Austria, 2011, doi:10.15479/AT:IST-2011-0005.
short: T. Wies, M. Muñiz, V. Kuncak, On an Efficient Decision Procedure for Imperative
Tree Data Structures, IST Austria, 2011.
date_created: 2018-12-12T11:39:01Z
date_published: 2011-04-26T00:00:00Z
date_updated: 2023-02-23T11:22:16Z
day: '26'
ddc:
- '000'
- '006'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2011-0005
file:
- access_level: open_access
checksum: b20029184c4a819c5f4466a4a3d238b5
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:01Z
date_updated: 2020-07-14T12:46:40Z
file_id: '5462'
file_name: IST-2011-0005_IST-2011-0005.pdf
file_size: 619053
relation: main_file
file_date_updated: 2020-07-14T12:46:40Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '25'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '19'
related_material:
record:
- id: '3323'
relation: later_version
status: public
status: public
title: On an efficient decision procedure for imperative tree data structures
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5384'
abstract:
- lang: eng
text: 'We consider probabilistic automata on infinite words with acceptance defined
by parity conditions. We consider three qualitative decision problems: (i) the
positive decision problem asks whether there is a word that is accepted with positive
probability; (ii) the almost decision problem asks whether there is a word that
is accepted with probability 1; and (iii) the limit decision problem asks whether
for every ε > 0 there is a word that is accepted with probability at least 1 −
ε. We unify and generalize several decidability results for probabilistic automata
over infinite words, and identify a robust (closed under union and intersection)
subclass of probabilistic automata for which all the qualitative decision problems
are decidable for parity conditions. We also show that if the input words are
restricted to lasso shape words, then the positive and almost problems are decidable
for all probabilistic automata with parity conditions.'
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: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: Chatterjee K, Tracol M. Decidable Problems for Probabilistic Automata on
Infinite Words. IST Austria; 2011. doi:10.15479/AT:IST-2011-0004
apa: Chatterjee, K., & Tracol, M. (2011). Decidable problems for probabilistic
automata on infinite words. IST Austria. https://doi.org/10.15479/AT:IST-2011-0004
chicago: Chatterjee, Krishnendu, and Mathieu Tracol. Decidable Problems for Probabilistic
Automata on Infinite Words. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0004.
ieee: K. Chatterjee and M. Tracol, Decidable problems for probabilistic automata
on infinite words. IST Austria, 2011.
ista: Chatterjee K, Tracol M. 2011. Decidable problems for probabilistic automata
on infinite words, IST Austria, 30p.
mla: Chatterjee, Krishnendu, and Mathieu Tracol. Decidable Problems for Probabilistic
Automata on Infinite Words. IST Austria, 2011, doi:10.15479/AT:IST-2011-0004.
short: K. Chatterjee, M. Tracol, Decidable Problems for Probabilistic Automata on
Infinite Words, IST Austria, 2011.
date_created: 2018-12-12T11:39:01Z
date_published: 2011-04-11T00:00:00Z
date_updated: 2023-02-23T11:05:53Z
day: '11'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0004
file:
- access_level: open_access
checksum: f5a0f664fadc335990f5fcf138df19f1
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:23Z
date_updated: 2020-07-14T12:46:40Z
file_id: '5545'
file_name: IST-2011-004_IST-2011-0004.pdf
file_size: 570827
relation: main_file
file_date_updated: 2020-07-14T12:46:40Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '30'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '20'
related_material:
record:
- id: '2957'
relation: later_version
status: public
status: public
title: Decidable problems for probabilistic automata on infinite words
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5385'
abstract:
- lang: eng
text: There is recently a significant effort to add quantitative objectives to formal
verification and synthesis. We introduce and investigate the extension of temporal
logics with quantitative atomic assertions, aiming for a general and flexible
framework for quantitative-oriented specifications. In the heart of quantitative
objectives lies the accumulation of values along a computation. It is either the
accumulated summation, as with the energy objectives, or the accumulated average,
as with the mean-payoff objectives. We investigate the extension of temporal logics
with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is
a numeric variable of the system, c is a constant rational number, and Sum(v)
and Avg(v) denote the accumulated sum and average of the values of v from the
beginning of the computation up to the current point of time. We also allow the
path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring
to the average value along an entire computation. We study the border of decidability
for extensions of various temporal logics. In particular, we show that extending
the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities by
prefix-accumulation assertions and extending LTL with path-accumulation assertions,
result in temporal logics whose model-checking problem is decidable. The extended
logics allow to significantly extend the currently known energy and mean-payoff
objectives. Moreover, the prefix-accumulation assertions may be refined with “controlled-accumulation”,
allowing, for example, to specify constraints on the average waiting time between
a request and a grant. On the negative side, we show that the fragment we point
to is, in a sense, the maximal logic whose extension with prefix-accumulation
assertions permits a decidable model-checking procedure. Extending a temporal
logic that has the EG or EU modalities, and in particular CTL and LTL, makes the
problem undecidable.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: 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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Boker U, Chatterjee K, Henzinger TA, Kupferman O. Temporal Specifications
with Accumulative Values. IST Austria; 2011. doi:10.15479/AT:IST-2011-0003
apa: Boker, U., Chatterjee, K., Henzinger, T. A., & Kupferman, O. (2011). Temporal
specifications with accumulative values. IST Austria. https://doi.org/10.15479/AT:IST-2011-0003
chicago: Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman.
Temporal Specifications with Accumulative Values. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0003.
ieee: U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, Temporal specifications
with accumulative values. IST Austria, 2011.
ista: Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2011. Temporal specifications
with accumulative values, IST Austria, 14p.
mla: Boker, Udi, et al. Temporal Specifications with Accumulative Values.
IST Austria, 2011, doi:10.15479/AT:IST-2011-0003.
short: U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, Temporal Specifications
with Accumulative Values, IST Austria, 2011.
date_created: 2018-12-12T11:39:02Z
date_published: 2011-04-04T00:00:00Z
date_updated: 2023-02-23T11:23:41Z
day: '04'
ddc:
- '000'
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.15479/AT:IST-2011-0003
ec_funded: 1
file:
- access_level: open_access
checksum: 8491d0d48c4911620ecd5350b413c11e
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:00Z
date_updated: 2020-07-14T12:46:41Z
file_id: '5461'
file_name: IST-2011-0003_IST-2011-0003.pdf
file_size: 366281
relation: main_file
file_date_updated: 2020-07-14T12:46:41Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '14'
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '21'
related_material:
record:
- id: '2038'
relation: later_version
status: public
- id: '3356'
relation: later_version
status: public
status: public
title: Temporal specifications with accumulative values
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5386'
abstract:
- lang: eng
text: 'We introduce TopoCut: a new way to integrate knowledge about topological
properties (TPs) into random field image segmentation model. Instead of including
TPs as additional constraints during minimization of the energy function, we devise
an efficient algorithm for modifying the unary potentials such that the resulting
segmentation is guaranteed with the desired properties. Our method is more flexible
in the sense that it handles more topology constraints than previous methods,
which were only able to enforce pairwise or global connectivity. In particular,
our method is very fast, making it for the first time possible to enforce global
topological properties in practical image segmentation tasks.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Daniel
full_name: Freedman, Daniel
last_name: Freedman
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Chen C, Freedman D, Lampert C. Enforcing Topological Constraints in Random
Field Image Segmentation. IST Austria; 2011. doi:10.15479/AT:IST-2011-0002
apa: Chen, C., Freedman, D., & Lampert, C. (2011). Enforcing topological
constraints in random field image segmentation. IST Austria. https://doi.org/10.15479/AT:IST-2011-0002
chicago: Chen, Chao, Daniel Freedman, and Christoph Lampert. Enforcing Topological
Constraints in Random Field Image Segmentation. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0002.
ieee: C. Chen, D. Freedman, and C. Lampert, Enforcing topological constraints
in random field image segmentation. IST Austria, 2011.
ista: Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in
random field image segmentation, IST Austria, 69p.
mla: Chen, Chao, et al. Enforcing Topological Constraints in Random Field Image
Segmentation. IST Austria, 2011, doi:10.15479/AT:IST-2011-0002.
short: C. Chen, D. Freedman, C. Lampert, Enforcing Topological Constraints in Random
Field Image Segmentation, IST Austria, 2011.
date_created: 2018-12-12T11:39:02Z
date_published: 2011-03-28T00:00:00Z
date_updated: 2023-02-23T11:22:48Z
day: '28'
ddc:
- '000'
department:
- _id: ChLa
doi: 10.15479/AT:IST-2011-0002
file:
- access_level: open_access
checksum: ad64c2add5fe2ad10e9d5c669f3f9526
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:34Z
date_updated: 2020-07-14T12:46:41Z
file_id: '5495'
file_name: IST-2011-0002_IST-2011-0002.pdf
file_size: 26390601
relation: main_file
file_date_updated: 2020-07-14T12:46:41Z
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '69'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '22'
related_material:
record:
- id: '3336'
relation: later_version
status: public
status: public
title: Enforcing topological constraints in random field image segmentation
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '5387'
abstract:
- lang: eng
text: We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy
parity objectives. In system design, the parity objective is used to encode ω-regular
specifications, and the mean-payoff and energy objectives can be used to model
quantitative resource constraints. The energy condition re- quires that the resource
level never drops below 0, and the mean-payoff condi- tion requires that the limit-average
value of the resource consumption is within a threshold. While these two (energy
and mean-payoff) classical conditions are equivalent for two-player games, we
show that they differ for MDPs. We show that the problem of deciding whether a
state is almost-sure winning (i.e., winning with probability 1) in energy parity
MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable
in polynomial time, improving a recent PSPACE bound.
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. Energy and Mean-Payoff Parity Markov Decision Processes.
IST Austria; 2011. doi:10.15479/AT:IST-2011-0001
apa: Chatterjee, K., & Doyen, L. (2011). Energy and mean-payoff parity Markov
decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2011-0001
chicago: Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity
Markov Decision Processes. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0001.
ieee: K. Chatterjee and L. Doyen, Energy and mean-payoff parity Markov decision
processes. IST Austria, 2011.
ista: Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov decision
processes, IST Austria, 20p.
mla: Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity
Markov Decision Processes. IST Austria, 2011, doi:10.15479/AT:IST-2011-0001.
short: K. Chatterjee, L. Doyen, Energy and Mean-Payoff Parity Markov Decision Processes,
IST Austria, 2011.
date_created: 2018-12-12T11:39:02Z
date_published: 2011-02-16T00:00:00Z
date_updated: 2023-02-23T11:23:11Z
day: '16'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0001
file:
- access_level: open_access
checksum: 824d6c70e6d3feb3e836b009e0b3cf73
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:52:57Z
date_updated: 2020-07-14T12:46:41Z
file_id: '5458'
file_name: IST-2011-0001_IST-2011-0001.pdf
file_size: 329976
relation: main_file
file_date_updated: 2020-07-14T12:46:41Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '23'
related_material:
record:
- id: '3345'
relation: later_version
status: public
status: public
title: Energy and mean-payoff parity Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '6496'
abstract:
- lang: eng
text: We report the switching behavior of the full bacterial flagellum system that
includes the filament and the motor in wild-type Escherichia coli cells. In sorting
the motor behavior by the clockwise bias, we find that the distributions of the
clockwise (CW) and counterclockwise (CCW) intervals are either exponential or
nonexponential with long tails. At low bias, CW intervals are exponentially distributed
and CCW intervals exhibit long tails. At intermediate CW bias (0.5) both CW and
CCW intervals are mainly exponentially distributed. A simple model suggests that
these two distinct switching behaviors are governed by the presence of signaling
noise within the chemotaxis network. Low noise yields exponentially distributed
intervals, whereas large noise yields nonexponential behavior with long tails.
These drastically different motor statistics may play a role in optimizing bacterial
behavior for a wide range of environmental conditions.
article_processing_charge: No
author:
- first_name: Heungwon
full_name: Park, Heungwon
last_name: Park
- first_name: Panos
full_name: Oikonomou, Panos
last_name: Oikonomou
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Philippe
full_name: Cluzel, Philippe
last_name: Cluzel
citation:
ama: Park H, Oikonomou P, Guet CC, Cluzel P. Noise underlies switching behavior
of the bacterial flagellum. Biophysical Journal. 2011;101(10):2336-2340.
doi:10.1016/j.bpj.2011.09.040
apa: Park, H., Oikonomou, P., Guet, C. C., & Cluzel, P. (2011). Noise underlies
switching behavior of the bacterial flagellum. Biophysical Journal. Elsevier.
https://doi.org/10.1016/j.bpj.2011.09.040
chicago: Park, Heungwon, Panos Oikonomou, Calin C Guet, and Philippe Cluzel. “Noise
Underlies Switching Behavior of the Bacterial Flagellum.” Biophysical Journal.
Elsevier, 2011. https://doi.org/10.1016/j.bpj.2011.09.040.
ieee: H. Park, P. Oikonomou, C. C. Guet, and P. Cluzel, “Noise underlies switching
behavior of the bacterial flagellum,” Biophysical Journal, vol. 101, no.
10. Elsevier, pp. 2336–2340, 2011.
ista: Park H, Oikonomou P, Guet CC, Cluzel P. 2011. Noise underlies switching behavior
of the bacterial flagellum. Biophysical Journal. 101(10), 2336–2340.
mla: Park, Heungwon, et al. “Noise Underlies Switching Behavior of the Bacterial
Flagellum.” Biophysical Journal, vol. 101, no. 10, Elsevier, 2011, pp.
2336–40, doi:10.1016/j.bpj.2011.09.040.
short: H. Park, P. Oikonomou, C.C. Guet, P. Cluzel, Biophysical Journal 101 (2011)
2336–2340.
date_created: 2019-05-28T11:54:29Z
date_published: 2011-11-16T00:00:00Z
date_updated: 2021-04-16T11:54:49Z
day: '16'
department:
- _id: CaGu
doi: 10.1016/j.bpj.2011.09.040
external_id:
pmid:
- '22098731'
intvolume: ' 101'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3218319/
month: '11'
oa: 1
oa_version: Published Version
page: 2336-2340
pmid: 1
publication: Biophysical Journal
publication_identifier:
issn:
- 0006-3495
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Noise underlies switching behavior of the bacterial flagellum
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 101
year: '2011'
...
---
_id: '9483'
abstract:
- lang: eng
text: Imprinted genes are expressed primarily or exclusively from either the maternal
or paternal allele, a phenomenon that occurs in flowering plants and mammals.
Flowering plant imprinted gene expression has been described primarily in endosperm,
a terminal nutritive tissue consumed by the embryo during seed development or
after germination. Imprinted expression in Arabidopsis thaliana endosperm is orchestrated
by differences in cytosine DNA methylation between the paternal and maternal genomes
as well as by Polycomb group proteins. Currently, only 11 imprinted A. thaliana
genes are known. Here, we use extensive sequencing of cDNA libraries to identify
9 paternally expressed and 34 maternally expressed imprinted genes in A. thaliana
endosperm that are regulated by the DNA-demethylating glycosylase DEMETER, the
DNA methyltransferase MET1, and/or the core Polycomb group protein FIE. These
genes encode transcription factors, proteins involved in hormone signaling, components
of the ubiquitin protein degradation pathway, regulators of histone and DNA methylation,
and small RNA pathway proteins. We also identify maternally expressed genes that
may be regulated by unknown mechanisms or deposited from maternal tissues. We
did not detect any imprinted genes in the embryo. Our results show that imprinted
gene expression is an extensive mechanistically complex phenomenon that likely
affects multiple aspects of seed development.
article_processing_charge: No
article_type: original
author:
- first_name: Tzung-Fu
full_name: Hsieh, Tzung-Fu
last_name: Hsieh
- first_name: Juhyun
full_name: Shin, Juhyun
last_name: Shin
- first_name: Rie
full_name: Uzawa, Rie
last_name: Uzawa
- first_name: Pedro
full_name: Silva, Pedro
last_name: Silva
- first_name: Stephanie
full_name: Cohen, Stephanie
last_name: Cohen
- first_name: Matthew J.
full_name: Bauer, Matthew J.
last_name: Bauer
- first_name: Meryl
full_name: Hashimoto, Meryl
last_name: Hashimoto
- first_name: Ryan C.
full_name: Kirkbride, Ryan C.
last_name: Kirkbride
- first_name: John J.
full_name: Harada, John J.
last_name: Harada
- first_name: Daniel
full_name: Zilberman, Daniel
id: 6973db13-dd5f-11ea-814e-b3e5455e9ed1
last_name: Zilberman
orcid: 0000-0002-0123-8649
- first_name: Robert L.
full_name: Fischer, Robert L.
last_name: Fischer
citation:
ama: Hsieh T-F, Shin J, Uzawa R, et al. Regulation of imprinted gene expression
in Arabidopsis endosperm. Proceedings of the National Academy of Sciences.
2011;108(5):1755-1762. doi:10.1073/pnas.1019273108
apa: Hsieh, T.-F., Shin, J., Uzawa, R., Silva, P., Cohen, S., Bauer, M. J., … Fischer,
R. L. (2011). Regulation of imprinted gene expression in Arabidopsis endosperm.
Proceedings of the National Academy of Sciences. National Academy of Sciences.
https://doi.org/10.1073/pnas.1019273108
chicago: Hsieh, Tzung-Fu, Juhyun Shin, Rie Uzawa, Pedro Silva, Stephanie Cohen,
Matthew J. Bauer, Meryl Hashimoto, et al. “Regulation of Imprinted Gene Expression
in Arabidopsis Endosperm.” Proceedings of the National Academy of Sciences.
National Academy of Sciences, 2011. https://doi.org/10.1073/pnas.1019273108.
ieee: T.-F. Hsieh et al., “Regulation of imprinted gene expression in Arabidopsis
endosperm,” Proceedings of the National Academy of Sciences, vol. 108,
no. 5. National Academy of Sciences, pp. 1755–1762, 2011.
ista: Hsieh T-F, Shin J, Uzawa R, Silva P, Cohen S, Bauer MJ, Hashimoto M, Kirkbride
RC, Harada JJ, Zilberman D, Fischer RL. 2011. Regulation of imprinted gene expression
in Arabidopsis endosperm. Proceedings of the National Academy of Sciences. 108(5),
1755–1762.
mla: Hsieh, Tzung-Fu, et al. “Regulation of Imprinted Gene Expression in Arabidopsis
Endosperm.” Proceedings of the National Academy of Sciences, vol. 108,
no. 5, National Academy of Sciences, 2011, pp. 1755–62, doi:10.1073/pnas.1019273108.
short: T.-F. Hsieh, J. Shin, R. Uzawa, P. Silva, S. Cohen, M.J. Bauer, M. Hashimoto,
R.C. Kirkbride, J.J. Harada, D. Zilberman, R.L. Fischer, Proceedings of the National
Academy of Sciences 108 (2011) 1755–1762.
date_created: 2021-06-07T07:40:38Z
date_published: 2011-02-01T00:00:00Z
date_updated: 2021-12-14T08:33:49Z
day: '01'
department:
- _id: DaZi
doi: 10.1073/pnas.1019273108
extern: '1'
external_id:
pmid:
- '21257907'
intvolume: ' 108'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1073/pnas.1019273108
month: '02'
oa: 1
oa_version: Published Version
page: 1755-1762
pmid: 1
publication: Proceedings of the National Academy of Sciences
publication_identifier:
eissn:
- 1091-6490
issn:
- 0027-8424
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Regulation of imprinted gene expression in Arabidopsis endosperm
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 108
year: '2011'
...
---
_id: '9522'
abstract:
- lang: eng
text: Little is known about chromatin remodeling events immediately after fertilization.
A recent report by Autran et al. (2011) in Cell now shows that chromatin regulatory
pathways that silence transposable elements are responsible for global delayed
activation of gene expression in the early Arabidopsis embryo.
article_processing_charge: No
author:
- first_name: Daniel
full_name: Zilberman, Daniel
id: 6973db13-dd5f-11ea-814e-b3e5455e9ed1
last_name: Zilberman
orcid: 0000-0002-0123-8649
citation:
ama: Zilberman D. Balancing Parental Contributions in Plant Embryonic Gene Activation.
Vol 20. Elsevier; 2011:735-736. doi:10.1016/j.devcel.2011.05.018
apa: Zilberman, D. (2011). Balancing parental contributions in plant embryonic
gene activation. Developmental Cell (Vol. 20, pp. 735–736). Elsevier.
https://doi.org/10.1016/j.devcel.2011.05.018
chicago: Zilberman, Daniel. Balancing Parental Contributions in Plant Embryonic
Gene Activation. Developmental Cell. Vol. 20. Elsevier, 2011. https://doi.org/10.1016/j.devcel.2011.05.018.
ieee: D. Zilberman, Balancing parental contributions in plant embryonic gene
activation, vol. 20, no. 6. Elsevier, 2011, pp. 735–736.
ista: Zilberman D. 2011. Balancing parental contributions in plant embryonic gene
activation, Elsevier,p.
mla: Zilberman, Daniel. “Balancing Parental Contributions in Plant Embryonic Gene
Activation.” Developmental Cell, vol. 20, no. 6, Elsevier, 2011, pp. 735–36,
doi:10.1016/j.devcel.2011.05.018.
short: D. Zilberman, Balancing Parental Contributions in Plant Embryonic Gene Activation,
Elsevier, 2011.
date_created: 2021-06-08T06:23:39Z
date_published: 2011-06-14T00:00:00Z
date_updated: 2021-12-14T08:34:37Z
day: '14'
department:
- _id: DaZi
doi: 10.1016/j.devcel.2011.05.018
extern: '1'
external_id:
pmid:
- '21664571'
intvolume: ' 20'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.devcel.2011.05.018
month: '06'
oa: 1
oa_version: Published Version
page: 735-736
pmid: 1
publication: Developmental Cell
publication_identifier:
eissn:
- 1878-1551
issn:
- 1534-5807
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: Balancing parental contributions in plant embryonic gene activation
type: other_academic_publication
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 20
year: '2011'
...
---
_id: '9648'
abstract:
- lang: eng
text: In this paper, we establish a correspondence between the incremental algorithm
for computing AT-models [8,9] and the one for computing persistent homology [6,14,15].
We also present a decremental algorithm for computing AT-models that allows to
extend the persistence computation to a wider setting. Finally, we show how to
combine incremental and decremental techniques for persistent homology computation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Rocio
full_name: Gonzalez-Diaz, Rocio
last_name: Gonzalez-Diaz
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Maria Jose
full_name: Jimenez, Maria Jose
last_name: Jimenez
- first_name: Regina
full_name: Poyatos, Regina
last_name: Poyatos
citation:
ama: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. Incremental-decremental algorithm
for computing AT-models and persistent homology. In: Computer Analysis of Images
and Patterns. Vol 6854. Springer Nature; 2011:286-293. doi:10.1007/978-3-642-23672-3_35'
apa: 'Gonzalez-Diaz, R., Ion, A., Jimenez, M. J., & Poyatos, R. (2011). Incremental-decremental
algorithm for computing AT-models and persistent homology. In Computer Analysis
of Images and Patterns (Vol. 6854, pp. 286–293). Seville, Spain: Springer
Nature. https://doi.org/10.1007/978-3-642-23672-3_35'
chicago: Gonzalez-Diaz, Rocio, Adrian Ion, Maria Jose Jimenez, and Regina Poyatos.
“Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.”
In Computer Analysis of Images and Patterns, 6854:286–93. Springer Nature,
2011. https://doi.org/10.1007/978-3-642-23672-3_35.
ieee: R. Gonzalez-Diaz, A. Ion, M. J. Jimenez, and R. Poyatos, “Incremental-decremental
algorithm for computing AT-models and persistent homology,” in Computer Analysis
of Images and Patterns, Seville, Spain, 2011, vol. 6854, pp. 286–293.
ista: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. 2011. Incremental-decremental
algorithm for computing AT-models and persistent homology. Computer Analysis of
Images and Patterns. CAIP: International Conference on Computer Analysis of Images
and Patterns, LNCS, vol. 6854, 286–293.'
mla: Gonzalez-Diaz, Rocio, et al. “Incremental-Decremental Algorithm for Computing
AT-Models and Persistent Homology.” Computer Analysis of Images and Patterns,
vol. 6854, Springer Nature, 2011, pp. 286–93, doi:10.1007/978-3-642-23672-3_35.
short: R. Gonzalez-Diaz, A. Ion, M.J. Jimenez, R. Poyatos, in:, Computer Analysis
of Images and Patterns, Springer Nature, 2011, pp. 286–293.
conference:
end_date: 2011-08-31
location: Seville, Spain
name: 'CAIP: International Conference on Computer Analysis of Images and Patterns'
start_date: 2011-08-29
date_created: 2021-07-11T22:01:19Z
date_published: 2011-08-01T00:00:00Z
date_updated: 2021-08-12T13:53:17Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-23672-3_35
intvolume: ' 6854'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://hdl.handle.net/11441/30766
month: '08'
oa: 1
oa_version: Published Version
page: 286-293
publication: Computer Analysis of Images and Patterns
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783642236716'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental-decremental algorithm for computing AT-models and persistent homology
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 6854
year: '2011'
...
---
_id: '9762'
abstract:
- lang: eng
text: Defining population structure and genetic diversity levels is of the utmost
importance for developing efficient conservation strategies. Overfishing has caused
mean annual catches of the European spiny lobster (Palinurus elephas) to decrease
alarmingly along its distribution area. In this context, there is a need for comprehensive
studies to evaluate the genetic health of the exploited populations. The present
work is based on a set of 10 nuclear markers amplified in 331 individuals from
10 different localities covering most of P. elephas distribution area. Samples
from Atlantic and Mediterranean basins showed small but significant differences,
indicating that P. elephas populations do not behave as a single panmictic unit
but form two partially-overlapping groups. Despite intense overfishing, our dataset
did not recover a recent bottleneck signal, and showed a large and stable historical
effective size instead. This result could be accounted for by specific life history
traits (reproduction and longevity) and the limitations of molecular markers in
covering very recent timescales for non temporal samples. Our study emphasizes
the necessity of integrating information on effective population sizes and life
history parameters when evaluating population connectivity levels from genetic
data.
article_processing_charge: No
author:
- first_name: Ferran
full_name: Palero, Ferran
id: 3F0E2A22-F248-11E8-B48F-1D18A9856A87
last_name: Palero
orcid: 0000-0002-0343-8329
- first_name: Pere
full_name: Abello, Pere
last_name: Abello
- first_name: Enrique
full_name: Macpherson, Enrique
last_name: Macpherson
- first_name: Mark
full_name: Beaumont, Mark
last_name: Beaumont
- first_name: Marta
full_name: Pascual, Marta
last_name: Pascual
citation:
ama: 'Palero F, Abello P, Macpherson E, Beaumont M, Pascual M. Data from: Effect
of oceanographic barriers and overfishing on the population genetic structure
of the European spiny lobster (Palinurus elephas). 2011. doi:10.5061/dryad.299h8'
apa: 'Palero, F., Abello, P., Macpherson, E., Beaumont, M., & Pascual, M. (2011).
Data from: Effect of oceanographic barriers and overfishing on the population
genetic structure of the European spiny lobster (Palinurus elephas). IST Austria.
https://doi.org/10.5061/dryad.299h8'
chicago: 'Palero, Ferran, Pere Abello, Enrique Macpherson, Mark Beaumont, and Marta
Pascual. “Data from: Effect of Oceanographic Barriers and Overfishing on the Population
Genetic Structure of the European Spiny Lobster (Palinurus Elephas).” IST Austria,
2011. https://doi.org/10.5061/dryad.299h8.'
ieee: 'F. Palero, P. Abello, E. Macpherson, M. Beaumont, and M. Pascual, “Data from:
Effect of oceanographic barriers and overfishing on the population genetic structure
of the European spiny lobster (Palinurus elephas).” IST Austria, 2011.'
ista: 'Palero F, Abello P, Macpherson E, Beaumont M, Pascual M. 2011. Data from:
Effect of oceanographic barriers and overfishing on the population genetic structure
of the European spiny lobster (Palinurus elephas), IST Austria, 10.5061/dryad.299h8.'
mla: 'Palero, Ferran, et al. Data from: Effect of Oceanographic Barriers and
Overfishing on the Population Genetic Structure of the European Spiny Lobster
(Palinurus Elephas). IST Austria, 2011, doi:10.5061/dryad.299h8.'
short: F. Palero, P. Abello, E. Macpherson, M. Beaumont, M. Pascual, (2011).
date_created: 2021-08-02T07:11:19Z
date_published: 2011-05-12T00:00:00Z
date_updated: 2023-02-23T11:25:25Z
day: '12'
department:
- _id: NiBa
doi: 10.5061/dryad.299h8
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.299h8
month: '05'
oa: 1
oa_version: Published Version
publisher: IST Austria
related_material:
record:
- id: '3395'
relation: used_in_publication
status: public
status: public
title: 'Data from: Effect of oceanographic barriers and overfishing on the population
genetic structure of the European spiny lobster (Palinurus elephas)'
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2011'
...
---
_id: '9943'
abstract:
- lang: eng
text: Segmentation is the process of partitioning digital images into meaningful
regions. The analysis of biological high content images often requires segmentation
as a first step. We propose ilastik as an easy-to-use tool which allows the user
without expertise in image processing to perform segmentation and classification
in a unified way. ilastik learns from labels provided by the user through a convenient
mouse interface. Based on these labels, ilastik infers a problem specific segmentation.
A random forest classifier is used in the learning step, in which each pixel's
neighborhood is characterized by a set of generic (nonlinear) features. ilastik
supports up to three spatial plus one spectral dimension and makes use of all
dimensions in the feature calculation. ilastik provides realtime feedback that
enables the user to interactively refine the segmentation result and hence further
fine-tune the classifier. An uncertainty measure guides the user to ambiguous
regions in the images. Real time performance is achieved by multi-threading which
fully exploits the capabilities of modern multi-core machines. Once a classifier
has been trained on a set of representative images, it can be exported and used
to automatically process a very large number of images (e.g. using the CellProfiler
pipeline). ilastik is an open source project and released under the BSD license
at www.ilastik.org.
article_processing_charge: No
author:
- first_name: Christoph M
full_name: Sommer, Christoph M
id: 4DF26D8C-F248-11E8-B48F-1D18A9856A87
last_name: Sommer
orcid: 0000-0003-1216-9105
- first_name: Christoph
full_name: Straehle, Christoph
last_name: Straehle
- first_name: Ullrich
full_name: Köthe, Ullrich
last_name: Köthe
- first_name: Fred A.
full_name: Hamprecht, Fred A.
last_name: Hamprecht
citation:
ama: 'Sommer CM, Straehle C, Köthe U, Hamprecht FA. Ilastik: Interactive learning
and segmentation toolkit. In: 2011 IEEE International Symposium on Biomedical
Imaging: From Nano to Micro. Institute of Electrical and Electronics Engineers;
2011. doi:10.1109/isbi.2011.5872394'
apa: 'Sommer, C. M., Straehle, C., Köthe, U., & Hamprecht, F. A. (2011). Ilastik:
Interactive learning and segmentation toolkit. In 2011 IEEE International Symposium
on Biomedical Imaging: from Nano to Micro. Chicago, Illinois, USA: Institute
of Electrical and Electronics Engineers. https://doi.org/10.1109/isbi.2011.5872394'
chicago: 'Sommer, Christoph M, Christoph Straehle, Ullrich Köthe, and Fred A. Hamprecht.
“Ilastik: Interactive Learning and Segmentation Toolkit.” In 2011 IEEE International
Symposium on Biomedical Imaging: From Nano to Micro. Institute of Electrical
and Electronics Engineers, 2011. https://doi.org/10.1109/isbi.2011.5872394.'
ieee: 'C. M. Sommer, C. Straehle, U. Köthe, and F. A. Hamprecht, “Ilastik: Interactive
learning and segmentation toolkit,” in 2011 IEEE International Symposium on
Biomedical Imaging: from Nano to Micro, Chicago, Illinois, USA, 2011.'
ista: 'Sommer CM, Straehle C, Köthe U, Hamprecht FA. 2011. Ilastik: Interactive
learning and segmentation toolkit. 2011 IEEE International Symposium on Biomedical
Imaging: from Nano to Micro. ISBI: International Symposium on Biomedical Imaging.'
mla: 'Sommer, Christoph M., et al. “Ilastik: Interactive Learning and Segmentation
Toolkit.” 2011 IEEE International Symposium on Biomedical Imaging: From Nano
to Micro, Institute of Electrical and Electronics Engineers, 2011, doi:10.1109/isbi.2011.5872394.'
short: 'C.M. Sommer, C. Straehle, U. Köthe, F.A. Hamprecht, in:, 2011 IEEE International
Symposium on Biomedical Imaging: From Nano to Micro, Institute of Electrical and
Electronics Engineers, 2011.'
conference:
end_date: 2011-04-02
location: Chicago, Illinois, USA
name: 'ISBI: International Symposium on Biomedical Imaging'
start_date: 2011-03-30
date_created: 2021-08-19T11:49:58Z
date_published: 2011-06-09T00:00:00Z
date_updated: 2023-02-23T14:13:38Z
day: '09'
department:
- _id: Bio
doi: 10.1109/isbi.2011.5872394
extern: '1'
keyword:
- image segmentation
- biomedical imaging
- three dimensional displays
- neurons
- retina
- observers
- image color analysis
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.researchgate.net/publication/224241106_Ilastik_Interactive_learning_and_segmentation_toolkit
month: '06'
oa: 1
oa_version: Preprint
publication: '2011 IEEE International Symposium on Biomedical Imaging: from Nano to
Micro'
publication_identifier:
eissn:
- 1945-8452
isbn:
- 978-1-4244-4127-3
issn:
- 1945-7928
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
status: public
title: 'Ilastik: Interactive learning and segmentation toolkit'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2011'
...
---
_id: '3345'
abstract:
- lang: eng
text: We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy
parity objectives. In system design, the parity objective is used to encode ω-regular
specifications, and the mean-payoff and energy objectives can be used to model
quantitative resource constraints. The energy condition re- quires that the resource
level never drops below 0, and the mean-payoff condi- tion requires that the limit-average
value of the resource consumption is within a threshold. While these two (energy
and mean-payoff) classical conditions are equivalent for two-player games, we
show that they differ for MDPs. We show that the problem of deciding whether a
state is almost-sure winning (i.e., winning with probability 1) in energy parity
MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable
in polynomial time, improving a recent PSPACE bound.
alternative_title:
- LNCS
arxiv: 1
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. Energy and mean-payoff parity Markov Decision Processes.
In: Vol 6907. Springer; 2011:206-218. doi:10.1007/978-3-642-22993-0_21'
apa: 'Chatterjee, K., & Doyen, L. (2011). Energy and mean-payoff parity Markov
Decision Processes (Vol. 6907, pp. 206–218). Presented at the MFCS: Mathematical
Foundations of Computer Science, Warsaw, Poland: Springer. https://doi.org/10.1007/978-3-642-22993-0_21'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Energy and Mean-Payoff Parity
Markov Decision Processes,” 6907:206–18. Springer, 2011. https://doi.org/10.1007/978-3-642-22993-0_21.
ieee: 'K. Chatterjee and L. Doyen, “Energy and mean-payoff parity Markov Decision
Processes,” presented at the MFCS: Mathematical Foundations of Computer Science,
Warsaw, Poland, 2011, vol. 6907, pp. 206–218.'
ista: 'Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov Decision
Processes. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907,
206–218.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity
Markov Decision Processes. Vol. 6907, Springer, 2011, pp. 206–18, doi:10.1007/978-3-642-22993-0_21.
short: K. Chatterjee, L. Doyen, in:, Springer, 2011, pp. 206–218.
conference:
end_date: 2011-08-26
location: Warsaw, Poland
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2011-08-22
date_created: 2018-12-11T12:02:48Z
date_published: 2011-09-28T00:00:00Z
date_updated: 2023-02-23T12:23:59Z
day: '28'
department:
- _id: KrCh
doi: 10.1007/978-3-642-22993-0_21
external_id:
arxiv:
- '1104.2909'
intvolume: ' 6907'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.2909
month: '09'
oa: 1
oa_version: Preprint
page: 206 - 218
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3276'
quality_controlled: '1'
related_material:
record:
- id: '5387'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Energy and mean-payoff parity Markov Decision Processes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6907
year: '2011'
...
---
_id: '3346'
abstract:
- lang: eng
text: We study Markov decision processes (MDPs) with multiple limit-average (or
mean-payoff) functions. We consider two different objectives, namely, expectation
and satisfaction objectives. Given an MDP with k reward functions, in the expectation
objective the goal is to maximize the expected limit-average value, and in the
satisfaction objective the goal is to maximize the probability of runs such that
the limit-average value stays above a given vector. We show that under the expectation
objective, in contrast to the single-objective case, both randomization and memory
are necessary for strategies, and that finite-memory randomized strategies are
sufficient. Under the satisfaction objective, in contrast to the single-objective
case, infinite memory is necessary for strategies, and that randomized memoryless
strategies are sufficient for epsilon-approximation, for all epsilon>;0. We
further prove that the decision problems for both expectation and satisfaction
objectives can be solved in polynomial time and the trade-off curve (Pareto curve)
can be epsilon-approximated in time polynomial in the size of the MDP and 1/epsilon,
and exponential in the number of reward functions, for all epsilon>;0. Our
results also reveal flaws in previous work for MDPs with multiple mean-payoff
functions under the expectation objective, correct the flaws and obtain improved
results.
article_number: '5970225'
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: Václav
full_name: Brožek, Václav
last_name: Brožek
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vojtěch
full_name: Forejt, Vojtěch
last_name: Forejt
- first_name: Antonín
full_name: Kučera, Antonín
last_name: Kučera
citation:
ama: 'Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. Two views on multiple
mean payoff objectives in Markov Decision Processes. In: IEEE; 2011. doi:10.1109/LICS.2011.10'
apa: 'Brázdil, T., Brožek, V., Chatterjee, K., Forejt, V., & Kučera, A. (2011).
Two views on multiple mean payoff objectives in Markov Decision Processes. Presented
at the LICS: Logic in Computer Science, Toronto, Canada: IEEE. https://doi.org/10.1109/LICS.2011.10'
chicago: Brázdil, Tomáš, Václav Brožek, Krishnendu Chatterjee, Vojtěch Forejt, and
Antonín Kučera. “Two Views on Multiple Mean Payoff Objectives in Markov Decision
Processes.” IEEE, 2011. https://doi.org/10.1109/LICS.2011.10.
ieee: 'T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, and A. Kučera, “Two views
on multiple mean payoff objectives in Markov Decision Processes,” presented at
the LICS: Logic in Computer Science, Toronto, Canada, 2011.'
ista: 'Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. 2011. Two views on
multiple mean payoff objectives in Markov Decision Processes. LICS: Logic in Computer
Science, 5970225.'
mla: Brázdil, Tomáš, et al. Two Views on Multiple Mean Payoff Objectives in Markov
Decision Processes. 5970225, IEEE, 2011, doi:10.1109/LICS.2011.10.
short: T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, in:, IEEE, 2011.
conference:
end_date: 2011-06-24
location: Toronto, Canada
name: 'LICS: Logic in Computer Science'
start_date: 2011-06-21
date_created: 2018-12-11T12:02:48Z
date_published: 2011-06-21T00:00:00Z
date_updated: 2021-01-12T07:42:49Z
day: '21'
department:
- _id: KrCh
doi: 10.1109/LICS.2011.10
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.3489
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: IEEE
publist_id: '3275'
quality_controlled: '1'
scopus_import: 1
status: public
title: Two views on multiple mean payoff objectives in Markov Decision Processes
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3347'
abstract:
- lang: eng
text: 'The class of omega-regular languages provides a robust specification language
in verification. Every omega-regular condition can be decomposed into a safety
part and a liveness part. The liveness part ensures that something good happens
"eventually". Finitary liveness was proposed by Alur and Henzinger as
a stronger formulation of liveness. It requires that there exists an unknown,
fixed bound b such that something good happens within b transitions. In this work
we consider automata with finitary acceptance conditions defined by finitary Buchi,
parity and Streett languages. We study languages expressible by such automata:
we give their topological complexity and present a regular-expression characterization.
We compare the expressive power of finitary automata and give optimal algorithms
for classical decisions questions. We show that the finitary languages are Sigma
2-complete; we present a complete picture of the expressive power of various classes
of automata with finitary and infinitary acceptance conditions; we show that the
languages defined by finitary parity automata exactly characterize the star-free
fragment of omega B-regular languages; and we show that emptiness is NLOGSPACE-complete
and universality as well as language inclusion are PSPACE-complete for finitary
parity and Streett automata.'
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Nathanaël
full_name: Fijalkow, Nathanaël
id: A1B5DD72-E997-11E9-8398-E808B6C6ADC0
last_name: Fijalkow
citation:
ama: 'Chatterjee K, Fijalkow N. Finitary languages. In: Vol 6638. Springer; 2011:216-226.
doi:10.1007/978-3-642-21254-3_16'
apa: 'Chatterjee, K., & Fijalkow, N. (2011). Finitary languages (Vol. 6638,
pp. 216–226). Presented at the LATA: Language and Automata Theory and Applications,
Tarragona, Spain: Springer. https://doi.org/10.1007/978-3-642-21254-3_16'
chicago: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Finitary Languages,” 6638:216–26.
Springer, 2011. https://doi.org/10.1007/978-3-642-21254-3_16.
ieee: 'K. Chatterjee and N. Fijalkow, “Finitary languages,” presented at the LATA:
Language and Automata Theory and Applications, Tarragona, Spain, 2011, vol. 6638,
pp. 216–226.'
ista: 'Chatterjee K, Fijalkow N. 2011. Finitary languages. LATA: Language and Automata
Theory and Applications, LNCS, vol. 6638, 216–226.'
mla: Chatterjee, Krishnendu, and Nathanaël Fijalkow. Finitary Languages.
Vol. 6638, Springer, 2011, pp. 216–26, doi:10.1007/978-3-642-21254-3_16.
short: K. Chatterjee, N. Fijalkow, in:, Springer, 2011, pp. 216–226.
conference:
end_date: 2011-05-31
location: Tarragona, Spain
name: 'LATA: Language and Automata Theory and Applications'
start_date: 2011-05-26
date_created: 2018-12-11T12:02:48Z
date_published: 2011-06-16T00:00:00Z
date_updated: 2021-01-12T07:42:50Z
day: '16'
department:
- _id: KrCh
doi: 10.1007/978-3-642-21254-3_16
external_id:
arxiv:
- '1101.1727'
intvolume: ' 6638'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1101.1727
month: '06'
oa: 1
oa_version: Preprint
page: 216 - 226
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3274'
quality_controlled: '1'
scopus_import: 1
status: public
title: Finitary languages
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6638
year: '2011'
...
---
_id: '3348'
abstract:
- lang: eng
text: We study synthesis of controllers for real-time systems, where the objective
is to stay in a given safe set. The problem is solved by obtaining winning strategies
in the setting of concurrent two-player timed automaton games with safety objectives.
To prevent a player from winning by blocking time, we restrict each player to
strategies that ensure that the player cannot be responsible for causing a zeno
run. We construct winning strategies for the controller which require access only
to (1) the system clocks (thus, controllers which require their own internal infinitely
precise clocks are not necessary), and (2) a linear (in the number of clocks)
number of memory bits. Precisely, we show that for safety objectives, a memory
of size (3 · |C|+lg(|C|+1)) bits suffices for winning controller strategies, where
C is the set of clocks of the timed automaton game, significantly improving the
previous known exponential bound. We also settle the open question of whether
winning region controller strategies require memory for safety objectives by showing
with an example the necessity of memory for region strategies to win for safety
objectives.
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Prabhu V. Synthesis of memory efficient real time controllers
for safety objectives. In: Springer; 2011:221-230. doi:10.1145/1967701.1967734'
apa: 'Chatterjee, K., & Prabhu, V. (2011). Synthesis of memory efficient real
time controllers for safety objectives (pp. 221–230). Presented at the HSCC: Hybrid
Systems - Computation and Control, Chicago, USA: Springer. https://doi.org/10.1145/1967701.1967734'
chicago: Chatterjee, Krishnendu, and Vinayak Prabhu. “Synthesis of Memory Efficient
Real Time Controllers for Safety Objectives,” 221–30. Springer, 2011. https://doi.org/10.1145/1967701.1967734.
ieee: 'K. Chatterjee and V. Prabhu, “Synthesis of memory efficient real time controllers
for safety objectives,” presented at the HSCC: Hybrid Systems - Computation and
Control, Chicago, USA, 2011, pp. 221–230.'
ista: 'Chatterjee K, Prabhu V. 2011. Synthesis of memory efficient real time controllers
for safety objectives. HSCC: Hybrid Systems - Computation and Control, 221–230.'
mla: Chatterjee, Krishnendu, and Vinayak Prabhu. Synthesis of Memory Efficient
Real Time Controllers for Safety Objectives. Springer, 2011, pp. 221–30, doi:10.1145/1967701.1967734.
short: K. Chatterjee, V. Prabhu, in:, Springer, 2011, pp. 221–230.
conference:
end_date: 2011-04-14
location: Chicago, USA
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2011-04-12
date_created: 2018-12-11T12:02:49Z
date_published: 2011-01-31T00:00:00Z
date_updated: 2021-01-12T07:42:50Z
day: '31'
department:
- _id: KrCh
doi: 10.1145/1967701.1967734
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1101.5842
month: '01'
oa: 1
oa_version: Submitted Version
page: 221 - 230
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3273'
quality_controlled: '1'
scopus_import: 1
status: public
title: Synthesis of memory efficient real time controllers for safety objectives
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3349'
abstract:
- lang: eng
text: 'Games on graphs provide a natural model for reactive non-terminating systems.
In such games, the interaction of two players on an arena results in an infinite
path that describes a run of the system. Different settings are used to model
various open systems in computer science, as for instance turn-based or concurrent
moves, and deterministic or stochastic transitions. In this paper, we are interested
in turn-based games, and specifically in deterministic parity games and stochastic
reachability games (also known as simple stochastic games). We present a simple,
direct and efficient reduction from deterministic parity games to simple stochastic
games: it yields an arena whose size is linear up to a logarithmic factor in size
of the original arena.'
alternative_title:
- EPTCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Nathanaël
full_name: Fijalkow, Nathanaël
last_name: Fijalkow
citation:
ama: 'Chatterjee K, Fijalkow N. A reduction from parity games to simple stochastic
games. In: Vol 54. EPTCS; 2011:74-86. doi:10.4204/EPTCS.54.6'
apa: 'Chatterjee, K., & Fijalkow, N. (2011). A reduction from parity games to
simple stochastic games (Vol. 54, pp. 74–86). Presented at the GandALF: Games,
Automata, Logic, and Formal Verification, Minori, Italy: EPTCS. https://doi.org/10.4204/EPTCS.54.6'
chicago: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “A Reduction from Parity
Games to Simple Stochastic Games,” 54:74–86. EPTCS, 2011. https://doi.org/10.4204/EPTCS.54.6.
ieee: 'K. Chatterjee and N. Fijalkow, “A reduction from parity games to simple stochastic
games,” presented at the GandALF: Games, Automata, Logic, and Formal Verification,
Minori, Italy, 2011, vol. 54, pp. 74–86.'
ista: 'Chatterjee K, Fijalkow N. 2011. A reduction from parity games to simple stochastic
games. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 54,
74–86.'
mla: Chatterjee, Krishnendu, and Nathanaël Fijalkow. A Reduction from Parity
Games to Simple Stochastic Games. Vol. 54, EPTCS, 2011, pp. 74–86, doi:10.4204/EPTCS.54.6.
short: K. Chatterjee, N. Fijalkow, in:, EPTCS, 2011, pp. 74–86.
conference:
end_date: 2011-06-17
location: Minori, Italy
name: 'GandALF: Games, Automata, Logic, and Formal Verification'
start_date: 2011-06-15
date_created: 2018-12-11T12:02:49Z
date_published: 2011-06-04T00:00:00Z
date_updated: 2021-01-12T07:42:51Z
day: '04'
department:
- _id: KrCh
doi: 10.4204/EPTCS.54.6
intvolume: ' 54'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1106.1232
month: '06'
oa: 1
oa_version: Submitted Version
page: 74 - 86
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: EPTCS
publist_id: '3272'
scopus_import: 1
status: public
title: A reduction from parity games to simple stochastic games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 54
year: '2011'
...
---
_id: '3350'
abstract:
- lang: eng
text: A controller for a discrete game with ω-regular objectives requires attention
if, intuitively, it requires measuring the state and switching from the current
control action. Minimum attention controllers are preferable in modern shared
implementations of cyber-physical systems because they produce the least burden
on system resources such as processor time or communication bandwidth. We give
algorithms to compute minimum attention controllers for ω-regular objectives in
imperfect information discrete two-player games. We show a polynomial-time reduction
from minimum attention controller synthesis to synthesis of controllers for mean-payoff
parity objectives in games of incomplete information. This gives an optimal EXPTIME-complete
synthesis algorithm. We show that the minimum attention controller problem is
decidable for infinite state systems with finite bisimulation quotients. In particular,
the problem is decidable for timed and rectangular automata.
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: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: 'Chatterjee K, Majumdar R. Minimum attention controller synthesis for omega
regular objectives. In: Fahrenberg U, Tripakis S, eds. Vol 6919. Springer; 2011:145-159.
doi:10.1007/978-3-642-24310-3_11'
apa: 'Chatterjee, K., & Majumdar, R. (2011). Minimum attention controller synthesis
for omega regular objectives. In U. Fahrenberg & S. Tripakis (Eds.) (Vol.
6919, pp. 145–159). Presented at the FORMATS: Formal Modeling and Analysis of
Timed Systems, Aalborg, Denmark: Springer. https://doi.org/10.1007/978-3-642-24310-3_11'
chicago: Chatterjee, Krishnendu, and Ritankar Majumdar. “Minimum Attention Controller
Synthesis for Omega Regular Objectives.” edited by Uli Fahrenberg and Stavros
Tripakis, 6919:145–59. Springer, 2011. https://doi.org/10.1007/978-3-642-24310-3_11.
ieee: 'K. Chatterjee and R. Majumdar, “Minimum attention controller synthesis for
omega regular objectives,” presented at the FORMATS: Formal Modeling and Analysis
of Timed Systems, Aalborg, Denmark, 2011, vol. 6919, pp. 145–159.'
ista: 'Chatterjee K, Majumdar R. 2011. Minimum attention controller synthesis for
omega regular objectives. FORMATS: Formal Modeling and Analysis of Timed Systems,
LNCS, vol. 6919, 145–159.'
mla: Chatterjee, Krishnendu, and Ritankar Majumdar. Minimum Attention Controller
Synthesis for Omega Regular Objectives. Edited by Uli Fahrenberg and Stavros
Tripakis, vol. 6919, Springer, 2011, pp. 145–59, doi:10.1007/978-3-642-24310-3_11.
short: K. Chatterjee, R. Majumdar, in:, U. Fahrenberg, S. Tripakis (Eds.), Springer,
2011, pp. 145–159.
conference:
end_date: 2011-09-23
location: Aalborg, Denmark
name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
start_date: 2011-09-21
date_created: 2018-12-11T12:02:49Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:51Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-24310-3_11
editor:
- first_name: Uli
full_name: Fahrenberg, Uli
last_name: Fahrenberg
- first_name: Stavros
full_name: Tripakis, Stavros
last_name: Tripakis
intvolume: ' 6919'
language:
- iso: eng
month: '01'
oa_version: None
page: 145 - 159
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3271'
quality_controlled: '1'
scopus_import: 1
status: public
title: Minimum attention controller synthesis for omega regular objectives
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6919
year: '2011'
...