---
_id: '3334'
article_type: letter_note
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Günter
full_name: Ziegler, Günter
last_name: Ziegler
citation:
ama: Edelsbrunner H, Pach J, Ziegler G. Letter from the new editors-in-chief. Discrete
& Computational Geometry. 2011;45(1):1-2. doi:10.1007/s00454-010-9313-9
apa: Edelsbrunner, H., Pach, J., & Ziegler, G. (2011). Letter from the new editors-in-chief.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-010-9313-9
chicago: Edelsbrunner, Herbert, János Pach, and Günter Ziegler. “Letter from the
New Editors-in-Chief.” Discrete & Computational Geometry. Springer,
2011. https://doi.org/10.1007/s00454-010-9313-9.
ieee: H. Edelsbrunner, J. Pach, and G. Ziegler, “Letter from the new editors-in-chief,”
Discrete & Computational Geometry, vol. 45, no. 1. Springer, pp. 1–2,
2011.
ista: Edelsbrunner H, Pach J, Ziegler G. 2011. Letter from the new editors-in-chief.
Discrete & Computational Geometry. 45(1), 1–2.
mla: Edelsbrunner, Herbert, et al. “Letter from the New Editors-in-Chief.” Discrete
& Computational Geometry, vol. 45, no. 1, Springer, 2011, pp. 1–2, doi:10.1007/s00454-010-9313-9.
short: H. Edelsbrunner, J. Pach, G. Ziegler, Discrete & Computational Geometry
45 (2011) 1–2.
date_created: 2018-12-11T12:02:44Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:44Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-010-9313-9
intvolume: ' 45'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 2
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3297'
quality_controlled: '1'
scopus_import: 1
status: public
title: Letter from the new editors-in-chief
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2011'
...
---
_id: '3335'
abstract:
- lang: eng
text: We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent
Betti numbers, which formalize the topological information content of the cosmic
mass distribution. While the Betti numbers do not fully quantify topology, they
extend the information beyond conventional cosmological studies of topology in
terms of genus and Euler characteristic. The richer information content of Betti
numbers goes along the availability of fast algorithms to compute them. For continuous
density fields, we determine the scale-dependence of Betti numbers by invoking
the cosmologically familiar filtration of sublevel or superlevel sets defined
by density thresholds. For the discrete galaxy distribution, however, the analysis
is based on the alpha shapes of the particles. These simplicial complexes constitute
an ordered sequence of nested subsets of the Delaunay tessellation, a filtration
defined by the scale parameter, α. As they are homotopy equivalent to the sublevel
sets of the distance field, they are an excellent tool for assessing the topological
structure of a discrete point distribution. In order to develop an intuitive understanding
for the behavior of Betti numbers as a function of α, and their relation to the
morphological patterns in the Cosmic Web, we first study them within the context
of simple heuristic Voronoi clustering models. These can be tuned to consist of
specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or
sheets. To elucidate the relative prominence of the various Betti numbers in different
stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently,
we address the topology of structures emerging in the standard LCDM scenario and
in cosmological scenarios with alternative dark energy content. The evolution
of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic
Web. We also demonstrate that the scale-dependence of the Betti numbers yields
a promising measure of cosmological parameters, with a potential to help in determining
the nature of dark energy and to probe primordial non-Gaussianities. We also discuss
the expected Betti numbers as a function of the density threshold for superlevel
sets of a Gaussian random field. Finally, we introduce the concept of persistent
homology. It measures scale levels of the mass distribution and allows us to separate
small from large scale features. Within the context of the hierarchical cosmic
structure formation, persistence provides a natural formalism for a multiscale
topology study of the Cosmic Web.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Rien
full_name: Van De Weygaert, Rien
last_name: Van De Weygaert
- first_name: Gert
full_name: Vegter, Gert
last_name: Vegter
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Bernard
full_name: Jones, Bernard
last_name: Jones
- first_name: Pratyush
full_name: Pranav, Pratyush
last_name: Pranav
- first_name: Changbom
full_name: Park, Changbom
last_name: Park
- first_name: Wojciech
full_name: Hellwing, Wojciech
last_name: Hellwing
- first_name: Bob
full_name: Eldering, Bob
last_name: Eldering
- first_name: Nico
full_name: Kruithof, Nico
last_name: Kruithof
- first_name: Patrick
full_name: Bos, Patrick
last_name: Bos
- first_name: Johan
full_name: Hidding, Johan
last_name: Hidding
- first_name: Job
full_name: Feldbrugge, Job
last_name: Feldbrugge
- first_name: Eline
full_name: Ten Have, Eline
last_name: Ten Have
- first_name: Matti
full_name: Van Engelen, Matti
last_name: Van Engelen
- first_name: Manuel
full_name: Caroli, Manuel
last_name: Caroli
- first_name: Monique
full_name: Teillaud, Monique
last_name: Teillaud
citation:
ama: 'Van De Weygaert R, Vegter G, Edelsbrunner H, et al. Alpha, Betti and the Megaparsec
Universe: On the topology of the Cosmic Web. In: Gavrilova M, Tan K, Mostafavi
M, eds. Transactions on Computational Science XIV. Vol 6970. Special Issue
on Voronoi Diagrams and Delaunay Triangulation. Springer; 2011:60-101. doi:10.1007/978-3-642-25249-5_3'
apa: 'Van De Weygaert, R., Vegter, G., Edelsbrunner, H., Jones, B., Pranav, P.,
Park, C., … Teillaud, M. (2011). Alpha, Betti and the Megaparsec Universe: On
the topology of the Cosmic Web. In M. Gavrilova, K. Tan, & M. Mostafavi (Eds.),
Transactions on Computational Science XIV (Vol. 6970, pp. 60–101). Springer.
https://doi.org/10.1007/978-3-642-25249-5_3'
chicago: 'Van De Weygaert, Rien, Gert Vegter, Herbert Edelsbrunner, Bernard Jones,
Pratyush Pranav, Changbom Park, Wojciech Hellwing, et al. “Alpha, Betti and the
Megaparsec Universe: On the Topology of the Cosmic Web.” In Transactions on
Computational Science XIV, edited by Marina Gavrilova, Kenneth Tan, and Mir
Mostafavi, 6970:60–101. Special Issue on Voronoi Diagrams and Delaunay Triangulation.
Springer, 2011. https://doi.org/10.1007/978-3-642-25249-5_3.'
ieee: 'R. Van De Weygaert et al., “Alpha, Betti and the Megaparsec Universe:
On the topology of the Cosmic Web,” in Transactions on Computational Science
XIV, vol. 6970, M. Gavrilova, K. Tan, and M. Mostafavi, Eds. Springer, 2011,
pp. 60–101.'
ista: 'Van De Weygaert R, Vegter G, Edelsbrunner H, Jones B, Pranav P, Park C, Hellwing
W, Eldering B, Kruithof N, Bos P, Hidding J, Feldbrugge J, Ten Have E, Van Engelen
M, Caroli M, Teillaud M. 2011.Alpha, Betti and the Megaparsec Universe: On the
topology of the Cosmic Web. In: Transactions on Computational Science XIV. LNCS,
vol. 6970, 60–101.'
mla: 'Van De Weygaert, Rien, et al. “Alpha, Betti and the Megaparsec Universe: On
the Topology of the Cosmic Web.” Transactions on Computational Science XIV,
edited by Marina Gavrilova et al., vol. 6970, Springer, 2011, pp. 60–101, doi:10.1007/978-3-642-25249-5_3.'
short: R. Van De Weygaert, G. Vegter, H. Edelsbrunner, B. Jones, P. Pranav, C. Park,
W. Hellwing, B. Eldering, N. Kruithof, P. Bos, J. Hidding, J. Feldbrugge, E. Ten
Have, M. Van Engelen, M. Caroli, M. Teillaud, in:, M. Gavrilova, K. Tan, M. Mostafavi
(Eds.), Transactions on Computational Science XIV, Springer, 2011, pp. 60–101.
date_created: 2018-12-11T12:02:44Z
date_published: 2011-11-09T00:00:00Z
date_updated: 2021-01-12T07:42:44Z
day: '09'
department:
- _id: HeEd
doi: 10.1007/978-3-642-25249-5_3
editor:
- first_name: Marina
full_name: Gavrilova, Marina
last_name: Gavrilova
- first_name: Kenneth
full_name: Tan, Kenneth
last_name: Tan
- first_name: Mir
full_name: Mostafavi, Mir
last_name: Mostafavi
external_id:
arxiv:
- '1306.3640'
intvolume: ' 6970'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1306.3640
month: '11'
oa: 1
oa_version: Preprint
page: 60 - 101
publication: Transactions on Computational Science XIV
publication_status: published
publisher: Springer
publist_id: '3295'
quality_controlled: '1'
scopus_import: 1
series_title: Special Issue on Voronoi Diagrams and Delaunay Triangulation
status: public
title: 'Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web'
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6970
year: '2011'
...
---
_id: '3336'
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.'
acknowledgement: The first author is supported by the Austrian Science Fund (FWF)
grant No. P20134-N13. The authors would like to thank Sebastian Nowozin for helpful
discussions.
article_processing_charge: No
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. In: CVPR: Computer Vision and Pattern Recognition.
IEEE; 2011:2089-2096. doi:10.1109/CVPR.2011.5995503'
apa: 'Chen, C., Freedman, D., & Lampert, C. (2011). Enforcing topological constraints
in random field image segmentation. In CVPR: Computer Vision and Pattern Recognition
(pp. 2089–2096). Colorado Springs, CO, United States: IEEE. https://doi.org/10.1109/CVPR.2011.5995503'
chicago: 'Chen, Chao, Daniel Freedman, and Christoph Lampert. “Enforcing Topological
Constraints in Random Field Image Segmentation.” In CVPR: Computer Vision and
Pattern Recognition, 2089–96. IEEE, 2011. https://doi.org/10.1109/CVPR.2011.5995503.'
ieee: 'C. Chen, D. Freedman, and C. Lampert, “Enforcing topological constraints
in random field image segmentation,” in CVPR: Computer Vision and Pattern Recognition,
Colorado Springs, CO, United States, 2011, pp. 2089–2096.'
ista: 'Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in
random field image segmentation. CVPR: Computer Vision and Pattern Recognition.
CVPR: Conference on Computer Vision and Pattern Recognition, 2089–2096.'
mla: 'Chen, Chao, et al. “Enforcing Topological Constraints in Random Field Image
Segmentation.” CVPR: Computer Vision and Pattern Recognition, IEEE, 2011,
pp. 2089–96, doi:10.1109/CVPR.2011.5995503.'
short: 'C. Chen, D. Freedman, C. Lampert, in:, CVPR: Computer Vision and Pattern
Recognition, IEEE, 2011, pp. 2089–2096.'
conference:
end_date: 2011-06-25
location: Colorado Springs, CO, United States
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2011-06-20
date_created: 2018-12-11T12:02:45Z
date_published: 2011-07-22T00:00:00Z
date_updated: 2023-02-23T12:23:56Z
day: '22'
department:
- _id: HeEd
- _id: ChLa
doi: 10.1109/CVPR.2011.5995503
language:
- iso: eng
month: '07'
oa_version: None
page: 2089 - 2096
publication: 'CVPR: Computer Vision and Pattern Recognition'
publication_identifier:
eisbn:
- 978-1-4577-0395-9
isbn:
- 978-1-4577-0394-2
publication_status: published
publisher: IEEE
publist_id: '3294'
quality_controlled: '1'
related_material:
record:
- id: '5386'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Enforcing topological constraints in random field image segmentation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3337'
abstract:
- lang: eng
text: Playing table tennis is a difficult task for robots, especially due to their
limitations of acceleration. A key bottleneck is the amount of time needed to
reach the desired hitting position and velocity of the racket for returning the
incoming ball. Here, it often does not suffice to simply extrapolate the ball's
trajectory after the opponent returns it but more information is needed. Humans
are able to predict the ball's trajectory based on the opponent's moves and, thus,
have a considerable advantage. Hence, we propose to incorporate an anticipation
system into robot table tennis players, which enables the robot to react earlier
while the opponent is performing the striking movement. Based on visual observation
of the opponent's racket movement, the robot can predict the aim of the opponent
and adjust its movement generation accordingly. The policies for deciding how
and when to react are obtained by reinforcement learning. We conduct experiments
with an existing robot player to show that the learned reaction policy can significantly
improve the performance of the overall system.
author:
- first_name: Zhikun
full_name: Wang, Zhikun
last_name: Wang
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Katharina
full_name: Mülling, Katharina
last_name: Mülling
- first_name: Bernhard
full_name: Schölkopf, Bernhard
last_name: Schölkopf
- first_name: Jan
full_name: Peters, Jan
last_name: Peters
citation:
ama: 'Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. Learning anticipation
policies for robot table tennis. In: IEEE; 2011:332-337. doi:10.1109/IROS.2011.6094892'
apa: 'Wang, Z., Lampert, C., Mülling, K., Schölkopf, B., & Peters, J. (2011).
Learning anticipation policies for robot table tennis (pp. 332–337). Presented
at the IROS: RSJ International Conference on Intelligent Robots and Systems, San
Francisco, USA: IEEE. https://doi.org/10.1109/IROS.2011.6094892'
chicago: Wang, Zhikun, Christoph Lampert, Katharina Mülling, Bernhard Schölkopf,
and Jan Peters. “Learning Anticipation Policies for Robot Table Tennis,” 332–37.
IEEE, 2011. https://doi.org/10.1109/IROS.2011.6094892.
ieee: 'Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, and J. Peters, “Learning anticipation
policies for robot table tennis,” presented at the IROS: RSJ International Conference
on Intelligent Robots and Systems, San Francisco, USA, 2011, pp. 332–337.'
ista: 'Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. 2011. Learning anticipation
policies for robot table tennis. IROS: RSJ International Conference on Intelligent
Robots and Systems, 332–337.'
mla: Wang, Zhikun, et al. Learning Anticipation Policies for Robot Table Tennis.
IEEE, 2011, pp. 332–37, doi:10.1109/IROS.2011.6094892.
short: Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, J. Peters, in:, IEEE, 2011,
pp. 332–337.
conference:
end_date: 2011-09-30
location: San Francisco, USA
name: 'IROS: RSJ International Conference on Intelligent Robots and Systems'
start_date: 2011-09-25
date_created: 2018-12-11T12:02:45Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:45Z
day: '01'
department:
- _id: ChLa
doi: 10.1109/IROS.2011.6094892
language:
- iso: eng
month: '01'
oa_version: None
page: 332 - 337
publication_status: published
publisher: IEEE
publist_id: '3293'
quality_controlled: '1'
scopus_import: 1
status: public
title: Learning anticipation policies for robot table tennis
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3338'
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 inde- pendently 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, respec- tively. 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 power- ful 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.'
arxiv: 1
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. arXiv.
2011:1-51.
apa: Chatterjee, K. (2011). Bounded rationality in concurrent parity games. arXiv.
ArXiv.
chicago: Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.”
ArXiv. ArXiv, 2011.
ieee: K. Chatterjee, “Bounded rationality in concurrent parity games,” arXiv.
ArXiv, pp. 1–51, 2011.
ista: Chatterjee K. 2011. Bounded rationality in concurrent parity games. arXiv,
1–51, .
mla: Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.” ArXiv,
ArXiv, 2011, pp. 1–51.
short: K. Chatterjee, ArXiv (2011) 1–51.
date_created: 2018-12-11T12:02:45Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2023-02-23T12:23:40Z
day: '11'
department:
- _id: KrCh
external_id:
arxiv:
- '1107.2146'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2146
month: '07'
oa: 1
oa_version: Preprint
page: 1 - 51
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3287'
related_material:
record:
- id: '5380'
relation: earlier_version
status: public
status: public
title: Bounded rationality in concurrent parity games
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3339'
abstract:
- lang: eng
text: 'Turn-based stochastic games and its important subclass Markov decision processes
(MDPs) provide models for systems with both probabilistic and nondeterministic
behaviors. We consider turn-based stochastic games with two classical quantitative
objectives: discounted-sum and long-run average objectives. The game models and
the quantitative objectives are widely used in probabilistic verification, planning,
optimal inventory control, network protocol and performance analysis. Games and
MDPs that model realistic systems often have very large state spaces, and probabilistic
abstraction techniques are necessary to handle the state-space explosion. The
commonly used full-abstraction techniques do not yield space-savings for systems
that have many states with similar value, but does not necessarily have similar
transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions
(MLA), that clusters states based on value only, disregarding differences in their
transition relation was proposed for qualitative objectives (reachability and
safety objectives). In this paper we extend the MLA technique to solve stochastic
games with discounted-sum and long-run average objectives. We present the MLA
technique based abstraction-refinement algorithm for stochastic games and MDPs
with discounted-sum objectives. For long-run average objectives, our solution
works for all MDPs and a sub-class of stochastic games where every state has the
same value. '
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: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Roy
full_name: Pritam, Roy
last_name: Pritam
citation:
ama: Chatterjee K, De Alfaro L, Pritam R. Magnifying lens abstraction for stochastic
games with discounted and long-run average objectives. arXiv. 2011.
apa: Chatterjee, K., De Alfaro, L., & Pritam, R. (2011). Magnifying lens abstraction
for stochastic games with discounted and long-run average objectives. arXiv.
ArXiv.
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Roy Pritam. “Magnifying Lens
Abstraction for Stochastic Games with Discounted and Long-Run Average Objectives.”
ArXiv. ArXiv, 2011.
ieee: K. Chatterjee, L. De Alfaro, and R. Pritam, “Magnifying lens abstraction for
stochastic games with discounted and long-run average objectives,” arXiv.
ArXiv, 2011.
ista: Chatterjee K, De Alfaro L, Pritam R. 2011. Magnifying lens abstraction for
stochastic games with discounted and long-run average objectives. arXiv, .
mla: Chatterjee, Krishnendu, et al. “Magnifying Lens Abstraction for Stochastic
Games with Discounted and Long-Run Average Objectives.” ArXiv, ArXiv, 2011.
short: K. Chatterjee, L. De Alfaro, R. Pritam, ArXiv (2011).
date_created: 2018-12-11T12:02:46Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2021-01-12T07:42:46Z
day: '11'
department:
- _id: KrCh
external_id:
arxiv:
- '1107.2132'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2132
month: '07'
oa: 1
oa_version: Preprint
page: '17'
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3286'
status: public
title: Magnifying lens abstraction for stochastic games with discounted and long-run
average objectives
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3342'
abstract:
- lang: eng
text: 'We consider Markov decision processes (MDPs) with ω-regular specifications
given as parity objectives. We consider the problem of computing the set of almost-sure
winning states from where the objective can be ensured with probability 1. The
algorithms for the computation of the almost-sure winning set for parity objectives
iteratively use the solutions for the almost-sure winning set for Büchi objectives
(a special case of parity objectives). Our contributions are as follows: First,
we present the first subquadratic symbolic algorithm to compute the almost-sure
winning set for MDPs with Büchi objectives; our algorithm takes O(nm) symbolic
steps as compared to the previous known algorithm that takes O(n 2) symbolic steps,
where n is the number of states and m is the number of edges of the MDP. In practice
MDPs often have constant out-degree, and then our symbolic algorithm takes O(nn) symbolic
steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second,
we present a new algorithm, namely win-lose algorithm, with the following two
properties: (a) the algorithm iteratively computes subsets of the almost-sure
winning set and its complement, as compared to all previous algorithms that discover
the almost-sure winning set upon termination; and (b) requires O(nK) symbolic
steps, where K is the maximal number of edges of strongly connected components
(scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s.
Third, we improve the algorithm for symbolic scc computation; the previous known
algorithm takes linear symbolic steps, and our new algorithm improves the constants
associated with the linear number of steps. In the worst case the previous known
algorithm takes 5·n symbolic steps, whereas our new algorithm takes 4 ·n symbolic
steps.'
alternative_title:
- LNCS
article_processing_charge: No
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Manas
full_name: Joglekar, Manas
last_name: Joglekar
- first_name: Shah
full_name: Nisarg, Shah
last_name: Nisarg
citation:
ama: 'Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. Symbolic algorithms for
qualitative analysis of Markov decision processes with Büchi objectives. In: Gopalakrishnan
G, Qadeer S, eds. Vol 6806. Springer; 2011:260-276. doi:10.1007/978-3-642-22110-1_21'
apa: 'Chatterjee, K., Henzinger, M. H., Joglekar, M., & Nisarg, S. (2011). Symbolic
algorithms for qualitative analysis of Markov decision processes with Büchi objectives.
In G. Gopalakrishnan & S. Qadeer (Eds.) (Vol. 6806, pp. 260–276). Presented
at the CAV: Computer Aided Verification, Snowbird, USA: Springer. https://doi.org/10.1007/978-3-642-22110-1_21'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Shah Nisarg.
“Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with
Büchi Objectives.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:260–76.
Springer, 2011. https://doi.org/10.1007/978-3-642-22110-1_21.
ieee: 'K. Chatterjee, M. H. Henzinger, M. Joglekar, and S. Nisarg, “Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives,”
presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806,
pp. 260–276.'
ista: 'Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. 2011. Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives. CAV:
Computer Aided Verification, LNCS, vol. 6806, 260–276.'
mla: Chatterjee, Krishnendu, et al. Symbolic Algorithms for Qualitative Analysis
of Markov Decision Processes with Büchi Objectives. Edited by Ganesh Gopalakrishnan
and Shaz Qadeer, vol. 6806, Springer, 2011, pp. 260–76, doi:10.1007/978-3-642-22110-1_21.
short: K. Chatterjee, M.H. Henzinger, M. Joglekar, S. Nisarg, in:, G. Gopalakrishnan,
S. Qadeer (Eds.), Springer, 2011, pp. 260–276.
conference:
end_date: 2011-07-20
location: Snowbird, USA
name: 'CAV: Computer Aided Verification'
start_date: 2011-07-14
date_created: 2018-12-11T12:02:47Z
date_published: 2011-08-11T00:00:00Z
date_updated: 2023-02-23T11:00:13Z
day: '11'
department:
- _id: KrCh
doi: 10.1007/978-3-642-22110-1_21
editor:
- first_name: Ganesh
full_name: Gopalakrishnan, Ganesh
last_name: Gopalakrishnan
- first_name: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
external_id:
arxiv:
- '1104.3348'
intvolume: ' 6806'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.3348
month: '08'
oa: 1
oa_version: Preprint
page: 260 - 276
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: '3282'
quality_controlled: '1'
related_material:
record:
- id: '2831'
relation: later_version
status: public
status: public
title: Symbolic algorithms for qualitative analysis of Markov decision processes with
Büchi objectives
type: conference
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 6806
year: '2011'
...
---
_id: '3343'
abstract:
- lang: eng
text: 'We present faster and dynamic algorithms for the following problems arising
in probabilistic verification: Computation of the maximal end-component (mec)
decomposition of Markov decision processes (MDPs), and of the almost sure winning
set for reachability and parity objectives in MDPs. We achieve the following running
time for static algorithms in MDPs with graphs of n vertices and m edges: (1)
O(m · min{ √m, n2/3 }) for the mec decomposition, improving the longstanding O(m·n)
bound; (2) O(m·n2/3) for reachability objectives, improving the previous O(m ·
√m) bound for m > n4/3; and (3) O(m · min{ √m, n2/3 } · log(d)) for parity
objectives with d priorities, improving the previous O(m · √m · d) bound. We also
give incremental and decremental algorithms in linear time for mec decomposition
and reachability objectives and O(m · log d) time for parity ob jectives.'
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Chatterjee K, Henzinger MH. Faster and dynamic algorithms for maximal end-component
decomposition and related graph problems in probabilistic verification. In: SIAM;
2011:1318-1336. doi:10.1137/1.9781611973082.101'
apa: 'Chatterjee, K., & Henzinger, M. H. (2011). Faster and dynamic algorithms
for maximal end-component decomposition and related graph problems in probabilistic
verification (pp. 1318–1336). Presented at the SODA: Symposium on Discrete Algorithms,
San Francisco, SA, United States: SIAM. https://doi.org/10.1137/1.9781611973082.101'
chicago: Chatterjee, Krishnendu, and Monika H Henzinger. “Faster and Dynamic Algorithms
for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic
Verification,” 1318–36. SIAM, 2011. https://doi.org/10.1137/1.9781611973082.101.
ieee: 'K. Chatterjee and M. H. Henzinger, “Faster and dynamic algorithms for maximal
end-component decomposition and related graph problems in probabilistic verification,”
presented at the SODA: Symposium on Discrete Algorithms, San Francisco, SA, United
States, 2011, pp. 1318–1336.'
ista: 'Chatterjee K, Henzinger MH. 2011. Faster and dynamic algorithms for maximal
end-component decomposition and related graph problems in probabilistic verification.
SODA: Symposium on Discrete Algorithms, 1318–1336.'
mla: Chatterjee, Krishnendu, and Monika H. Henzinger. Faster and Dynamic Algorithms
for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic
Verification. SIAM, 2011, pp. 1318–36, doi:10.1137/1.9781611973082.101.
short: K. Chatterjee, M.H. Henzinger, in:, SIAM, 2011, pp. 1318–1336.
conference:
end_date: 2011-01-25
location: San Francisco, SA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2011-01-23
date_created: 2018-12-11T12:02:47Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2023-02-14T10:36:10Z
day: '01'
department:
- _id: KrCh
doi: 10.1137/1.9781611973082.101
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprints.cs.univie.ac.at/21/
month: '01'
oa: 1
oa_version: Submitted Version
page: 1318 - 1336
publication_status: published
publisher: SIAM
publist_id: '3278'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster and dynamic algorithms for maximal end-component decomposition and related
graph problems in probabilistic verification
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3344'
abstract:
- lang: eng
text: 'Games played on graphs provide the mathematical framework to analyze several
important problems in computer science as well as mathematics, such as the synthesis
problem of Church, model checking of open reactive systems and many others. On
the basis of mode of interaction of the players these games can be classified
as follows: (a) turn-based (players make moves in turns); and (b) concurrent (players
make moves simultaneously). On the basis of the information available to the players
these games can be classified as follows: (a) perfect-information (players have
perfect view of the game); and (b) partial-information (players have partial view
of the game). In this talk we will consider all these classes of games with reachability
objectives, where the goal of one player is to reach a set of target vertices
of the graph, and the goal of the opponent player is to prevent the player from
reaching the target. We will survey the results for various classes of games,
and the results range from linear time decision algorithms to EXPTIME-complete
problems to undecidable problems.'
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
citation:
ama: 'Chatterjee K. Graph games with reachability objectives. In: Delzanno G, Potapov
I, eds. Vol 6945. Springer; 2011:1-1. doi:10.1007/978-3-642-24288-5_1'
apa: 'Chatterjee, K. (2011). Graph games with reachability objectives. In G. Delzanno
& I. Potapov (Eds.) (Vol. 6945, pp. 1–1). Presented at the RP: Reachability
Problems, Genoa, Italy: Springer. https://doi.org/10.1007/978-3-642-24288-5_1'
chicago: Chatterjee, Krishnendu. “Graph Games with Reachability Objectives.” edited
by Giorgo Delzanno and Igor Potapov, 6945:1–1. Springer, 2011. https://doi.org/10.1007/978-3-642-24288-5_1.
ieee: 'K. Chatterjee, “Graph games with reachability objectives,” presented at the
RP: Reachability Problems, Genoa, Italy, 2011, vol. 6945, pp. 1–1.'
ista: 'Chatterjee K. 2011. Graph games with reachability objectives. RP: Reachability
Problems, LNCS, vol. 6945, 1–1.'
mla: Chatterjee, Krishnendu. Graph Games with Reachability Objectives. Edited
by Giorgo Delzanno and Igor Potapov, vol. 6945, Springer, 2011, pp. 1–1, doi:10.1007/978-3-642-24288-5_1.
short: K. Chatterjee, in:, G. Delzanno, I. Potapov (Eds.), Springer, 2011, pp. 1–1.
conference:
end_date: 2011-09-30
location: Genoa, Italy
name: 'RP: Reachability Problems'
start_date: 2011-09-28
date_created: 2018-12-11T12:02:47Z
date_published: 2011-10-15T00:00:00Z
date_updated: 2021-01-12T07:42:48Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-24288-5_1
editor:
- first_name: Giorgo
full_name: Delzanno, Giorgo
last_name: Delzanno
- first_name: Igor
full_name: Potapov, Igor
last_name: Potapov
intvolume: ' 6945'
language:
- iso: eng
month: '10'
oa_version: None
page: 1 - 1
publication_status: published
publisher: Springer
publist_id: '3277'
quality_controlled: '1'
status: public
title: Graph games with reachability objectives
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6945
year: '2011'
...
---
_id: '10907'
abstract:
- lang: eng
text: This paper presents a method to create a model of an articulated object using
the planar motion in an initialization video. The model consists of rigid parts
connected by points of articulation. The rigid parts are described by the positions
of salient feature-points tracked throughout the video. Following a filtering
step that identifies points that belong to different objects, rigid parts are
found by a grouping process in a graph pyramid. Valid articulation points are
selected by verifying multiple hypotheses for each pair of parts.
acknowledgement: This work has been partially supported by the Austrian Science Fund
under grants S9103-N13 and P18716-N13.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicole M.
full_name: Artner, Nicole M.
last_name: Artner
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Walter G.
full_name: Kropatsch, Walter G.
last_name: Kropatsch
citation:
ama: 'Artner NM, Ion A, Kropatsch WG. Spatio-temporal extraction of articulated
models in a graph pyramid. In: Jiang X, Ferrer M, Torsello A, eds. Graph-Based
Representations in Pattern Recognition. Vol 6658. LNIP. Berlin, Heidelberg:
Springer; 2011:215-224. doi:10.1007/978-3-642-20844-7_22'
apa: 'Artner, N. M., Ion, A., & Kropatsch, W. G. (2011). Spatio-temporal extraction
of articulated models in a graph pyramid. In X. Jiang, M. Ferrer, & A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition (Vol. 6658,
pp. 215–224). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20844-7_22'
chicago: 'Artner, Nicole M., Adrian Ion, and Walter G. Kropatsch. “Spatio-Temporal
Extraction of Articulated Models in a Graph Pyramid.” In Graph-Based Representations
in Pattern Recognition, edited by Xiaoyi Jiang, Miquel Ferrer, and Andrea
Torsello, 6658:215–24. LNIP. Berlin, Heidelberg: Springer, 2011. https://doi.org/10.1007/978-3-642-20844-7_22.'
ieee: N. M. Artner, A. Ion, and W. G. Kropatsch, “Spatio-temporal extraction of
articulated models in a graph pyramid,” in Graph-Based Representations in Pattern
Recognition, Münster, Germany, 2011, vol. 6658, pp. 215–224.
ista: 'Artner NM, Ion A, Kropatsch WG. 2011. Spatio-temporal extraction of articulated
models in a graph pyramid. Graph-Based Representations in Pattern Recognition.
GbRPR: Graph-based Representations in Pattern RecognitionLNIP, LNCS, vol. 6658,
215–224.'
mla: Artner, Nicole M., et al. “Spatio-Temporal Extraction of Articulated Models
in a Graph Pyramid.” Graph-Based Representations in Pattern Recognition,
edited by Xiaoyi Jiang et al., vol. 6658, Springer, 2011, pp. 215–24, doi:10.1007/978-3-642-20844-7_22.
short: N.M. Artner, A. Ion, W.G. Kropatsch, in:, X. Jiang, M. Ferrer, A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition, Springer, Berlin,
Heidelberg, 2011, pp. 215–224.
conference:
end_date: 2011-05-20
location: Münster, Germany
name: 'GbRPR: Graph-based Representations in Pattern Recognition'
start_date: 2011-05-18
date_created: 2022-03-21T08:08:35Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2023-09-05T14:10:15Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-20844-7_22
editor:
- first_name: Xiaoyi
full_name: Jiang, Xiaoyi
last_name: Jiang
- first_name: Miquel
full_name: Ferrer, Miquel
last_name: Ferrer
- first_name: Andrea
full_name: Torsello, Andrea
last_name: Torsello
intvolume: ' 6658'
language:
- iso: eng
month: '06'
oa_version: None
page: 215-224
place: Berlin, Heidelberg
publication: Graph-Based Representations in Pattern Recognition
publication_identifier:
eisbn:
- '9783642208447'
eissn:
- 1611-3349
isbn:
- '9783642208430'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNIP
status: public
title: Spatio-temporal extraction of articulated models in a graph pyramid
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 6658
year: '2011'
...
---
_id: '469'
abstract:
- lang: eng
text: 'Spontaneous release of glutamate is important for maintaining synaptic strength
and controlling spike timing in the brain. Mechanisms regulating spontaneous exocytosis
remain poorly understood. Extracellular calcium concentration ([Ca2+]o) regulates
Ca2+ entry through voltage-activated calcium channels (VACCs) and consequently
is a pivotal determinant of action potential-evoked vesicle fusion. Extracellular
Ca 2+ also enhances spontaneous release, but via unknown mechanisms. Here we report
that external Ca2+ triggers spontaneous glutamate release more weakly than evoked
release in mouse neocortical neurons. Blockade of VACCs has no effect on the spontaneous
release rate or its dependence on [Ca2+]o. Intracellular [Ca2+] slowly increases
in a minority of neurons following increases in [Ca2+]o. Furthermore, the enhancement
of spontaneous release by extracellular calcium is insensitive to chelation of
intracellular calcium by BAPTA. Activation of the calcium-sensing receptor (CaSR),
a G-protein-coupled receptor present in nerve terminals, by several specific agonists
increased spontaneous glutamate release. The frequency of spontaneous synaptic
transmission was decreased in CaSR mutant neurons. The concentration-effect relationship
for extracellular calcium regulation of spontaneous release was well described
by a combination of CaSR-dependent and CaSR-independent mechanisms. Overall these
results indicate that extracellular Ca2+ does not trigger spontaneous glutamate
release by simply increasing calcium influx but stimulates CaSR and thereby promotes
resting spontaneous glutamate release. '
author:
- first_name: Nicholas
full_name: Vyleta, Nicholas
id: 36C4978E-F248-11E8-B48F-1D18A9856A87
last_name: Vyleta
- first_name: Stephen
full_name: Smith, Stephen
last_name: Smith
citation:
ama: Vyleta N, Smith S. Spontaneous glutamate release is independent of calcium
influx and tonically activated by the calcium-sensing receptor. European Journal
of Neuroscience. 2011;31(12):4593-4606. doi:10.1523/JNEUROSCI.6398-10.2011
apa: Vyleta, N., & Smith, S. (2011). Spontaneous glutamate release is independent
of calcium influx and tonically activated by the calcium-sensing receptor. European
Journal of Neuroscience. Wiley-Blackwell. https://doi.org/10.1523/JNEUROSCI.6398-10.2011
chicago: Vyleta, Nicholas, and Stephen Smith. “Spontaneous Glutamate Release Is
Independent of Calcium Influx and Tonically Activated by the Calcium-Sensing Receptor.”
European Journal of Neuroscience. Wiley-Blackwell, 2011. https://doi.org/10.1523/JNEUROSCI.6398-10.2011.
ieee: N. Vyleta and S. Smith, “Spontaneous glutamate release is independent of calcium
influx and tonically activated by the calcium-sensing receptor,” European Journal
of Neuroscience, vol. 31, no. 12. Wiley-Blackwell, pp. 4593–4606, 2011.
ista: Vyleta N, Smith S. 2011. Spontaneous glutamate release is independent of calcium
influx and tonically activated by the calcium-sensing receptor. European Journal
of Neuroscience. 31(12), 4593–4606.
mla: Vyleta, Nicholas, and Stephen Smith. “Spontaneous Glutamate Release Is Independent
of Calcium Influx and Tonically Activated by the Calcium-Sensing Receptor.” European
Journal of Neuroscience, vol. 31, no. 12, Wiley-Blackwell, 2011, pp. 4593–606,
doi:10.1523/JNEUROSCI.6398-10.2011.
short: N. Vyleta, S. Smith, European Journal of Neuroscience 31 (2011) 4593–4606.
date_created: 2018-12-11T11:46:39Z
date_published: 2011-03-23T00:00:00Z
date_updated: 2021-01-12T08:00:49Z
day: '23'
department:
- _id: PeJo
doi: 10.1523/JNEUROSCI.6398-10.2011
intvolume: ' 31'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3097128/
month: '03'
oa: 1
oa_version: Submitted Version
page: 4593 - 4606
publication: European Journal of Neuroscience
publication_status: published
publisher: Wiley-Blackwell
publist_id: '7353'
quality_controlled: '1'
scopus_import: 1
status: public
title: Spontaneous glutamate release is independent of calcium influx and tonically
activated by the calcium-sensing receptor
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2011'
...
---
_id: '490'
abstract:
- lang: eng
text: 'BioSig is an open source software library for biomedical signal processing.
The aim of the BioSig project is to foster research in biomedical signal processing
by providing free and open source software tools for many different application
areas. Some of the areas where BioSig can be employed are neuroinformatics, brain-computer
interfaces, neurophysiology, psychology, cardiovascular systems, and sleep research.
Moreover, the analysis of biosignals such as the electroencephalogram (EEG), electrocorticogram
(ECoG), electrocardiogram (ECG), electrooculogram (EOG), electromyogram (EMG),
or respiration signals is a very relevant element of the BioSig project. Specifically,
BioSig provides solutions for data acquisition, artifact processing, quality control,
feature extraction, classification, modeling, and data visualization, to name
a few. In this paper, we highlight several methods to help students and researchers
to work more efficiently with biomedical signals. '
article_number: '935364'
author:
- first_name: Alois
full_name: Schlögl, Alois
id: 45BF87EE-F248-11E8-B48F-1D18A9856A87
last_name: Schlögl
orcid: 0000-0002-5621-8100
- first_name: Carmen
full_name: Vidaurre, Carmen
last_name: Vidaurre
- first_name: Tilmann
full_name: Sander, Tilmann
last_name: Sander
citation:
ama: 'Schlögl A, Vidaurre C, Sander T. BioSig: The free and open source software
library for biomedical signal processing. Computational Intelligence and Neuroscience.
2011;2011. doi:10.1155/2011/935364'
apa: 'Schlögl, A., Vidaurre, C., & Sander, T. (2011). BioSig: The free and open
source software library for biomedical signal processing. Computational Intelligence
and Neuroscience. Hindawi Publishing Corporation. https://doi.org/10.1155/2011/935364'
chicago: 'Schlögl, Alois, Carmen Vidaurre, and Tilmann Sander. “BioSig: The Free
and Open Source Software Library for Biomedical Signal Processing.” Computational
Intelligence and Neuroscience. Hindawi Publishing Corporation, 2011. https://doi.org/10.1155/2011/935364.'
ieee: 'A. Schlögl, C. Vidaurre, and T. Sander, “BioSig: The free and open source
software library for biomedical signal processing,” Computational Intelligence
and Neuroscience, vol. 2011. Hindawi Publishing Corporation, 2011.'
ista: 'Schlögl A, Vidaurre C, Sander T. 2011. BioSig: The free and open source software
library for biomedical signal processing. Computational Intelligence and Neuroscience.
2011, 935364.'
mla: 'Schlögl, Alois, et al. “BioSig: The Free and Open Source Software Library
for Biomedical Signal Processing.” Computational Intelligence and Neuroscience,
vol. 2011, 935364, Hindawi Publishing Corporation, 2011, doi:10.1155/2011/935364.'
short: A. Schlögl, C. Vidaurre, T. Sander, Computational Intelligence and Neuroscience
2011 (2011).
date_created: 2018-12-11T11:46:45Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T08:01:02Z
day: '01'
ddc:
- '005'
department:
- _id: ScienComp
- _id: PeJo
doi: 10.1155/2011/935364
file:
- access_level: open_access
checksum: 8263bbf255171f2054f43f3db5f53b6e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:44Z
date_updated: 2020-07-14T12:46:35Z
file_id: '4642'
file_name: IST-2018-947-v1+1_2011_Schloegl_BioSig.pdf
file_size: 2863551
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 2011'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: Computational Intelligence and Neuroscience
publication_status: published
publisher: Hindawi Publishing Corporation
publist_id: '7330'
pubrep_id: '947'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'BioSig: The free and open source software library for biomedical signal processing'
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: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 2011
year: '2011'
...
---
_id: '491'
abstract:
- lang: eng
text: In their search for antigens, lymphocytes continuously shuttle among blood
vessels, lymph vessels, and lymphatic tissues. Chemokines mediate entry of lymphocytes
into lymphatic tissues, and sphingosine 1-phosphate (S1P) promotes localization
of lymphocytes to the vasculature. Both signals are sensed through G protein-coupled
receptors (GPCRs). Most GPCRs undergo ligand-dependent homologous receptor desensitization,
a process that decreases their signaling output after previous exposure to high
ligand concentration. Such desensitization can explain why lymphocytes do not
take an intermediate position between two signals but rather oscillate between
them. The desensitization of S1P receptor 1 (S1PR1) is mediated by GPCR kinase
2 (GRK2). Deletion of GRK2 in lymphocytes compromises desensitization by high
vascular S1P concentrations, thereby reducing responsiveness to the chemokine
signal and trapping the cells in the vascular compartment. The desensitization
kinetics of S1PR1 allows lymphocytes to dynamically shuttle between vasculature
and lymphatic tissue, although the positional information in both compartments
is static.
article_number: pe43
author:
- first_name: Alexander
full_name: Eichner, Alexander
id: 4DFA52AE-F248-11E8-B48F-1D18A9856A87
last_name: Eichner
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
citation:
ama: Eichner A, Sixt MK. Setting the clock for recirculating lymphocytes. Science
Signaling. 2011;4(198). doi:10.1126/scisignal.2002617
apa: Eichner, A., & Sixt, M. K. (2011). Setting the clock for recirculating
lymphocytes. Science Signaling. American Association for the Advancement
of Science. https://doi.org/10.1126/scisignal.2002617
chicago: Eichner, Alexander, and Michael K Sixt. “Setting the Clock for Recirculating
Lymphocytes.” Science Signaling. American Association for the Advancement
of Science, 2011. https://doi.org/10.1126/scisignal.2002617.
ieee: A. Eichner and M. K. Sixt, “Setting the clock for recirculating lymphocytes,”
Science Signaling, vol. 4, no. 198. American Association for the Advancement
of Science, 2011.
ista: Eichner A, Sixt MK. 2011. Setting the clock for recirculating lymphocytes.
Science Signaling. 4(198), pe43.
mla: Eichner, Alexander, and Michael K. Sixt. “Setting the Clock for Recirculating
Lymphocytes.” Science Signaling, vol. 4, no. 198, pe43, American Association
for the Advancement of Science, 2011, doi:10.1126/scisignal.2002617.
short: A. Eichner, M.K. Sixt, Science Signaling 4 (2011).
date_created: 2018-12-11T11:46:46Z
date_published: 2011-11-08T00:00:00Z
date_updated: 2021-01-12T08:01:02Z
day: '08'
department:
- _id: MiSi
doi: 10.1126/scisignal.2002617
intvolume: ' 4'
issue: '198'
language:
- iso: eng
month: '11'
oa_version: None
publication: Science Signaling
publication_status: published
publisher: American Association for the Advancement of Science
publist_id: '7329'
quality_controlled: '1'
scopus_import: 1
status: public
title: Setting the clock for recirculating lymphocytes
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2011'
...
---
_id: '518'
abstract:
- lang: eng
text: Cancer stem cells or cancer initiating cells are believed to contribute to
cancer recurrence after therapy. MicroRNAs (miRNAs) are short RNA molecules with
fundamental roles in gene regulation. The role of miRNAs in cancer stem cells
is only poorly understood. Here, we report miRNA expression profiles of glioblastoma
stem cell-containing CD133 + cell populations. We find that miR-9, miR-9 * (referred
to as miR-9/9 *), miR-17 and miR-106b are highly abundant in CD133 + cells. Furthermore,
inhibition of miR-9/9 * or miR-17 leads to reduced neurosphere formation and stimulates
cell differentiation. Calmodulin-binding transcription activator 1 (CAMTA1) is
a putative transcription factor, which induces the expression of the anti-proliferative
cardiac hormone natriuretic peptide A (NPPA). We identify CAMTA1 as an miR-9/9
* and miR-17 target. CAMTA1 expression leads to reduced neurosphere formation
and tumour growth in nude mice, suggesting that CAMTA1 can function as tumour
suppressor. Consistently, CAMTA1 and NPPA expression correlate with patient survival.
Our findings could provide a basis for novel strategies of glioblastoma therapy.
article_processing_charge: No
article_type: original
author:
- first_name: Daniel
full_name: Schraivogel, Daniel
last_name: Schraivogel
- first_name: Lasse
full_name: Weinmann, Lasse
last_name: Weinmann
- first_name: Dagmar
full_name: Beier, Dagmar
last_name: Beier
- first_name: Ghazaleh
full_name: Tabatabai, Ghazaleh
last_name: Tabatabai
- first_name: Alexander
full_name: Eichner, Alexander
id: 4DFA52AE-F248-11E8-B48F-1D18A9856A87
last_name: Eichner
- first_name: Jia
full_name: Zhu, Jia
last_name: Zhu
- first_name: Martina
full_name: Anton, Martina
last_name: Anton
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
- first_name: Michael
full_name: Weller, Michael
last_name: Weller
- first_name: Christoph
full_name: Beier, Christoph
last_name: Beier
- first_name: Gunter
full_name: Meister, Gunter
last_name: Meister
citation:
ama: Schraivogel D, Weinmann L, Beier D, et al. CAMTA1 is a novel tumour suppressor
regulated by miR-9/9 * in glioblastoma stem cells. EMBO Journal. 2011;30(20):4309-4322.
doi:10.1038/emboj.2011.301
apa: Schraivogel, D., Weinmann, L., Beier, D., Tabatabai, G., Eichner, A., Zhu,
J., … Meister, G. (2011). CAMTA1 is a novel tumour suppressor regulated by miR-9/9
* in glioblastoma stem cells. EMBO Journal. Wiley-Blackwell. https://doi.org/10.1038/emboj.2011.301
chicago: Schraivogel, Daniel, Lasse Weinmann, Dagmar Beier, Ghazaleh Tabatabai,
Alexander Eichner, Jia Zhu, Martina Anton, et al. “CAMTA1 Is a Novel Tumour Suppressor
Regulated by MiR-9/9 * in Glioblastoma Stem Cells.” EMBO Journal. Wiley-Blackwell,
2011. https://doi.org/10.1038/emboj.2011.301.
ieee: D. Schraivogel et al., “CAMTA1 is a novel tumour suppressor regulated
by miR-9/9 * in glioblastoma stem cells,” EMBO Journal, vol. 30, no. 20.
Wiley-Blackwell, pp. 4309–4322, 2011.
ista: Schraivogel D, Weinmann L, Beier D, Tabatabai G, Eichner A, Zhu J, Anton M,
Sixt MK, Weller M, Beier C, Meister G. 2011. CAMTA1 is a novel tumour suppressor
regulated by miR-9/9 * in glioblastoma stem cells. EMBO Journal. 30(20), 4309–4322.
mla: Schraivogel, Daniel, et al. “CAMTA1 Is a Novel Tumour Suppressor Regulated
by MiR-9/9 * in Glioblastoma Stem Cells.” EMBO Journal, vol. 30, no. 20,
Wiley-Blackwell, 2011, pp. 4309–22, doi:10.1038/emboj.2011.301.
short: D. Schraivogel, L. Weinmann, D. Beier, G. Tabatabai, A. Eichner, J. Zhu,
M. Anton, M.K. Sixt, M. Weller, C. Beier, G. Meister, EMBO Journal 30 (2011) 4309–4322.
date_created: 2018-12-11T11:46:55Z
date_published: 2011-10-19T00:00:00Z
date_updated: 2021-01-12T08:01:19Z
day: '19'
department:
- _id: MiSi
doi: 10.1038/emboj.2011.301
external_id:
pmid:
- '21857646'
intvolume: ' 30'
issue: '20'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3199389/
month: '10'
oa: 1
oa_version: Submitted Version
page: 4309 - 4322
pmid: 1
publication: EMBO Journal
publication_status: published
publisher: Wiley-Blackwell
publist_id: '7301'
quality_controlled: '1'
scopus_import: 1
status: public
title: CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma
stem cells
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2011'
...
---
_id: '531'
abstract:
- lang: eng
text: Software transactional memories (STM) are described in the literature with
assumptions of sequentially consistent program execution and atomicity of high
level operations like read, write, and abort. However, in a realistic setting,
processors use relaxed memory models to optimize hardware performance. Moreover,
the atomicity of operations depends on the underlying hardware. This paper presents
the first approach to verify STMs under relaxed memory models with atomicity of
32 bit loads and stores, and read-modify-write operations. We describe RML, a
simple language for expressing concurrent programs. We develop a semantics of
RML parametrized by a relaxed memory model. We then present our tool, FOIL, which
takes as input the RML description of an STM algorithm restricted to two threads
and two variables, and the description of a memory model, and automatically determines
the locations of fences, which if inserted, ensure the correctness of the restricted
STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and
McRT STM under the memory models of sequential consistency, total store order,
partial store order, and relaxed memory order for two threads and two variables.
Finally, we extend the verification results for DSTM and TL2 to an arbitrary number
of threads and variables by manually proving that the structural properties of
STMs are satisfied at the hardware level of atomicity under the considered relaxed
memory models.
article_processing_charge: No
article_type: original
author:
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- 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: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
citation:
ama: Guerraoui R, Henzinger TA, Singh V. Verification of STM on relaxed memory models.
Formal Methods in System Design. 2011;39(3):297-331. doi:10.1007/s10703-011-0131-3
apa: Guerraoui, R., Henzinger, T. A., & Singh, V. (2011). Verification of STM
on relaxed memory models. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-011-0131-3
chicago: Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Verification of
STM on Relaxed Memory Models.” Formal Methods in System Design. Springer,
2011. https://doi.org/10.1007/s10703-011-0131-3.
ieee: R. Guerraoui, T. A. Henzinger, and V. Singh, “Verification of STM on relaxed
memory models,” Formal Methods in System Design, vol. 39, no. 3. Springer,
pp. 297–331, 2011.
ista: Guerraoui R, Henzinger TA, Singh V. 2011. Verification of STM on relaxed memory
models. Formal Methods in System Design. 39(3), 297–331.
mla: Guerraoui, Rachid, et al. “Verification of STM on Relaxed Memory Models.” Formal
Methods in System Design, vol. 39, no. 3, Springer, 2011, pp. 297–331, doi:10.1007/s10703-011-0131-3.
short: R. Guerraoui, T.A. Henzinger, V. Singh, Formal Methods in System Design 39
(2011) 297–331.
date_created: 2018-12-11T11:47:00Z
date_published: 2011-12-01T00:00:00Z
date_updated: 2021-01-12T08:01:27Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/s10703-011-0131-3
intvolume: ' 39'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/178042/files/art3A10.10072Fs10703-011-0131-3.pdf
month: '12'
oa: 1
oa_version: Published Version
page: 297 - 331
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '7288'
quality_controlled: '1'
scopus_import: 1
status: public
title: Verification of STM on relaxed memory models
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 39
year: '2011'
...
---
_id: '5379'
abstract:
- lang: eng
text: Computing the winning set for Büchi objectives in alternating games on graphs
is a central problem in computer aided verification with a large number of applications.
The long standing best known upper bound for solving the problem is ̃O(n·m), where
n is the number of vertices and m is the number of edges in the graph. We are
the first to break the ̃O(n·m) boundary by presenting a new technique that reduces
the running time to O(n2). This bound also leads to O(n2) time algorithms for
computing the set of almost-sure winning vertices for Büchi objectives (1) in
alternating games with probabilistic transitions (improving an earlier bound of
O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier
bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3
an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique
can be used to compute the maximal end-component decomposition of a graph in time
O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show
how to maintain the winning set for Büchi objectives in alternating games under
a sequence of edge insertions or a sequence of edge deletions in O(n) amortized
time per operation. This is the first dynamic algorithm for this problem.
alternative_title:
- IST Austria Technical Report
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Chatterjee K, Henzinger MH. An O(N2) Time Algorithm for Alternating Büchi
Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0009
apa: Chatterjee, K., & Henzinger, M. H. (2011). An O(n2) time algorithm for
alternating Büchi games. IST Austria. https://doi.org/10.15479/AT:IST-2011-0009
chicago: Chatterjee, Krishnendu, and Monika H Henzinger. An O(N2) Time Algorithm
for Alternating Büchi Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0009.
ieee: K. Chatterjee and M. H. Henzinger, An O(n2) time algorithm for alternating
Büchi games. IST Austria, 2011.
ista: Chatterjee K, Henzinger MH. 2011. An O(n2) time algorithm for alternating
Büchi games, IST Austria, 20p.
mla: Chatterjee, Krishnendu, and Monika H. Henzinger. An O(N2) Time Algorithm
for Alternating Büchi Games. IST Austria, 2011, doi:10.15479/AT:IST-2011-0009.
short: K. Chatterjee, M.H. Henzinger, An O(N2) Time Algorithm for Alternating Büchi
Games, IST Austria, 2011.
date_created: 2018-12-12T11:38:59Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2023-02-23T11:15:12Z
day: '11'
ddc:
- '000'
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2011-0009
file:
- access_level: open_access
checksum: 0b354264229045d982332fd2cb5b9a26
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:43Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5504'
file_name: IST-2011-0009_IST-2011-0009.pdf
file_size: 388665
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: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '15'
related_material:
record:
- id: '3165'
relation: later_version
status: public
status: public
title: An O(n2) time algorithm for alternating Büchi games
type: technical_report
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2011'
...
---
_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'
...