---
_id: '1054'
abstract:
- lang: eng
text: We investigate local three-body correlations for bosonic particles in three
dimensions and one dimension as a function of the interaction strength. The three-body
correlation function g(3) is determined by measuring the three-body recombination
rate in an ultracold gas of Cs atoms. In three dimensions, we measure the dependence
of g(3) on the gas parameter in a BEC, finding good agreement with the theoretical
prediction accounting for beyond-mean-field effects. In one dimension, we observe
a reduction of g( 3) by several orders of magnitude upon increasing interactions
from the weakly interacting BEC to the strongly interacting Tonks-Girardeau regime,
in good agreement with predictions from the Lieb-Liniger model for all strengths
of interaction.
acknowledgement: We thank R. Grimm for generous support. We gratefully acknowledge
funding by the Austrian Science Fund (FWF) within Project No. I153-N16 and within
the framework of the European Science Foundation (ESF) EuroQUASAR collective research
project QuDeGPM. G. P. acknowledges funding from the EU through NAME-QUAM and AQUTE.
article_processing_charge: No
arxiv: 1
author:
- first_name: Elmar
full_name: Haller, Elmar
last_name: Haller
- first_name: Mahmoud
full_name: Rabie, Mahmoud
last_name: Rabie
- first_name: Manfred
full_name: Mark, Manfred
last_name: Mark
- first_name: Johann G
full_name: Danzl, Johann G
id: 42EFD3B6-F248-11E8-B48F-1D18A9856A87
last_name: Danzl
orcid: 0000-0001-8559-3973
- first_name: Russell
full_name: Hart, Russell
last_name: Hart
- first_name: Katharina
full_name: Lauber, Katharina
last_name: Lauber
- first_name: Guido
full_name: Pupillo, Guido
last_name: Pupillo
- first_name: Hanns
full_name: Nägerl, Hanns
last_name: Nägerl
citation:
ama: Haller E, Rabie M, Mark M, et al. Three-body correlation functions and recombination
rates for bosons in three dimensions and one dimension. Physical Review Letters.
2011;107(23). doi:10.1103/PhysRevLett.107.230404
apa: Haller, E., Rabie, M., Mark, M., Danzl, J. G., Hart, R., Lauber, K., … Nägerl,
H. (2011). Three-body correlation functions and recombination rates for bosons
in three dimensions and one dimension. Physical Review Letters. American
Physical Society. https://doi.org/10.1103/PhysRevLett.107.230404
chicago: Haller, Elmar, Mahmoud Rabie, Manfred Mark, Johann G Danzl, Russell Hart,
Katharina Lauber, Guido Pupillo, and Hanns Nägerl. “Three-Body Correlation Functions
and Recombination Rates for Bosons in Three Dimensions and One Dimension.” Physical
Review Letters. American Physical Society, 2011. https://doi.org/10.1103/PhysRevLett.107.230404.
ieee: E. Haller et al., “Three-body correlation functions and recombination
rates for bosons in three dimensions and one dimension,” Physical Review Letters,
vol. 107, no. 23. American Physical Society, 2011.
ista: Haller E, Rabie M, Mark M, Danzl JG, Hart R, Lauber K, Pupillo G, Nägerl H.
2011. Three-body correlation functions and recombination rates for bosons in three
dimensions and one dimension. Physical Review Letters. 107(23).
mla: Haller, Elmar, et al. “Three-Body Correlation Functions and Recombination Rates
for Bosons in Three Dimensions and One Dimension.” Physical Review Letters,
vol. 107, no. 23, American Physical Society, 2011, doi:10.1103/PhysRevLett.107.230404.
short: E. Haller, M. Rabie, M. Mark, J.G. Danzl, R. Hart, K. Lauber, G. Pupillo,
H. Nägerl, Physical Review Letters 107 (2011).
date_created: 2018-12-11T11:49:54Z
date_published: 2011-12-02T00:00:00Z
date_updated: 2021-01-12T06:47:57Z
day: '02'
doi: 10.1103/PhysRevLett.107.230404
extern: '1'
external_id:
arxiv:
- '1107.4516'
intvolume: ' 107'
issue: '23'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1107.4516
month: '12'
oa: 1
oa_version: Preprint
publication: Physical Review Letters
publication_status: published
publisher: American Physical Society
publist_id: '6335'
status: public
title: Three-body correlation functions and recombination rates for bosons in three
dimensions and one dimension
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 107
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: '967'
abstract:
- lang: eng
text: Motivated by recent experiments on the material Ba3NiSb 2O9, we consider a
spin-one quantum antiferromagnet on a triangular lattice with the Heisenberg bilinear
and biquadratic exchange interactions and a single-ion anisotropy. Using a fermionic
"triplon" representation for spins, we study the phase diagram within
mean-field theory. In addition to a fully gapped spin-liquid ground state, we
find a state where one gapless triplon mode with a Fermi surface coexists with
d+id topological pairing of the other triplons. Despite the existence of a Fermi
surface, this ground state has fully gapped bulk spin excitations. Such a state
has linear in-temperature specific heat and constant in-plane spin susceptibility,
with an unusually high Wilson ratio.
author:
- first_name: Maksym
full_name: Maksym Serbyn
id: 47809E7E-F248-11E8-B48F-1D18A9856A87
last_name: Serbyn
orcid: 0000-0002-2399-5827
- first_name: Todadri
full_name: Senthil, Todadri S
last_name: Senthil
- first_name: Patrick
full_name: Lee, Patrick
last_name: Lee
citation:
ama: Serbyn M, Senthil T, Lee P. Exotic S=1 spin-liquid state with fermionic excitations
on the triangular lattice. Physical Review B - Condensed Matter and Materials
Physics. 2011;84(18). doi:10.1103/PhysRevB.84.180403
apa: Serbyn, M., Senthil, T., & Lee, P. (2011). Exotic S=1 spin-liquid state
with fermionic excitations on the triangular lattice. Physical Review B - Condensed
Matter and Materials Physics. American Physical Society. https://doi.org/10.1103/PhysRevB.84.180403
chicago: Serbyn, Maksym, Todadri Senthil, and Patrick Lee. “Exotic S=1 Spin-Liquid
State with Fermionic Excitations on the Triangular Lattice.” Physical Review
B - Condensed Matter and Materials Physics. American Physical Society, 2011.
https://doi.org/10.1103/PhysRevB.84.180403.
ieee: M. Serbyn, T. Senthil, and P. Lee, “Exotic S=1 spin-liquid state with fermionic
excitations on the triangular lattice,” Physical Review B - Condensed Matter
and Materials Physics, vol. 84, no. 18. American Physical Society, 2011.
ista: Serbyn M, Senthil T, Lee P. 2011. Exotic S=1 spin-liquid state with fermionic
excitations on the triangular lattice. Physical Review B - Condensed Matter and
Materials Physics. 84(18).
mla: Serbyn, Maksym, et al. “Exotic S=1 Spin-Liquid State with Fermionic Excitations
on the Triangular Lattice.” Physical Review B - Condensed Matter and Materials
Physics, vol. 84, no. 18, American Physical Society, 2011, doi:10.1103/PhysRevB.84.180403.
short: M. Serbyn, T. Senthil, P. Lee, Physical Review B - Condensed Matter and Materials
Physics 84 (2011).
date_created: 2018-12-11T11:49:27Z
date_published: 2011-11-03T00:00:00Z
date_updated: 2021-01-12T08:22:18Z
day: '03'
doi: 10.1103/PhysRevB.84.180403
extern: 1
intvolume: ' 84'
issue: '18'
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1108.3070
month: '11'
oa: 1
publication: Physical Review B - Condensed Matter and Materials Physics
publication_status: published
publisher: American Physical Society
publist_id: '6432'
quality_controlled: 0
status: public
title: Exotic S=1 spin-liquid state with fermionic excitations on the triangular lattice
type: journal_article
volume: 84
year: '2011'
...
---
_id: '969'
abstract:
- lang: eng
text: We investigate the isotope effect on the London penetration depth of a superconductor
which measures n S/m*, the ratio of superfluid density to effective mass. We use
a simplified model of electrons weakly coupled to a single phonon frequency ω
E, but assume that the energy gap Δ does not have any isotope effect. Nevertheless,
we find an isotope effect for n S/m* which is significant if Δ is sufficiently
large that it becomes comparable to ω E, a regime of interest to high-T c cuprate
superconductors and possibly other families of unconventional superconductors
with relatively high T c. Our model is too simple to describe the cuprates and
it gives the wrong sign of the isotope effect when compared with experiment, but
it is a proof of principle that the isotope effect exists for n S/m* in materials
where the pairing gap and T c are not of phonon origin and have no isotope effect.
author:
- first_name: Maksym
full_name: Maksym Serbyn
id: 47809E7E-F248-11E8-B48F-1D18A9856A87
last_name: Serbyn
orcid: 0000-0002-2399-5827
- first_name: Patrick
full_name: Lee, Patrick
last_name: Lee
citation:
ama: Serbyn M, Lee P. Isotope effect on the superfluid density in conventional and
high-temperature superconductors. Physical Review B - Condensed Matter and
Materials Physics. 2011;83(2). doi:10.1103/PhysRevB.83.024506
apa: Serbyn, M., & Lee, P. (2011). Isotope effect on the superfluid density
in conventional and high-temperature superconductors. Physical Review B - Condensed
Matter and Materials Physics. American Physical Society. https://doi.org/10.1103/PhysRevB.83.024506
chicago: Serbyn, Maksym, and Patrick Lee. “Isotope Effect on the Superfluid Density
in Conventional and High-Temperature Superconductors.” Physical Review B -
Condensed Matter and Materials Physics. American Physical Society, 2011. https://doi.org/10.1103/PhysRevB.83.024506.
ieee: M. Serbyn and P. Lee, “Isotope effect on the superfluid density in conventional
and high-temperature superconductors,” Physical Review B - Condensed Matter
and Materials Physics, vol. 83, no. 2. American Physical Society, 2011.
ista: Serbyn M, Lee P. 2011. Isotope effect on the superfluid density in conventional
and high-temperature superconductors. Physical Review B - Condensed Matter and
Materials Physics. 83(2).
mla: Serbyn, Maksym, and Patrick Lee. “Isotope Effect on the Superfluid Density
in Conventional and High-Temperature Superconductors.” Physical Review B -
Condensed Matter and Materials Physics, vol. 83, no. 2, American Physical
Society, 2011, doi:10.1103/PhysRevB.83.024506.
short: M. Serbyn, P. Lee, Physical Review B - Condensed Matter and Materials Physics
83 (2011).
date_created: 2018-12-11T11:49:28Z
date_published: 2011-01-19T00:00:00Z
date_updated: 2021-01-12T08:22:19Z
day: '19'
doi: 10.1103/PhysRevB.83.024506
extern: 1
intvolume: ' 83'
issue: '2'
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1009.2429
month: '01'
oa: 1
publication: Physical Review B - Condensed Matter and Materials Physics
publication_status: published
publisher: American Physical Society
publist_id: '6434'
quality_controlled: 0
status: public
title: Isotope effect on the superfluid density in conventional and high-temperature
superconductors
type: journal_article
volume: 83
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: '3318'
abstract:
- lang: eng
text: Parvalbumin is thought to act in a manner similar to EGTA, but how a slow
Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear.
Direct measurements of parvalbumin concentration and paired recordings in rodent
hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics
only when expressed at high levels. Modeling suggests that, in high concentrations,
parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition
with local saturation of endogenous fixed buffers.
author:
- first_name: Emmanuel
full_name: Eggermann, Emmanuel
last_name: Eggermann
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Eggermann E, Jonas PM. How the “slow” Ca(2+) buffer parvalbumin affects transmitter
release in nanodomain coupling regimes at GABAergic synapses. Nature Neuroscience.
2011;15:20-22. doi:10.1038/nn.3002
apa: Eggermann, E., & Jonas, P. M. (2011). How the “slow” Ca(2+) buffer parvalbumin
affects transmitter release in nanodomain coupling regimes at GABAergic synapses.
Nature Neuroscience. Nature Publishing Group. https://doi.org/10.1038/nn.3002
chicago: Eggermann, Emmanuel, and Peter M Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin
Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.”
Nature Neuroscience. Nature Publishing Group, 2011. https://doi.org/10.1038/nn.3002.
ieee: E. Eggermann and P. M. Jonas, “How the ‘slow’ Ca(2+) buffer parvalbumin affects
transmitter release in nanodomain coupling regimes at GABAergic synapses,” Nature
Neuroscience, vol. 15. Nature Publishing Group, pp. 20–22, 2011.
ista: Eggermann E, Jonas PM. 2011. How the “slow” Ca(2+) buffer parvalbumin affects
transmitter release in nanodomain coupling regimes at GABAergic synapses. Nature
Neuroscience. 15, 20–22.
mla: Eggermann, Emmanuel, and Peter M. Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin
Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.”
Nature Neuroscience, vol. 15, Nature Publishing Group, 2011, pp. 20–22,
doi:10.1038/nn.3002.
short: E. Eggermann, P.M. Jonas, Nature Neuroscience 15 (2011) 20–22.
date_created: 2018-12-11T12:02:38Z
date_published: 2011-12-04T00:00:00Z
date_updated: 2021-01-12T07:42:37Z
day: '04'
department:
- _id: PeJo
doi: 10.1038/nn.3002
intvolume: ' 15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3631701/
month: '12'
oa: 1
oa_version: Submitted Version
page: 20 - 22
publication: Nature Neuroscience
publication_status: published
publisher: Nature Publishing Group
publist_id: '3321'
quality_controlled: '1'
scopus_import: 1
status: public
title: How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain
coupling regimes at GABAergic synapses
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2011'
...
---
_id: '3320'
abstract:
- lang: eng
text: Powerful statistical models that can be learned efficiently from large amounts
of data are currently revolutionizing computer vision. These models possess a
rich internal structure reflecting task-specific relations and constraints. This
monograph introduces the reader to the most popular classes of structured models
in computer vision. Our focus is discrete undirected graphical models which we
cover in detail together with a description of algorithms for both probabilistic
inference and maximum a posteriori inference. We discuss separately recently successful
techniques for prediction in general structured models. In the second part of
this monograph we describe methods for parameter learning where we distinguish
the classic maximum likelihood based methods from the more recent prediction-based
parameter learning methods. We highlight developments to enhance current models
and discuss kernelized models and latent variable models. To make the monograph
more practical and to provide links to further study we provide examples of successful
application of many methods in the computer vision literature.
article_processing_charge: No
article_type: original
author:
- first_name: Sebastian
full_name: Nowozin, Sebastian
last_name: Nowozin
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Nowozin S, Lampert C. Structured learning and prediction in computer vision.
Foundations and Trends in Computer Graphics and Vision. 2011;6(3-4):185-365.
doi:10.1561/0600000033
apa: Nowozin, S., & Lampert, C. (2011). Structured learning and prediction in
computer vision. Foundations and Trends in Computer Graphics and Vision.
Now Publishers. https://doi.org/10.1561/0600000033
chicago: Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction
in Computer Vision.” Foundations and Trends in Computer Graphics and Vision.
Now Publishers, 2011. https://doi.org/10.1561/0600000033.
ieee: S. Nowozin and C. Lampert, “Structured learning and prediction in computer
vision,” Foundations and Trends in Computer Graphics and Vision, vol. 6,
no. 3–4. Now Publishers, pp. 185–365, 2011.
ista: Nowozin S, Lampert C. 2011. Structured learning and prediction in computer
vision. Foundations and Trends in Computer Graphics and Vision. 6(3–4), 185–365.
mla: Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction
in Computer Vision.” Foundations and Trends in Computer Graphics and Vision,
vol. 6, no. 3–4, Now Publishers, 2011, pp. 185–365, doi:10.1561/0600000033.
short: S. Nowozin, C. Lampert, Foundations and Trends in Computer Graphics and Vision
6 (2011) 185–365.
date_created: 2018-12-11T12:02:39Z
date_published: 2011-05-23T00:00:00Z
date_updated: 2023-10-17T11:52:46Z
day: '23'
ddc:
- '000'
department:
- _id: ChLa
doi: 10.1561/0600000033
file:
- access_level: open_access
checksum: f1043ef389f1558e2a226bb51568511f
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T14:34:47Z
date_updated: 2020-07-14T12:46:07Z
file_id: '7837'
file_name: 2011_CompGraphicsVision_Nowozin.pdf
file_size: 3745064
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 6'
issue: 3-4
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 185 - 365
publication: Foundations and Trends in Computer Graphics and Vision
publication_status: published
publisher: Now Publishers
publist_id: '3315'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Structured learning and prediction in computer vision
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2011'
...
---
_id: '3324'
abstract:
- lang: eng
text: 'Automated termination provers often use the following schema to prove that
a program terminates: construct a relational abstraction of the program''s transition
relation and then show that the relational abstraction is well-founded. The focus
of current tools has been on developing sophisticated techniques for constructing
the abstractions while relying on known decidable logics (such as linear arithmetic)
to express them. We believe we can significantly increase the class of programs
that are amenable to automated termination proofs by identifying more expressive
decidable logics for reasoning about well-founded relations. We therefore present
a new decision procedure for reasoning about multiset orderings, which are among
the most powerful orderings used to prove termination. We show that, using our
decision procedure, one can automatically prove termination of natural abstractions
of programs.'
alternative_title:
- LNCS
author:
- first_name: Ruzica
full_name: Piskac, Ruzica
last_name: Piskac
- first_name: Thomas
full_name: Wies, Thomas
id: 447BFB88-F248-11E8-B48F-1D18A9856A87
last_name: Wies
citation:
ama: 'Piskac R, Wies T. Decision procedures for automating termination proofs. In:
Jhala R, Schmidt D, eds. Vol 6538. Springer; 2011:371-386. doi:10.1007/978-3-642-18275-4_26'
apa: 'Piskac, R., & Wies, T. (2011). Decision procedures for automating termination
proofs. In R. Jhala & D. Schmidt (Eds.) (Vol. 6538, pp. 371–386). Presented
at the VMCAI: Verification Model Checking and Abstract Interpretation, Texas,
USA: Springer. https://doi.org/10.1007/978-3-642-18275-4_26'
chicago: Piskac, Ruzica, and Thomas Wies. “Decision Procedures for Automating Termination
Proofs.” edited by Ranjit Jhala and David Schmidt, 6538:371–86. Springer, 2011.
https://doi.org/10.1007/978-3-642-18275-4_26.
ieee: 'R. Piskac and T. Wies, “Decision procedures for automating termination proofs,”
presented at the VMCAI: Verification Model Checking and Abstract Interpretation,
Texas, USA, 2011, vol. 6538, pp. 371–386.'
ista: 'Piskac R, Wies T. 2011. Decision procedures for automating termination proofs.
VMCAI: Verification Model Checking and Abstract Interpretation, LNCS, vol. 6538,
371–386.'
mla: Piskac, Ruzica, and Thomas Wies. Decision Procedures for Automating Termination
Proofs. Edited by Ranjit Jhala and David Schmidt, vol. 6538, Springer, 2011,
pp. 371–86, doi:10.1007/978-3-642-18275-4_26.
short: R. Piskac, T. Wies, in:, R. Jhala, D. Schmidt (Eds.), Springer, 2011, pp.
371–386.
conference:
end_date: 2011-01-25
location: Texas, USA
name: 'VMCAI: Verification Model Checking and Abstract Interpretation'
start_date: 2011-01-23
date_created: 2018-12-11T12:02:40Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:39Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-18275-4_26
editor:
- first_name: Ranjit
full_name: Jhala, Ranjit
last_name: Jhala
- first_name: David
full_name: Schmidt, David
last_name: Schmidt
intvolume: ' 6538'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/170697/
month: '01'
oa: 1
oa_version: Submitted Version
page: 371 - 386
publication_status: published
publisher: Springer
publist_id: '3311'
quality_controlled: '1'
scopus_import: 1
status: public
title: Decision procedures for automating termination proofs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6538
year: '2011'
...
---
_id: '3326'
abstract:
- lang: eng
text: 'Weighted automata map input words to numerical values. Ap- plications of
weighted automata include formal verification of quantitative properties, as well
as text, speech, and image processing. A weighted au- tomaton is defined with
respect to a semiring. For the tropical semiring, the weight of a run is the sum
of the weights of the transitions taken along the run, and the value of a word
is the minimal weight of an accepting run on it. In the 90’s, Krob studied the
decidability of problems on rational series defined with respect to the tropical
semiring. Rational series are strongly related to weighted automata, and Krob’s
results apply to them. In par- ticular, it follows from Krob’s results that the
universality problem (that is, deciding whether the values of all words are below
some threshold) is decidable for weighted automata defined with respect to the
tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable
when the domain is ∪ {∞}. In this paper we continue the study of the borders of
decidability in weighted automata, describe alternative and direct proofs of the
above results, and tighten them further. Unlike the proofs of Krob, which are
algebraic in their nature, our proofs stay in the terrain of state machines, and
the reduction is from the halting problem of a two-counter machine. This enables
us to significantly simplify Krob’s reasoning, make the un- decidability result
accessible to the automata-theoretic community, and strengthen it to apply already
to a very simple class of automata: all the states are accepting, there are no
initial nor final weights, and all the weights on the transitions are from the
set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten
also the decidability re- sults and to show that the universality problem for
weighted automata defined with respect to the tropical semiring with domain ∪
{∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus
draw a sharper picture about the decidability of decision problems for weighted
automata, in both the front of containment vs. universality and the front of the
∪ {∞} vs. the ∪ {∞} domains.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shaull
full_name: Almagor, Shaull
last_name: Almagor
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: 'Almagor S, Boker U, Kupferman O. What’s decidable about weighted automata
. In: Vol 6996. Springer; 2011:482-491. doi:10.1007/978-3-642-24372-1_37'
apa: 'Almagor, S., Boker, U., & Kupferman, O. (2011). What’s decidable about
weighted automata (Vol. 6996, pp. 482–491). Presented at the ATVA: Automated
Technology for Verification and Analysis, Taipei, Taiwan: Springer. https://doi.org/10.1007/978-3-642-24372-1_37'
chicago: Almagor, Shaull, Udi Boker, and Orna Kupferman. “What’s Decidable about
Weighted Automata ,” 6996:482–91. Springer, 2011. https://doi.org/10.1007/978-3-642-24372-1_37.
ieee: 'S. Almagor, U. Boker, and O. Kupferman, “What’s decidable about weighted
automata ,” presented at the ATVA: Automated Technology for Verification and Analysis,
Taipei, Taiwan, 2011, vol. 6996, pp. 482–491.'
ista: 'Almagor S, Boker U, Kupferman O. 2011. What’s decidable about weighted automata
. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6996, 482–491.'
mla: Almagor, Shaull, et al. What’s Decidable about Weighted Automata . Vol.
6996, Springer, 2011, pp. 482–91, doi:10.1007/978-3-642-24372-1_37.
short: S. Almagor, U. Boker, O. Kupferman, in:, Springer, 2011, pp. 482–491.
conference:
end_date: 2011-10-14
location: Taipei, Taiwan
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2011-10-11
date_created: 2018-12-11T12:02:41Z
date_published: 2011-10-14T00:00:00Z
date_updated: 2021-01-12T07:42:40Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-24372-1_37
file:
- access_level: open_access
checksum: a7ca08a2cb1b6925f4c18a3034ae5659
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:08:32Z
date_updated: 2020-07-14T12:46:07Z
file_id: '7868'
file_name: 2011_LNCS_Almagor.pdf
file_size: 182309
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
intvolume: ' 6996'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 482 - 491
publication_status: published
publisher: Springer
publist_id: '3309'
quality_controlled: '1'
status: public
title: 'What’s decidable about weighted automata '
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6996
year: '2011'
...
---
_id: '3328'
abstract:
- lang: eng
text: 'We report on a generic uni- and bivariate algebraic kernel that is publicly
available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art
implementations on polynomials, roots of polynomial systems, and the support to
analyze algebraic curves defined by bivariate polynomials. The kernel design is
generic, that is, various number types and substeps can be exchanged. It is accompanied
with a ready-to-use interface to enable arrangements induced by algebraic curves,
that have already been used as basis for various geometric applications, as arrangements
on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel
applications: arrangements of rotated algebraic curves and Boolean set operations
on polygons bounded by segments of algebraic curves. We also provide experiments
showing that our general implementation is competitive and even often clearly
outperforms existing implementations that are explicitly tailored for specific
types of non-linear curves that are available in CGAL.'
article_processing_charge: No
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Michael
full_name: Hemmer, Michael
last_name: Hemmer
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear
geometric applications. In: ACM; 2011:179-186. doi:10.1145/1998196.1998224'
apa: 'Berberich, E., Hemmer, M., & Kerber, M. (2011). A generic algebraic kernel
for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium
on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998224'
chicago: Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic
Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. https://doi.org/10.1145/1998196.1998224.
ieee: 'E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non
linear geometric applications,” presented at the SCG: Symposium on Computational
Geometry, Paris, France, 2011, pp. 179–186.'
ista: 'Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non
linear geometric applications. SCG: Symposium on Computational Geometry, 179–186.'
mla: Berberich, Eric, et al. A Generic Algebraic Kernel for Non Linear Geometric
Applications. ACM, 2011, pp. 179–86, doi:10.1145/1998196.1998224.
short: E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2021-01-12T07:42:41Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998224
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.inria.fr/inria-00480031/file/RR-7274.pdf
month: '06'
oa: 1
oa_version: Published Version
page: 179 - 186
publication_status: published
publisher: ACM
publist_id: '3307'
quality_controlled: '1'
scopus_import: 1
status: public
title: A generic algebraic kernel for non linear geometric applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3329'
abstract:
- lang: eng
text: 'We consider the offset-deconstruction problem: Given a polygonal shape Q
with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance,
as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
If it does, we also seek a preferably simple-looking solution shape P; then, P''s
offset constitutes an accurate, vertex-reduced, and smoothened approximation of
Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal
shape, assuming the real-RAM model of computation. An alternative algorithm, based
purely on rational arithmetic, answers the same deconstruction problem, up to
an uncertainty parameter, and its running time depends on the parameter δ (in
addition to the other input parameters: n, δ and the radius of the disk). If the
input shape is found to be approximable, the rational-arithmetic algorithm also
computes an approximate solution shape for the problem. For convex shapes, the
complexity of the exact decision algorithm drops to O(n), which is also the time
required to compute a solution shape P with at most one more vertex than a vertex-minimal
one. Our study is motivated by applications from two different domains. However,
since the offset operation has numerous uses, we anticipate that the reverse question
that we study here will be still more broadly applicable. We present results obtained
with our implementation of the rational-arithmetic algorithm.'
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate
offsets. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational
Geometry. ACM; 2011:187-196. doi:10.1145/1998196.1998225'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2011). Deconstructing
approximate offsets. In Proceedings of the twenty-seventh annual symposium
on Computational geometry (pp. 187–196). Paris, France: ACM. https://doi.org/10.1145/1998196.1998225'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
Approximate Offsets.” In Proceedings of the Twenty-Seventh Annual Symposium
on Computational Geometry, 187–96. ACM, 2011. https://doi.org/10.1145/1998196.1998225.
ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
approximate offsets,” in Proceedings of the twenty-seventh annual symposium
on Computational geometry, Paris, France, 2011, pp. 187–196.
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate
offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry.
SCG: Symposium on Computational Geometry, 187–196.'
mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Proceedings
of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011,
pp. 187–96, doi:10.1145/1998196.1998225.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of
the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp.
187–196.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2023-02-23T11:12:57Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998225
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1109.2158
month: '06'
oa: 1
oa_version: Preprint
page: 187 - 196
publication: Proceedings of the twenty-seventh annual symposium on Computational geometry
publication_status: published
publisher: ACM
publist_id: '3306'
quality_controlled: '1'
related_material:
record:
- id: '3115'
relation: later_version
status: public
scopus_import: 1
status: public
title: Deconstructing approximate offsets
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3330'
abstract:
- lang: eng
text: We consider the problem of approximating all real roots of a square-free polynomial
f. Given isolating intervals, our algorithm refines each of them to a width at
most 2-L, that is, each of the roots is approximated to L bits after the binary
point. Our method provides a certified answer for arbitrary real polynomials,
only requiring finite approximations of the polynomial coefficient and choosing
a suitable working precision adaptively. In this way, we get a correct algorithm
that is simple to implement and practically efficient. Our algorithm uses the
quadratic interval refinement method; we adapt that method to be able to cope
with inaccuracies when evaluating f, without sacrificing its quadratic convergence
behavior. We prove a bound on the bit complexity of our algorithm in terms of
degree, coefficient size and discriminant. Our bound improves previous work on
integer polynomials by a factor of deg f and essentially matches best known theoretical
bounds on root approximation which are obtained by very sophisticated algorithms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: 'Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer;
2011:209-216. doi:10.1145/1993886.1993920'
apa: 'Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials
(pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920'
chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
USA, 2011, pp. 209–216.'
ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
International Symposium on Symbolic and Algebraic Computation, 209–216.'
mla: Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials.
Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
end_date: 2011-06-11
location: California, USA
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
arxiv:
- '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3332'
abstract:
- lang: eng
text: Given an algebraic hypersurface O in ℝd, how many simplices are necessary
for a simplicial complex isotopic to O? We address this problem and the variant
where all vertices of the complex must lie on O. We give asymptotically tight
worst-case bounds for algebraic plane curves. Our results gradually improve known
bounds in higher dimensions; however, the question for tight bounds remains unsolved
for d ≥ 3.
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: Kerber M, Sagraloff M. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 2011;27(3):419-430. doi:10.1007/s00373-011-1020-7
apa: Kerber, M., & Sagraloff, M. (2011). A note on the complexity of real algebraic
hypersurfaces. Graphs and Combinatorics. Springer. https://doi.org/10.1007/s00373-011-1020-7
chicago: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real
Algebraic Hypersurfaces.” Graphs and Combinatorics. Springer, 2011. https://doi.org/10.1007/s00373-011-1020-7.
ieee: M. Kerber and M. Sagraloff, “A note on the complexity of real algebraic hypersurfaces,”
Graphs and Combinatorics, vol. 27, no. 3. Springer, pp. 419–430, 2011.
ista: Kerber M, Sagraloff M. 2011. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 27(3), 419–430.
mla: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic
Hypersurfaces.” Graphs and Combinatorics, vol. 27, no. 3, Springer, 2011,
pp. 419–30, doi:10.1007/s00373-011-1020-7.
short: M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 419–430.
date_created: 2018-12-11T12:02:43Z
date_published: 2011-03-17T00:00:00Z
date_updated: 2021-01-12T07:42:43Z
day: '17'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s00373-011-1020-7
file:
- access_level: open_access
checksum: a63a1e3e885dcc68f1e3dea68dfbe213
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:11:36Z
date_updated: 2020-07-14T12:46:08Z
file_id: '7869'
file_name: 2011_GraphsCombi_Kerber.pdf
file_size: 143976
relation: main_file
file_date_updated: 2020-07-14T12:46:08Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 419 - 430
publication: Graphs and Combinatorics
publication_status: published
publisher: Springer
publist_id: '3301'
quality_controlled: '1'
scopus_import: 1
status: public
title: A note on the complexity of real algebraic hypersurfaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
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: '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'
...