---
_id: '8522'
abstract:
- lang: eng
text: For diffeomorphisms of smooth compact manifolds, we consider the problem of
how fast the number of periodic points with period $n$grows as a function of $n$.
In many familiar cases (e.g., Anosov systems) the growth is exponential, but arbitrarily
fast growth is possible; in fact, the first author has shown that arbitrarily
fast growth is topologically (Baire) generic for $C^2$ or smoother diffeomorphisms.
In the present work we show that, by contrast, for a measure-theoretic notion
of genericity we call ``prevalence'', the growth is not much faster than exponential.
Specifically, we show that for each $\delta > 0$, there is a prevalent set of
( $C^{1+\rho}$ or smoother) diffeomorphisms for which the number of period $n$
points is bounded above by $\operatorname{exp}(C n^{1+\delta})$ for some $C$ independent
of $n$. We also obtain a related bound on the decay of the hyperbolicity of the
periodic points as a function of $n$. The contrast between topologically generic
and measure-theoretically generic behavior for the growth of the number of periodic
points and the decay of their hyperbolicity shows this to be a subtle and complex
phenomenon, reminiscent of KAM theory.
article_processing_charge: No
article_type: original
author:
- first_name: Vadim
full_name: Kaloshin, Vadim
id: FE553552-CDE8-11E9-B324-C0EBE5697425
last_name: Kaloshin
orcid: 0000-0002-6051-2628
- first_name: Brian R.
full_name: Hunt, Brian R.
last_name: Hunt
citation:
ama: Kaloshin V, Hunt BR. A stretched exponential bound on the rate of growth of
the number of periodic points for prevalent diffeomorphisms I. Electronic Research
Announcements of the American Mathematical Society. 2001;7(4):17-27. doi:10.1090/s1079-6762-01-00090-7
apa: Kaloshin, V., & Hunt, B. R. (2001). A stretched exponential bound on the
rate of growth of the number of periodic points for prevalent diffeomorphisms
I. Electronic Research Announcements of the American Mathematical Society.
American Mathematical Society. https://doi.org/10.1090/s1079-6762-01-00090-7
chicago: Kaloshin, Vadim, and Brian R. Hunt. “A Stretched Exponential Bound on the
Rate of Growth of the Number of Periodic Points for Prevalent Diffeomorphisms
I.” Electronic Research Announcements of the American Mathematical Society.
American Mathematical Society, 2001. https://doi.org/10.1090/s1079-6762-01-00090-7.
ieee: V. Kaloshin and B. R. Hunt, “A stretched exponential bound on the rate of
growth of the number of periodic points for prevalent diffeomorphisms I,” Electronic
Research Announcements of the American Mathematical Society, vol. 7, no. 4.
American Mathematical Society, pp. 17–27, 2001.
ista: Kaloshin V, Hunt BR. 2001. A stretched exponential bound on the rate of growth
of the number of periodic points for prevalent diffeomorphisms I. Electronic Research
Announcements of the American Mathematical Society. 7(4), 17–27.
mla: Kaloshin, Vadim, and Brian R. Hunt. “A Stretched Exponential Bound on the Rate
of Growth of the Number of Periodic Points for Prevalent Diffeomorphisms I.” Electronic
Research Announcements of the American Mathematical Society, vol. 7, no. 4,
American Mathematical Society, 2001, pp. 17–27, doi:10.1090/s1079-6762-01-00090-7.
short: V. Kaloshin, B.R. Hunt, Electronic Research Announcements of the American
Mathematical Society 7 (2001) 17–27.
date_created: 2020-09-18T10:49:56Z
date_published: 2001-04-18T00:00:00Z
date_updated: 2021-01-12T08:19:51Z
day: '18'
doi: 10.1090/s1079-6762-01-00090-7
extern: '1'
intvolume: ' 7'
issue: '4'
keyword:
- General Mathematics
language:
- iso: eng
month: '04'
oa_version: None
page: 17-27
publication: Electronic Research Announcements of the American Mathematical Society
publication_identifier:
issn:
- 1079-6762
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
status: public
title: A stretched exponential bound on the rate of growth of the number of periodic
points for prevalent diffeomorphisms I
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2001'
...
---
_id: '8524'
abstract:
- lang: eng
text: 'A number α∈R is diophantine if it is not well approximable by rationals,
i.e. for some C,ε>0 and any relatively prime p,q∈Z we have |αq−p|>Cq−1−ε. It is
well-known and is easy to prove that almost every α in R is diophantine. In this
paper we address a noncommutative version of the diophantine properties. Consider
a pair A,B∈SO(3) and for each n∈Z+ take all possible words in A, A -1, B, and
B - 1 of length n, i.e. for a multiindex I=(i1,i1,…,im,jm) define |I|=∑mk=1(|ik|+|jk|)=n
and \( W_n(A,B ) = \{W_{\cal I}(A,B) = A^{i_1} B^{j_1} \dots A^{i_m} B^{j_m}\}_{|{\cal
I|}=n \).¶Gamburd—Jakobson—Sarnak [GJS] raised the problem: prove that for Haar
almost every pair A,B∈SO(3) the closest distance of words of length n to the identity,
i.e. sA,B(n)=min|I|=n∥WI(A,B)−E∥, is bounded from below by an exponential function
in n. This is the analog of the diophantine property for elements of SO(3). In
this paper we prove that s A,B (n) is bounded from below by an exponential function
in n 2. We also exhibit obstructions to a “simple” proof of the exponential estimate
in n.'
article_processing_charge: No
article_type: original
author:
- first_name: Vadim
full_name: Kaloshin, Vadim
id: FE553552-CDE8-11E9-B324-C0EBE5697425
last_name: Kaloshin
orcid: 0000-0002-6051-2628
- first_name: I.
full_name: Rodnianski, I.
last_name: Rodnianski
citation:
ama: Kaloshin V, Rodnianski I. Diophantine properties of elements of SO(3). Geometric
And Functional Analysis. 2001;11(5):953-970. doi:10.1007/s00039-001-8222-8
apa: Kaloshin, V., & Rodnianski, I. (2001). Diophantine properties of elements
of SO(3). Geometric And Functional Analysis. Springer Nature. https://doi.org/10.1007/s00039-001-8222-8
chicago: Kaloshin, Vadim, and I. Rodnianski. “Diophantine Properties of Elements
of SO(3).” Geometric And Functional Analysis. Springer Nature, 2001. https://doi.org/10.1007/s00039-001-8222-8.
ieee: V. Kaloshin and I. Rodnianski, “Diophantine properties of elements of SO(3),”
Geometric And Functional Analysis, vol. 11, no. 5. Springer Nature, pp.
953–970, 2001.
ista: Kaloshin V, Rodnianski I. 2001. Diophantine properties of elements of SO(3).
Geometric And Functional Analysis. 11(5), 953–970.
mla: Kaloshin, Vadim, and I. Rodnianski. “Diophantine Properties of Elements of
SO(3).” Geometric And Functional Analysis, vol. 11, no. 5, Springer Nature,
2001, pp. 953–70, doi:10.1007/s00039-001-8222-8.
short: V. Kaloshin, I. Rodnianski, Geometric And Functional Analysis 11 (2001) 953–970.
date_created: 2020-09-18T10:50:11Z
date_published: 2001-12-01T00:00:00Z
date_updated: 2021-01-12T08:19:52Z
day: '01'
doi: 10.1007/s00039-001-8222-8
extern: '1'
intvolume: ' 11'
issue: '5'
language:
- iso: eng
month: '12'
oa_version: None
page: 953-970
publication: Geometric And Functional Analysis
publication_identifier:
issn:
- 1016-443X
- 1420-8970
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Diophantine properties of elements of SO(3)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2001'
...
---
_id: '855'
abstract:
- lang: eng
text: 'Motivation: The context of the start codon (typically, AUG) and the features
of the 5′ Untranslated Regions (5′ UTRs) are important for understanding translation
regulation in eukaryotic mRNAs and for accurate prediction of the coding region
in genomic and cDNA sequences. The presence of AUG triplets in 5′ UTRs (upstream
AUGs) might effect the initiation rate and, in the context of gene prediction,
could reduce the accuracy of the identification of the authentic start. To reveal
potential connections between the presence of upstream AUGs and other features
of 5′ UTRs, such as their length and the start codon context, we undertook a systematic
analysis of the available eukaryotic 5′ UTR sequences. Results: We show that a
large fraction of 5′ UTRs in the available cDNA sequences, 15-53% depending on
the organism, contain upstream ATGs. A negative correlation was observed between
the information content of the translation start signal and the length of the
5′ UTR. Similarly, a negative correlation exists between the ''strength'' of the
start context and the number of upstream ATGs. Typically, cDNAs containing long
5′ UTRs with multiple upstream ATGs have a ''weak'' start context, and in contrast,
cDNAs containing short 5′ UTRs without ATGs have ''strong'' starts. These counter-intuitive
results may be interpreted in terms of upstream AUGs having an important role
in the regulation of translation efficiency by ensuring low basal translation
level via double negative control and creating the potential for additional regulatory
mechanisms. One of such mechanisms, supported by experimental studies of some
mRNAs, includes removal of the AUG-containing portion of the 5′ UTR by alternative
splicing.'
acknowledgement: This work has been partially supported by EU 'TRADAT' project and
by CNR Genetic Engineering (Italy), the RFBR grant for support of scientific schools
(00-15-97968) and SD RAS grant for young scientists (AVK). The authors wish to thank
J.Lyons-Weiler for helpful comments and A. Sorokin for help with the ATG_EVALUATOR
program.
article_processing_charge: No
article_type: original
author:
- first_name: Igor
full_name: Rogozin, Igor
last_name: Rogozin
- first_name: Alex
full_name: Kochetov, Alex
last_name: Kochetov
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Eugene
full_name: Koonin, Eugene
last_name: Koonin
- first_name: Luciano
full_name: Milanesi, Luciano
last_name: Milanesi
citation:
ama: Rogozin I, Kochetov A, Kondrashov F, Koonin E, Milanesi L. Presence of ATG
triplets in 5′ untranslated regions of eukaryotic cDNAs correlates with a ’weak’context
of the start codon. Bioinformatics. 2001;17(10):890-900. doi:10.1093/bioinformatics/17.10.890
apa: Rogozin, I., Kochetov, A., Kondrashov, F., Koonin, E., & Milanesi, L. (2001).
Presence of ATG triplets in 5′ untranslated regions of eukaryotic cDNAs correlates
with a ’weak’context of the start codon. Bioinformatics. Oxford University
Press. https://doi.org/10.1093/bioinformatics/17.10.890
chicago: Rogozin, Igor, Alex Kochetov, Fyodor Kondrashov, Eugene Koonin, and Luciano
Milanesi. “Presence of ATG Triplets in 5′ Untranslated Regions of Eukaryotic CDNAs
Correlates with a ’weak’context of the Start Codon.” Bioinformatics. Oxford
University Press, 2001. https://doi.org/10.1093/bioinformatics/17.10.890.
ieee: I. Rogozin, A. Kochetov, F. Kondrashov, E. Koonin, and L. Milanesi, “Presence
of ATG triplets in 5′ untranslated regions of eukaryotic cDNAs correlates with
a ’weak’context of the start codon,” Bioinformatics, vol. 17, no. 10. Oxford
University Press, pp. 890–900, 2001.
ista: Rogozin I, Kochetov A, Kondrashov F, Koonin E, Milanesi L. 2001. Presence
of ATG triplets in 5′ untranslated regions of eukaryotic cDNAs correlates with
a ’weak’context of the start codon. Bioinformatics. 17(10), 890–900.
mla: Rogozin, Igor, et al. “Presence of ATG Triplets in 5′ Untranslated Regions
of Eukaryotic CDNAs Correlates with a ’weak’context of the Start Codon.” Bioinformatics,
vol. 17, no. 10, Oxford University Press, 2001, pp. 890–900, doi:10.1093/bioinformatics/17.10.890.
short: I. Rogozin, A. Kochetov, F. Kondrashov, E. Koonin, L. Milanesi, Bioinformatics
17 (2001) 890–900.
date_created: 2018-12-11T11:48:52Z
date_published: 2001-10-01T00:00:00Z
date_updated: 2023-06-02T09:08:25Z
day: '01'
doi: 10.1093/bioinformatics/17.10.890
extern: '1'
external_id:
pmid:
- '11673233'
intvolume: ' 17'
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
page: 890 - 900
pmid: 1
publication: Bioinformatics
publication_identifier:
issn:
- 1367-4803
publication_status: published
publisher: Oxford University Press
publist_id: '6795'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Presence of ATG triplets in 5′ untranslated regions of eukaryotic cDNAs correlates
with a 'weak'context of the start codon
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '2001'
...
---
_id: '867'
abstract:
- lang: eng
text: Genes with new functions often evolve by gene duplication. Alternative splicing
is another means of evolutionary innovation in eukaryotes, which allows a single
gene to encode functionally diverse proteins. We investigate a connection between
these two evolutionary phenomena. For ∼10% of the described cases of substitution
alternative splicing, such that either one or another amino acid sequence is included
into the protein, evidence of origin by tandem exon duplication was found. This
is a conservative estimate because alternative exons are typically short and,
on many occasions, duplicates may have diverged beyond recognition. Dating exon
duplications through a combination of the available experimental data on alternative
splicing in orthologous genes from different species and computational analysis
indicates that most of the duplications antedate at least the radiation of mammalian
orders or even the radiation of vertebrate classes. At present, tandem exon duplication
is the only mechanism of evolution of substitution alternative splicing that can
be specifically demonstrated. Along with gene duplication, this could be a major
route for generating functional diversity during evolution of multicellular eukaryotes.
article_processing_charge: No
article_type: original
author:
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Eugene
full_name: Koonin, Eugene
last_name: Koonin
citation:
ama: Kondrashov F, Koonin E. Origin of alternative splicing by tandem exon duplication.
Human Molecular Genetics. 2001;10(23):2661-2669. doi:10.1093/hmg/10.23.2661
apa: Kondrashov, F., & Koonin, E. (2001). Origin of alternative splicing by
tandem exon duplication. Human Molecular Genetics. Oxford University Press.
https://doi.org/10.1093/hmg/10.23.2661
chicago: Kondrashov, Fyodor, and Eugene Koonin. “Origin of Alternative Splicing
by Tandem Exon Duplication.” Human Molecular Genetics. Oxford University
Press, 2001. https://doi.org/10.1093/hmg/10.23.2661.
ieee: F. Kondrashov and E. Koonin, “Origin of alternative splicing by tandem exon
duplication,” Human Molecular Genetics, vol. 10, no. 23. Oxford University
Press, pp. 2661–2669, 2001.
ista: Kondrashov F, Koonin E. 2001. Origin of alternative splicing by tandem exon
duplication. Human Molecular Genetics. 10(23), 2661–2669.
mla: Kondrashov, Fyodor, and Eugene Koonin. “Origin of Alternative Splicing by Tandem
Exon Duplication.” Human Molecular Genetics, vol. 10, no. 23, Oxford University
Press, 2001, pp. 2661–69, doi:10.1093/hmg/10.23.2661.
short: F. Kondrashov, E. Koonin, Human Molecular Genetics 10 (2001) 2661–2669.
date_created: 2018-12-11T11:48:55Z
date_published: 2001-11-01T00:00:00Z
date_updated: 2023-06-02T08:39:47Z
day: '01'
doi: 10.1093/hmg/10.23.2661
extern: '1'
external_id:
pmid:
- '11726553'
intvolume: ' 10'
issue: '23'
language:
- iso: eng
month: '11'
oa_version: Published Version
page: 2661 - 2669
pmid: 1
publication: Human Molecular Genetics
publication_identifier:
issn:
- 0964-6906
publication_status: published
publisher: Oxford University Press
publist_id: '6777'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Origin of alternative splicing by tandem exon duplication
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '2001'
...
---
_id: '874'
abstract:
- lang: eng
text: Sex is thought to facilitate accumulation of initially rare beneficial mutations
by allowing simultaneous allele replacements at many loci. However, this advantage
of sex depends on a restrictive assumption that the fitness of a genotype is determined
by fitness potential, a single intermediate variable to which all loci contribute
additively, so that new alleles can accumulate in any order. Individual-based
simulations of sexual and asexual populations reveal that under generic selection,
sex often retards adaptive evolution. When new alleles are beneficial only if
they accumulate in a prescribed order, a sexual population may evolve two or more
times slower than an asexual population because only asexual reproduction allows
some overlap of successive allele replacements. Many other fitness surfaces lead
to an even greater disadvantage of sex. Thus, either sex exists in spite of its
impact on the rate of adaptive allele replacements, or natural fitness surfaces
have rather specific properties, at least at the scale of intrapopulation genetic
variability.
article_processing_charge: No
article_type: original
author:
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Alexey
full_name: Kondrashov, Alexey
last_name: Kondrashov
citation:
ama: Kondrashov F, Kondrashov A. Multidimensional epistasis and the disadvantage
of sex. PNAS. 2001;98(21):12089-12092. doi:10.1073/pnas.211214298
apa: Kondrashov, F., & Kondrashov, A. (2001). Multidimensional epistasis and
the disadvantage of sex. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.211214298
chicago: Kondrashov, Fyodor, and Alexey Kondrashov. “Multidimensional Epistasis
and the Disadvantage of Sex.” PNAS. National Academy of Sciences, 2001.
https://doi.org/10.1073/pnas.211214298.
ieee: F. Kondrashov and A. Kondrashov, “Multidimensional epistasis and the disadvantage
of sex,” PNAS, vol. 98, no. 21. National Academy of Sciences, pp. 12089–12092,
2001.
ista: Kondrashov F, Kondrashov A. 2001. Multidimensional epistasis and the disadvantage
of sex. PNAS. 98(21), 12089–12092.
mla: Kondrashov, Fyodor, and Alexey Kondrashov. “Multidimensional Epistasis and
the Disadvantage of Sex.” PNAS, vol. 98, no. 21, National Academy of Sciences,
2001, pp. 12089–92, doi:10.1073/pnas.211214298.
short: F. Kondrashov, A. Kondrashov, PNAS 98 (2001) 12089–12092.
date_created: 2018-12-11T11:48:58Z
date_published: 2001-10-09T00:00:00Z
date_updated: 2023-06-02T08:18:22Z
day: '09'
doi: 10.1073/pnas.211214298
extern: '1'
external_id:
pmid:
- '11593020'
intvolume: ' 98'
issue: '21'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC59772/
month: '10'
oa: 1
oa_version: Published Version
page: 12089 - 12092
pmid: 1
publication: PNAS
publication_identifier:
issn:
- 0027-8424
publication_status: published
publisher: National Academy of Sciences
publist_id: '6774'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multidimensional epistasis and the disadvantage of sex
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 98
year: '2001'
...
---
_id: '888'
abstract:
- lang: eng
text: 'BACKGROUND: Detection of changes in a protein''s evolutionary rate may reveal
cases of change in that protein''s function. We developed and implemented a simple
relative rates test in an attempt to assess the rate constancy of protein evolution
and to detect cases of functional diversification between orthologous proteins.
The test was performed on clusters of orthologous protein sequences from complete
bacterial genomes (Chlamydia trachomatis, C. muridarum and Chlamydophila pneumoniae),
complete archaeal genomes (Pyrococcus horikoshii, P. abyssi and P. furiosus) and
partially sequenced mammalian genomes (human, mouse and rat). RESULTS: Amino-acid
sequence evolution rates are significantly correlated on different branches of
phylogenetic trees representing the great majority of analyzed orthologous protein
sets from all three domains of life. However, approximately 1% of the proteins
from each group of species deviates from this pattern and instead shows variation
that is consistent with an acceleration of the rate of amino-acid substitution,
which may be due to functional diversification. Most of the putative functionally
diversified proteins from all three species groups are predicted to function at
the periphery of the cells and mediate their interaction with the environment.
CONCLUSIONS: Relative rates of protein evolution are remarkably constant for the
three species groups analyzed here. Deviations from this rate constancy are probably
due to changes in selective constraints associated with diversification between
orthologs. Functional diversification between orthologs is thought to be a relatively
rare event. However, the resolution afforded by the test designed specifically
for genomic-scale datasets allowed us to identify numerous cases of possible functional
diversification between orthologous proteins.'
acknowledgement: We thank Alexey Kondrashov for many helpful discussions and constructive
criticisms, Charles DeLisi, David Landsman, Detlef Leipe, Wojciech Makalowski and
Itai Yanai for critical reading of the manuscript and constructive comments and
L. Aravind for advice on protein function prediction. The release of the unpublished
P. furiosus genome sequence by the Utah Genome Center at the University of Utah
is acknowledged and appreciated.
article_number: research0053.1
article_processing_charge: No
article_type: original
author:
- first_name: Ingo
full_name: Jordan, Ingo
last_name: Jordan
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Igor
full_name: Rogozin, Igor
last_name: Rogozin
- first_name: Roman
full_name: Tatusov, Roman
last_name: Tatusov
- first_name: Yuri
full_name: Wolf, Yuri
last_name: Wolf
- first_name: Eugene
full_name: Koonin, Eugene
last_name: Koonin
citation:
ama: Jordan I, Kondrashov F, Rogozin I, Tatusov R, Wolf Y, Koonin E. Constant relative
rate of protein evolution and detection of functional diversification among bacterial,
archaeal and eukaryotic proteins . Genome Biology. 2001;2(12). doi:10.1186/gb-2001-2-12-research0053
apa: Jordan, I., Kondrashov, F., Rogozin, I., Tatusov, R., Wolf, Y., & Koonin,
E. (2001). Constant relative rate of protein evolution and detection of functional
diversification among bacterial, archaeal and eukaryotic proteins . Genome
Biology. BioMed Central. https://doi.org/10.1186/gb-2001-2-12-research0053
chicago: Jordan, Ingo, Fyodor Kondrashov, Igor Rogozin, Roman Tatusov, Yuri Wolf,
and Eugene Koonin. “Constant Relative Rate of Protein Evolution and Detection
of Functional Diversification among Bacterial, Archaeal and Eukaryotic Proteins
.” Genome Biology. BioMed Central, 2001. https://doi.org/10.1186/gb-2001-2-12-research0053.
ieee: I. Jordan, F. Kondrashov, I. Rogozin, R. Tatusov, Y. Wolf, and E. Koonin,
“Constant relative rate of protein evolution and detection of functional diversification
among bacterial, archaeal and eukaryotic proteins ,” Genome Biology, vol.
2, no. 12. BioMed Central, 2001.
ista: Jordan I, Kondrashov F, Rogozin I, Tatusov R, Wolf Y, Koonin E. 2001. Constant
relative rate of protein evolution and detection of functional diversification
among bacterial, archaeal and eukaryotic proteins . Genome Biology. 2(12), research0053.1.
mla: Jordan, Ingo, et al. “Constant Relative Rate of Protein Evolution and Detection
of Functional Diversification among Bacterial, Archaeal and Eukaryotic Proteins
.” Genome Biology, vol. 2, no. 12, research0053.1, BioMed Central, 2001,
doi:10.1186/gb-2001-2-12-research0053.
short: I. Jordan, F. Kondrashov, I. Rogozin, R. Tatusov, Y. Wolf, E. Koonin, Genome
Biology 2 (2001).
date_created: 2018-12-11T11:49:02Z
date_published: 2001-01-01T00:00:00Z
date_updated: 2023-05-31T12:15:37Z
day: '01'
doi: 10.1186/gb-2001-2-12-research0053
extern: '1'
external_id:
pmid:
- '11790256'
intvolume: ' 2'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC64838/
month: '01'
oa: 1
oa_version: Published Version
pmid: 1
publication: Genome Biology
publication_identifier:
issn:
- 1465-6906
publication_status: published
publisher: BioMed Central
publist_id: '6758'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Constant relative rate of protein evolution and detection of functional diversification
among bacterial, archaeal and eukaryotic proteins '
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '2001'
...
---
_id: '2340'
abstract:
- lang: eng
text: "Recent experimental breakthroughs in the treatment of dilute Bose gases have
renewed interest in their quantum mechanical description, respectively in approximations
to it. The ground state properties of dilute Bose gases confined in external potentials
and interacting via repulsive short range forces are usually described by means
of the Gross-Pitaevskii energy functional. In joint work with Elliott H. Lieb
and Jakob Yngvason its status as an approximation for the quantum mechanical many-body
ground state problem has recently been rigorously clarified. We present a summary
of this work, for both the two-and three-dimensional case.\r\n"
alternative_title:
- 'Operator Theory: Advances and Applications'
article_processing_charge: No
arxiv: 1
author:
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: 'Seiringer R. Bosons in a trap: Asymptotic exactness of the Gross-Pitaevskii
ground state energy formula. In: Demuth M, Schultze B, eds. Vol 126. Birkhäuser;
2001:307-314. doi:10.1007/978-3-0348-8231-6'
apa: 'Seiringer, R. (2001). Bosons in a trap: Asymptotic exactness of the Gross-Pitaevskii
ground state energy formula. In M. Demuth & B. Schultze (Eds.) (Vol. 126,
pp. 307–314). Presented at the PDE: Partial Differential Equations and Spectral
Theory, Clausthal, Germany: Birkhäuser. https://doi.org/10.1007/978-3-0348-8231-6'
chicago: 'Seiringer, Robert. “Bosons in a Trap: Asymptotic Exactness of the Gross-Pitaevskii
Ground State Energy Formula.” edited by Michael Demuth and Bert Schultze, 126:307–14.
Birkhäuser, 2001. https://doi.org/10.1007/978-3-0348-8231-6.'
ieee: 'R. Seiringer, “Bosons in a trap: Asymptotic exactness of the Gross-Pitaevskii
ground state energy formula,” presented at the PDE: Partial Differential Equations
and Spectral Theory, Clausthal, Germany, 2001, vol. 126, pp. 307–314.'
ista: 'Seiringer R. 2001. Bosons in a trap: Asymptotic exactness of the Gross-Pitaevskii
ground state energy formula. PDE: Partial Differential Equations and Spectral
Theory, Operator Theory: Advances and Applications, vol. 126, 307–314.'
mla: 'Seiringer, Robert. Bosons in a Trap: Asymptotic Exactness of the Gross-Pitaevskii
Ground State Energy Formula. Edited by Michael Demuth and Bert Schultze, vol.
126, Birkhäuser, 2001, pp. 307–14, doi:10.1007/978-3-0348-8231-6.'
short: R. Seiringer, in:, M. Demuth, B. Schultze (Eds.), Birkhäuser, 2001, pp. 307–314.
conference:
location: Clausthal, Germany
name: 'PDE: Partial Differential Equations and Spectral Theory'
date_created: 2018-12-11T11:57:05Z
date_published: 2001-01-01T00:00:00Z
date_updated: 2023-05-30T13:20:05Z
day: '01'
doi: 10.1007/978-3-0348-8231-6
editor:
- first_name: Michael
full_name: Demuth, Michael
last_name: Demuth
- first_name: Bert
full_name: Schultze, Bert
last_name: Schultze
extern: '1'
external_id:
arxiv:
- math-ph/0010006
intvolume: ' 126'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/0010006
month: '01'
oa: 1
oa_version: None
page: 307 - 314
publication_identifier:
isbn:
- '9783034894838'
publication_status: published
publisher: Birkhäuser
publist_id: '4586'
quality_controlled: '1'
status: public
title: 'Bosons in a trap: Asymptotic exactness of the Gross-Pitaevskii ground state
energy formula'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 126
year: '2001'
...
---
_id: '2341'
abstract:
- lang: eng
text: We study the ground state properties of an atom with nuclear charge Z and
N bosonic "electrons" in the presence of a homogeneous magnetic field
B. We investigate the mean field limit N→∞ with N / Z fixed, and identify three
different asymptotic regions, according to B≪Z2,B∼Z2,andB≫Z2 . In Region 1 standard
Hartree theory is applicable. Region 3 is described by a one-dimensional functional,
which is identical to the so-called Hyper-Strong functional introduced by Lieb,
Solovej and Yngvason for atoms with fermionic electrons in the region B≫Z3 ; i.e.,
for very strong magnetic fields the ground state properties of atoms are independent
of statistics. For Region 2 we introduce a general magnetic Hartree functional,
which is studied in detail. It is shown that in the special case of an atom it
can be restricted to the subspace of zero angular momentum parallel to the magnetic
field, which simplifies the theory considerably. The functional reproduces the
energy and the one-particle reduced density matrix for the full N-particle ground
state to leading order in N, and it implies the description of the other regions
as limiting cases.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Bernhard
full_name: Baumgartner, Bernhard
last_name: Baumgartner
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Baumgartner B, Seiringer R. Atoms with bosonic "electrons"
in strong magnetic fields. Annales Henri Poincare. 2001;2(1):41-76. doi:10.1007/PL00001032
apa: Baumgartner, B., & Seiringer, R. (2001). Atoms with bosonic "electrons"
in strong magnetic fields. Annales Henri Poincare. Birkhäuser. https://doi.org/10.1007/PL00001032
chicago: Baumgartner, Bernhard, and Robert Seiringer. “Atoms with Bosonic "Electrons"
in Strong Magnetic Fields.” Annales Henri Poincare. Birkhäuser, 2001. https://doi.org/10.1007/PL00001032.
ieee: B. Baumgartner and R. Seiringer, “Atoms with bosonic "electrons"
in strong magnetic fields,” Annales Henri Poincare, vol. 2, no. 1. Birkhäuser,
pp. 41–76, 2001.
ista: Baumgartner B, Seiringer R. 2001. Atoms with bosonic "electrons"
in strong magnetic fields. Annales Henri Poincare. 2(1), 41–76.
mla: Baumgartner, Bernhard, and Robert Seiringer. “Atoms with Bosonic "Electrons"
in Strong Magnetic Fields.” Annales Henri Poincare, vol. 2, no. 1, Birkhäuser,
2001, pp. 41–76, doi:10.1007/PL00001032.
short: B. Baumgartner, R. Seiringer, Annales Henri Poincare 2 (2001) 41–76.
date_created: 2018-12-11T11:57:06Z
date_published: 2001-02-01T00:00:00Z
date_updated: 2023-05-30T12:49:08Z
day: '01'
doi: 10.1007/PL00001032
extern: '1'
external_id:
arxiv:
- math-ph/0007007
intvolume: ' 2'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/0007007
month: '02'
oa: 1
oa_version: None
page: 41 - 76
publication: Annales Henri Poincare
publication_identifier:
issn:
- 1424-0637
publication_status: published
publisher: Birkhäuser
publist_id: '4585'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Atoms with bosonic "electrons" in strong magnetic fields
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '2001'
...
---
_id: '2345'
abstract:
- lang: eng
text: We give upper bounds for the number of spin-1/2 particles that can be bound
to a nucleus of charge Z in the presence of a magnetic field B, including the
spin-field coupling. We use Lieb's strategy, which is known to yield Nc < 2Z
+ 1 for magnetic fields that go to zero at infinity, ignoring the spin-field interaction.
For particles with fermionic statistics in a homogeneous magnetic field our upper
bound has an additional term of the order of Z × min {(B/Z3)2/5, 1 + | 1n(B/Z3)|2}.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: 'Seiringer R. On the maximal ionization of atoms in strong magnetic fields.
Journal of Physics A: Mathematical and General. 2001;34(9):1943-1948. doi:10.1088/0305-4470/34/9/311'
apa: 'Seiringer, R. (2001). On the maximal ionization of atoms in strong magnetic
fields. Journal of Physics A: Mathematical and General. IOP Publishing
Ltd. https://doi.org/10.1088/0305-4470/34/9/311'
chicago: 'Seiringer, Robert. “On the Maximal Ionization of Atoms in Strong Magnetic
Fields.” Journal of Physics A: Mathematical and General. IOP Publishing
Ltd., 2001. https://doi.org/10.1088/0305-4470/34/9/311.'
ieee: 'R. Seiringer, “On the maximal ionization of atoms in strong magnetic fields,”
Journal of Physics A: Mathematical and General, vol. 34, no. 9. IOP Publishing
Ltd., pp. 1943–1948, 2001.'
ista: 'Seiringer R. 2001. On the maximal ionization of atoms in strong magnetic
fields. Journal of Physics A: Mathematical and General. 34(9), 1943–1948.'
mla: 'Seiringer, Robert. “On the Maximal Ionization of Atoms in Strong Magnetic
Fields.” Journal of Physics A: Mathematical and General, vol. 34, no. 9,
IOP Publishing Ltd., 2001, pp. 1943–48, doi:10.1088/0305-4470/34/9/311.'
short: 'R. Seiringer, Journal of Physics A: Mathematical and General 34 (2001) 1943–1948.'
date_created: 2018-12-11T11:57:07Z
date_published: 2001-03-09T00:00:00Z
date_updated: 2023-05-30T12:37:44Z
day: '09'
doi: 10.1088/0305-4470/34/9/311
extern: '1'
external_id:
arxiv:
- math-ph/0006002
intvolume: ' 34'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/0006002
month: '03'
oa: 1
oa_version: None
page: 1943 - 1948
publication: 'Journal of Physics A: Mathematical and General'
publication_identifier:
issn:
- 0305-4470
publication_status: published
publisher: IOP Publishing Ltd.
publist_id: '4580'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the maximal ionization of atoms in strong magnetic fields
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 34
year: '2001'
...
---
_id: '2346'
abstract:
- lang: eng
text: By means of a generalization of the Fefferman - de la Llave decomposition
we derive a general lower bound on the interaction energy of one-dimensional quantum
systems. We apply this result to a specific class of lowest Landau band wave functions.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Christian
full_name: Hainzl, Christian
last_name: Hainzl
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Hainzl C, Seiringer R. Bounds on one-dimensional exchange energies with application
to lowest Landau band quantum mechanics. Letters in Mathematical Physics.
2001;55(2):133-142. doi:10.1023/A:1010951905548
apa: Hainzl, C., & Seiringer, R. (2001). Bounds on one-dimensional exchange
energies with application to lowest Landau band quantum mechanics. Letters
in Mathematical Physics. Springer. https://doi.org/10.1023/A:1010951905548
chicago: Hainzl, Christian, and Robert Seiringer. “Bounds on One-Dimensional Exchange
Energies with Application to Lowest Landau Band Quantum Mechanics.” Letters
in Mathematical Physics. Springer, 2001. https://doi.org/10.1023/A:1010951905548.
ieee: C. Hainzl and R. Seiringer, “Bounds on one-dimensional exchange energies with
application to lowest Landau band quantum mechanics,” Letters in Mathematical
Physics, vol. 55, no. 2. Springer, pp. 133–142, 2001.
ista: Hainzl C, Seiringer R. 2001. Bounds on one-dimensional exchange energies with
application to lowest Landau band quantum mechanics. Letters in Mathematical Physics.
55(2), 133–142.
mla: Hainzl, Christian, and Robert Seiringer. “Bounds on One-Dimensional Exchange
Energies with Application to Lowest Landau Band Quantum Mechanics.” Letters
in Mathematical Physics, vol. 55, no. 2, Springer, 2001, pp. 133–42, doi:10.1023/A:1010951905548.
short: C. Hainzl, R. Seiringer, Letters in Mathematical Physics 55 (2001) 133–142.
date_created: 2018-12-11T11:57:07Z
date_published: 2001-02-01T00:00:00Z
date_updated: 2023-05-30T12:44:05Z
day: '01'
doi: 10.1023/A:1010951905548
extern: '1'
external_id:
arxiv:
- cond-mat/0102118
intvolume: ' 55'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/cond-mat/0102118
month: '02'
oa: 1
oa_version: Published Version
page: 133 - 142
publication: Letters in Mathematical Physics
publication_identifier:
issn:
- 0377-9017
publication_status: published
publisher: Springer
publist_id: '4581'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounds on one-dimensional exchange energies with application to lowest Landau
band quantum mechanics
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 55
year: '2001'
...
---
_id: '2347'
abstract:
- lang: eng
text: We consider the ground state properties of an inhomogeneous two-dimensional
Bose gas with a repulsive, short range pair interaction and an external confining
potential. In the limit when the particle number N is large but ρ̅a 2 is small,
where ρ̅ is the average particle density and a the scattering length, the ground
state energy and density are rigorously shown to be given to leading order by
a Gross–Pitaevskii (GP) energy functional with a coupling constant g~1/|1n(ρ̅a
2)|. In contrast to the 3D case the coupling constant depends on N through the
mean density. The GP energy per particle depends only on Ng. In 2D this parameter
is typically so large that the gradient term in the GP energy functional is negligible
and the simpler description by a Thomas–Fermi type functional is adequate.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Élliott
full_name: Lieb, Élliott
last_name: Lieb
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
- first_name: Jakob
full_name: Yngvason, Jakob
last_name: Yngvason
citation:
ama: Lieb É, Seiringer R, Yngvason J. A rigorous derivation of the Gross-Pitaevskii
energy functional for a two-dimensional Bose gas. Communications in Mathematical
Physics. 2001;224(1):17-31. doi:10.1007/s002200100533
apa: Lieb, É., Seiringer, R., & Yngvason, J. (2001). A rigorous derivation of
the Gross-Pitaevskii energy functional for a two-dimensional Bose gas. Communications
in Mathematical Physics. Springer. https://doi.org/10.1007/s002200100533
chicago: Lieb, Élliott, Robert Seiringer, and Jakob Yngvason. “A Rigorous Derivation
of the Gross-Pitaevskii Energy Functional for a Two-Dimensional Bose Gas.” Communications
in Mathematical Physics. Springer, 2001. https://doi.org/10.1007/s002200100533.
ieee: É. Lieb, R. Seiringer, and J. Yngvason, “A rigorous derivation of the Gross-Pitaevskii
energy functional for a two-dimensional Bose gas,” Communications in Mathematical
Physics, vol. 224, no. 1. Springer, pp. 17–31, 2001.
ista: Lieb É, Seiringer R, Yngvason J. 2001. A rigorous derivation of the Gross-Pitaevskii
energy functional for a two-dimensional Bose gas. Communications in Mathematical
Physics. 224(1), 17–31.
mla: Lieb, Élliott, et al. “A Rigorous Derivation of the Gross-Pitaevskii Energy
Functional for a Two-Dimensional Bose Gas.” Communications in Mathematical
Physics, vol. 224, no. 1, Springer, 2001, pp. 17–31, doi:10.1007/s002200100533.
short: É. Lieb, R. Seiringer, J. Yngvason, Communications in Mathematical Physics
224 (2001) 17–31.
date_created: 2018-12-11T11:57:08Z
date_published: 2001-11-01T00:00:00Z
date_updated: 2023-05-30T12:28:46Z
day: '01'
doi: 10.1007/s002200100533
extern: '1'
external_id:
arxiv:
- cond-mat/0005026
intvolume: ' 224'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/cond-mat/0005026
month: '11'
oa: 1
oa_version: Published Version
page: 17 - 31
publication: Communications in Mathematical Physics
publication_identifier:
issn:
- 0010-3616
publication_status: published
publisher: Springer
publist_id: '4579'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A rigorous derivation of the Gross-Pitaevskii energy functional for a two-dimensional
Bose gas
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 224
year: '2001'
...
---
_id: '2348'
abstract:
- lang: eng
text: This paper concerns the asymptotic ground state properties of heavy atoms
in strong, homogeneous magnetic fields. In the limit when the nuclear charge Z
tends to ∞ with the magnetic field B satisfying B ≫ Z4/3 all the electrons are
confined to the lowest Landau band. We consider here an energy functional, whose
variable is a sequence of one-dimensional density matrices corresponding to different
angular momentum functions in the lowest Landau band. We study this functional
in detail and derive various interesting properties, which are compared with the
density matrix (DM) theory introduced by Lieb, Solovej and Yngvason. In contrast
to the DM theory the variable perpendicular to the field is replaced by the discrete
angular momentum quantum numbers. Hence we call the new functional a discrete
density matrix (DDM) functional. We relate this DDM theory to the lowest Landau
band quantum mechanics and show that it reproduces correctly the ground state
energy apart from errors due to the indirect part of the Coulomb interaction energy.
acknowledgement: The authors would like to thank Bernhard Baumgartner and Jakob Yngvason
for proofreading and valuable comments.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Christian
full_name: Hainzl, Christian
last_name: Hainzl
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Hainzl C, Seiringer R. A discrete density matrix theory for atoms in strong
magnetic fields. Communications in Mathematical Physics. 2001;217(1):229-248.
doi:10.1007/s002200100373
apa: Hainzl, C., & Seiringer, R. (2001). A discrete density matrix theory for
atoms in strong magnetic fields. Communications in Mathematical Physics.
Springer. https://doi.org/10.1007/s002200100373
chicago: Hainzl, Christian, and Robert Seiringer. “A Discrete Density Matrix Theory
for Atoms in Strong Magnetic Fields.” Communications in Mathematical Physics.
Springer, 2001. https://doi.org/10.1007/s002200100373.
ieee: C. Hainzl and R. Seiringer, “A discrete density matrix theory for atoms in
strong magnetic fields,” Communications in Mathematical Physics, vol. 217,
no. 1. Springer, pp. 229–248, 2001.
ista: Hainzl C, Seiringer R. 2001. A discrete density matrix theory for atoms in
strong magnetic fields. Communications in Mathematical Physics. 217(1), 229–248.
mla: Hainzl, Christian, and Robert Seiringer. “A Discrete Density Matrix Theory
for Atoms in Strong Magnetic Fields.” Communications in Mathematical Physics,
vol. 217, no. 1, Springer, 2001, pp. 229–48, doi:10.1007/s002200100373.
short: C. Hainzl, R. Seiringer, Communications in Mathematical Physics 217 (2001)
229–248.
date_created: 2018-12-11T11:57:08Z
date_published: 2001-02-01T00:00:00Z
date_updated: 2023-05-30T06:54:54Z
day: '01'
doi: 10.1007/s002200100373
extern: '1'
external_id:
arxiv:
- math-ph/0010005
intvolume: ' 217'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/0010005
month: '02'
oa: 1
oa_version: Preprint
page: 229 - 248
publication: Communications in Mathematical Physics
publication_identifier:
issn:
- 0010-3616
publication_status: published
publisher: Springer
publist_id: '4578'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A discrete density matrix theory for atoms in strong magnetic fields
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2001'
...
---
_id: '2419'
abstract:
- lang: eng
text: For an absolutely continuous probability measure μ. on ℝd and a nonnegative
integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d
+ 1 random points which are i.i.d. according to μ contains the origin 0. For d
and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize
the measures in ℝd which attain this bound. As we will see, this result can be
considered a continuous analogue of the Upper Bound Theorem for the maximal number
of faces of convex polytopes with a given number of vertices. For our proof we
introduce so-called h-functions, continuous counterparts of h-vectors of simplicial
convex polytopes.
acknowledgement: We are indebted to Rolf Schneider for many helpful remarks and in
particular for bringing reference [6] to our attention
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Wagner U, Welzl E. A continuous analogue of the Upper Bound Theorem. Discrete
& Computational Geometry. 2001;26(2):205-219. doi:10.1007/s00454-001-0028-9
apa: Wagner, U., & Welzl, E. (2001). A continuous analogue of the Upper Bound
Theorem. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-001-0028-9
chicago: Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.”
Discrete & Computational Geometry. Springer, 2001. https://doi.org/10.1007/s00454-001-0028-9.
ieee: U. Wagner and E. Welzl, “A continuous analogue of the Upper Bound Theorem,”
Discrete & Computational Geometry, vol. 26, no. 2. Springer, pp. 205–219,
2001.
ista: Wagner U, Welzl E. 2001. A continuous analogue of the Upper Bound Theorem.
Discrete & Computational Geometry. 26(2), 205–219.
mla: Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.”
Discrete & Computational Geometry, vol. 26, no. 2, Springer, 2001,
pp. 205–19, doi:10.1007/s00454-001-0028-9.
short: U. Wagner, E. Welzl, Discrete & Computational Geometry 26 (2001) 205–219.
date_created: 2018-12-11T11:57:33Z
date_published: 2001-01-01T00:00:00Z
date_updated: 2023-05-24T13:13:51Z
day: '01'
doi: 10.1007/s00454-001-0028-9
extern: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 205 - 219
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '4506'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A continuous analogue of the Upper Bound Theorem
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 26
year: '2001'
...
---
_id: '4564'
abstract:
- lang: eng
text: This paper presents a concept for integrating the embedded programming methodology
Giotto and the object-oriented AOCS Framework to create an environment for the
rapid development of distributed software for safety-critical embedded control
systems with hard real-time requirements of the kind typically found in aerospace
applications.
acknowledgement: 'This research was supported in part by DARPA under grants F336 15-C-98-36
14, F33615-00-(2-1693, and F33615-00-C-1703, and by MARC0 under grant 98-DT-660. '
article_processing_charge: No
author:
- first_name: Timothy
full_name: Brown, Timothy
last_name: Brown
- first_name: Alessandro
full_name: Pasetti, Alessandro
last_name: Pasetti
- first_name: Wolfgang
full_name: Pree, Wolfgang
last_name: Pree
- 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: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
citation:
ama: 'Brown T, Pasetti A, Pree W, Henzinger TA, Kirsch C. A reusable and platform-independent
framework for distributed control systems. In: Proceedings of the 20th Digital
Avionics Systems Conference. IEEE; 2001:1-11. doi:10.1109/DASC.2001.964169'
apa: 'Brown, T., Pasetti, A., Pree, W., Henzinger, T. A., & Kirsch, C. (2001).
A reusable and platform-independent framework for distributed control systems.
In Proceedings of the 20th Digital Avionics Systems Conference (pp. 1–11).
Daytona Beach, FL, USA: IEEE. https://doi.org/10.1109/DASC.2001.964169'
chicago: Brown, Timothy, Alessandro Pasetti, Wolfgang Pree, Thomas A Henzinger,
and Christoph Kirsch. “A Reusable and Platform-Independent Framework for Distributed
Control Systems.” In Proceedings of the 20th Digital Avionics Systems Conference,
1–11. IEEE, 2001. https://doi.org/10.1109/DASC.2001.964169.
ieee: T. Brown, A. Pasetti, W. Pree, T. A. Henzinger, and C. Kirsch, “A reusable
and platform-independent framework for distributed control systems,” in Proceedings
of the 20th Digital Avionics Systems Conference, Daytona Beach, FL, USA, 2001,
pp. 1–11.
ista: 'Brown T, Pasetti A, Pree W, Henzinger TA, Kirsch C. 2001. A reusable and
platform-independent framework for distributed control systems. Proceedings of
the 20th Digital Avionics Systems Conference. DASC: Digital Avionics Systems Conference,
1–11.'
mla: Brown, Timothy, et al. “A Reusable and Platform-Independent Framework for Distributed
Control Systems.” Proceedings of the 20th Digital Avionics Systems Conference,
IEEE, 2001, pp. 1–11, doi:10.1109/DASC.2001.964169.
short: T. Brown, A. Pasetti, W. Pree, T.A. Henzinger, C. Kirsch, in:, Proceedings
of the 20th Digital Avionics Systems Conference, IEEE, 2001, pp. 1–11.
conference:
end_date: 2001-10-18
location: Daytona Beach, FL, USA
name: 'DASC: Digital Avionics Systems Conference'
start_date: 2001-10-14
date_created: 2018-12-11T12:09:30Z
date_published: 2001-08-06T00:00:00Z
date_updated: 2023-05-09T12:23:16Z
day: '06'
doi: 10.1109/DASC.2001.964169
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 1 - 11
publication: Proceedings of the 20th Digital Avionics Systems Conference
publication_identifier:
isbn:
- '0780370341'
publication_status: published
publisher: IEEE
publist_id: '143'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A reusable and platform-independent framework for distributed control systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4599'
abstract:
- lang: eng
text: 'State-space explosion is a fundamental obstacle in the formal verification
of designs and protocols. Several techniques for combating this problem have emerged
in the past few years, among which two are significant: partial-order reduction
and symbolic state-space search. In asynchronous systems, interleavings of independent
concurrent events are equivalent, and only a representative interleaving needs
to be explored to verify local properties. Partial-order methods exploit this
redundancy and visit only a subset of the reachable states. Symbolic techniques,
on the other hand, capture the transition relation of a system and the set of
reachable states as boolean functions. In many cases, these functions can be represented
compactly using binary decision diagrams (BDDs). Traditionally, the two techniques
have been practiced by two different schools—partial-order methods with enumerative
depth-first search for the analysis of asynchronous network protocols, and symbolic
breadth-first search for the analysis of synchronous hardware designs. We combine
both approaches and develop a method for using partial-order reduction techniques
in symbolic BDD-based invariant checking. We present theoretical results to prove
the correctness of the method, and experimental results to demonstrate its efficacy.'
acknowledgement: Gerard Holzmann provided us with information on SPIN. Ken McMillan
and Doron Peled contributed through discussions. The VIS group at UC Berkeley and
Rajeev Ranjan in particular helped with the experiments.
article_processing_charge: No
article_type: original
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Robert
full_name: Brayton, Robert
last_name: Brayton
- 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: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
- first_name: Sriram
full_name: Rajamani, Sriram
last_name: Rajamani
citation:
ama: Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. Partial-order reduction
in symbolic state-space exploration. Formal Methods in System Design. 2001;18(2):97-116.
doi:10.1023/A:1008767206905
apa: Alur, R., Brayton, R., Henzinger, T. A., Qadeer, S., & Rajamani, S. (2001).
Partial-order reduction in symbolic state-space exploration. Formal Methods
in System Design. Springer. https://doi.org/10.1023/A:1008767206905
chicago: Alur, Rajeev, Robert Brayton, Thomas A Henzinger, Shaz Qadeer, and Sriram
Rajamani. “Partial-Order Reduction in Symbolic State-Space Exploration.” Formal
Methods in System Design. Springer, 2001. https://doi.org/10.1023/A:1008767206905.
ieee: R. Alur, R. Brayton, T. A. Henzinger, S. Qadeer, and S. Rajamani, “Partial-order
reduction in symbolic state-space exploration,” Formal Methods in System Design,
vol. 18, no. 2. Springer, pp. 97–116, 2001.
ista: Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. 2001. Partial-order
reduction in symbolic state-space exploration. Formal Methods in System Design.
18(2), 97–116.
mla: Alur, Rajeev, et al. “Partial-Order Reduction in Symbolic State-Space Exploration.”
Formal Methods in System Design, vol. 18, no. 2, Springer, 2001, pp. 97–116,
doi:10.1023/A:1008767206905.
short: R. Alur, R. Brayton, T.A. Henzinger, S. Qadeer, S. Rajamani, Formal Methods
in System Design 18 (2001) 97–116.
date_created: 2018-12-11T12:09:41Z
date_published: 2001-03-01T00:00:00Z
date_updated: 2023-05-08T12:22:38Z
day: '01'
doi: 10.1023/A:1008767206905
extern: '1'
intvolume: ' 18'
issue: '2'
language:
- iso: eng
month: '03'
oa_version: None
page: 97 - 116
publication: Formal Methods in System Design
publication_identifier:
issn:
- 0925-9856
publication_status: published
publisher: Springer
publist_id: '108'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Partial-order reduction in symbolic state-space exploration
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '2001'
...
---
_id: '4600'
abstract:
- lang: eng
text: 'Model checking is a practical tool for automated debugging of embedded software.
In model checking, a high-level description of a system is compared against a
logical correctness requirement to discover inconsistencies. Since model checking
is based on exhaustive state-space exploration and the size of the state space
of a design grows exponentially with the size of the description, scalability
remains a challenge. We have thus developed techniques for exploiting modular
design structure during model checking, and the model checker jMocha (Java MOdel-CHecking
Algorithm) is based on this theme. Instead of manipulating unstructured state-transition
graphs, it supports the hierarchical modeling framework of reactive modules. jMocha
is a growing interactive software environment for specification, simulation and
verification, and is intended as a vehicle for the development of new verification
algorithms and approaches. It is written in Java and uses native C-code BDD libraries
from VIS. jMocha offers: (1) a GUI that looks familiar to Windows/Java users;
(2) a simulator that displays traces in a message sequence chart fashion; (3)
requirements verification both by symbolic and enumerative model checking; (4)
implementation verification by checking trace containment; (5) a proof manager
that aids compositional and assume-guarantee reasoning; and (6) SLANG (Scripting
LANGuage) for the rapid and structured development of new verification algorithms.
jMocha is available publicly at ; it is a successor and extension of the original
Mocha tool that was entirely written in C.'
acknowledgement: 'We thank Himyanshu Anand, Ben Horowitz, Franjo Ivancic, Michael
McDougall, Marius Minea, Oliver Moeller. Shaz Qadeer, Sriram Rajamani, and Jean-Francois
Raskin for their assistance in the development of JMOCHA. The MOCHA project is funded
in part by the DARPA grant NAG2-1214, the NSF CAREER awards CCR95-01708 and CCR97-34115,
the NSF grant CCR99-70925, the NSF ITR grant CCR0085949, the MARC0 grant 98-DT-660,
and the SRC contracts 99-TJ-683.003 and 99-TJ-688. '
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Radu
full_name: Grosu, Radu
last_name: Grosu
- 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: Myong
full_name: Kang, Myong
last_name: Kang
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Freddy
full_name: Mang, Freddy
last_name: Mang
- first_name: Bow
full_name: Wang, Bow
last_name: Wang
citation:
ama: 'Alur R, De Alfaro L, Grosu R, et al. jMocha: A model-checking tool that exploits
design structure. In: Proceedings of the 23rd International Conference on Software
Engineering. IEEE; 2001:835-836. doi:10.1109/ICSE.2001.919196'
apa: 'Alur, R., De Alfaro, L., Grosu, R., Henzinger, T. A., Kang, M., Kirsch, C.,
… Wang, B. (2001). jMocha: A model-checking tool that exploits design structure.
In Proceedings of the 23rd International Conference on Software Engineering
(pp. 835–836). IEEE. https://doi.org/10.1109/ICSE.2001.919196'
chicago: 'Alur, Rajeev, Luca De Alfaro, Radu Grosu, Thomas A Henzinger, Myong Kang,
Christoph Kirsch, Ritankar Majumdar, Freddy Mang, and Bow Wang. “JMocha: A Model-Checking
Tool That Exploits Design Structure.” In Proceedings of the 23rd International
Conference on Software Engineering, 835–36. IEEE, 2001. https://doi.org/10.1109/ICSE.2001.919196.'
ieee: 'R. Alur et al., “jMocha: A model-checking tool that exploits design
structure,” in Proceedings of the 23rd International Conference on Software
Engineering, 2001, pp. 835–836.'
ista: 'Alur R, De Alfaro L, Grosu R, Henzinger TA, Kang M, Kirsch C, Majumdar R,
Mang F, Wang B. 2001. jMocha: A model-checking tool that exploits design structure.
Proceedings of the 23rd International Conference on Software Engineering. ICSE:
Software Engineering, 835–836.'
mla: 'Alur, Rajeev, et al. “JMocha: A Model-Checking Tool That Exploits Design Structure.”
Proceedings of the 23rd International Conference on Software Engineering,
IEEE, 2001, pp. 835–36, doi:10.1109/ICSE.2001.919196.'
short: R. Alur, L. De Alfaro, R. Grosu, T.A. Henzinger, M. Kang, C. Kirsch, R. Majumdar,
F. Mang, B. Wang, in:, Proceedings of the 23rd International Conference on Software
Engineering, IEEE, 2001, pp. 835–836.
conference:
name: 'ICSE: Software Engineering'
date_created: 2018-12-11T12:09:41Z
date_published: 2001-08-07T00:00:00Z
date_updated: 2023-05-08T14:06:55Z
day: '07'
doi: 10.1109/ICSE.2001.919196
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 835 - 836
publication: Proceedings of the 23rd International Conference on Software Engineering
publication_identifier:
isbn:
- '0769510507'
publication_status: published
publisher: IEEE
publist_id: '109'
quality_controlled: '1'
status: public
title: 'jMocha: A model-checking tool that exploits design structure'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4622'
abstract:
- lang: eng
text: Conventional type systems specify interfaces in terms of values and domains.
We present a light-weight formalism that captures the temporal aspects of software
component interfaces. Specifically, we use an automata-based language to capture
both input assumptions about the order in which the methods of a component are
called, and output guarantees about the order in which the component calls external
methods. The formalism supports automatic compatability checks between interface
models, and thus constitutes a type system for component interaction. Unlike traditional
uses of automata, our formalism is based on an optimistic approach to composition,
and on an alternating approach to design refinement. According to the optimistic
approach, two components are compatible if there is some environment that can
make them work together. According to the alternating approach, one interface
refines another if it has weaker input assumptions, and stronger output guarantees.
We show that these notions have game-theoretic foundations that lead to efficient
algorithms for checking compatibility and refinement.
acknowledgement: We thank Edward A. Lee, Xiaojun Liu, Freddy Mang, and Yuhong Xiong
for fruitful discussions. This research was supported in part by the AFOSR MURI
grant F49620-00-1-0327, the DARPA MoBIES grant F33615-00-C-1703, the MARCO GSRC
grant 98-DT-660, the NSF Theory grant CCR-9988172, and the NSF ITR grant CCR-0085949.
article_processing_charge: No
author:
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'De Alfaro L, Henzinger TA. Interface automata. In: Proceedings of the 8th
European Software Engineering Conference. ACM; 2001:109-120. doi:10.1145/503209.503226'
apa: 'De Alfaro, L., & Henzinger, T. A. (2001). Interface automata. In Proceedings
of the 8th European software engineering conference (pp. 109–120). Vienna,
Austria: ACM. https://doi.org/10.1145/503209.503226'
chicago: De Alfaro, Luca, and Thomas A Henzinger. “Interface Automata.” In Proceedings
of the 8th European Software Engineering Conference, 109–20. ACM, 2001. https://doi.org/10.1145/503209.503226.
ieee: L. De Alfaro and T. A. Henzinger, “Interface automata,” in Proceedings
of the 8th European software engineering conference, Vienna, Austria, 2001,
pp. 109–120.
ista: 'De Alfaro L, Henzinger TA. 2001. Interface automata. Proceedings of the 8th
European software engineering conference. FSE: Foundations of Software Engineering,
109–120.'
mla: De Alfaro, Luca, and Thomas A. Henzinger. “Interface Automata.” Proceedings
of the 8th European Software Engineering Conference, ACM, 2001, pp. 109–20,
doi:10.1145/503209.503226.
short: L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 8th European Software
Engineering Conference, ACM, 2001, pp. 109–120.
conference:
end_date: 2001-09-14
location: Vienna, Austria
name: 'FSE: Foundations of Software Engineering'
start_date: 2001-09-10
date_created: 2018-12-11T12:09:48Z
date_published: 2001-06-01T00:00:00Z
date_updated: 2023-05-08T12:01:02Z
day: '01'
doi: 10.1145/503209.503226
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 109 - 120
publication: Proceedings of the 8th European software engineering conference
publication_identifier:
isbn:
- '9781581133905'
publication_status: published
publisher: ACM
publist_id: '83'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Interface automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4623'
abstract:
- lang: eng
text: We classify component-based models of computation into component models and
interface models. A component model specifies for each component howthe component
behaves in an arbitrary environment; an interface model specifies for each component
what the component expects from the environment. Component models support compositional
abstraction, and therefore component-based verification. Interface models support
compositional refinement, and therefore componentbased design. Many aspects of
interface models, such as compatibility and refinement checking between interfaces,
are properly viewed in a gametheoretic setting, where the input and output values
of an interface are chosen by different players.
acknowledgement: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327,
the DARPA ITO grant F33615-00-C-1693, the MARCO grant 98-DT-660, and the NSF ITR
grant CCR-0085949.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'De Alfaro L, Henzinger TA. Interface theories for component-based design.
In: Proceedings of the 1st International Workshop on Embedded Software.
Vol 2211. ACM; 2001:148-165. doi:10.1007/3-540-45449-7_11'
apa: 'De Alfaro, L., & Henzinger, T. A. (2001). Interface theories for component-based
design. In Proceedings of the 1st International Workshop on Embedded Software
(Vol. 2211, pp. 148–165). Tahoe City, CA, USA: ACM. https://doi.org/10.1007/3-540-45449-7_11'
chicago: De Alfaro, Luca, and Thomas A Henzinger. “Interface Theories for Component-Based
Design.” In Proceedings of the 1st International Workshop on Embedded Software,
2211:148–65. ACM, 2001. https://doi.org/10.1007/3-540-45449-7_11.
ieee: L. De Alfaro and T. A. Henzinger, “Interface theories for component-based
design,” in Proceedings of the 1st International Workshop on Embedded Software,
Tahoe City, CA, USA, 2001, vol. 2211, pp. 148–165.
ista: 'De Alfaro L, Henzinger TA. 2001. Interface theories for component-based design.
Proceedings of the 1st International Workshop on Embedded Software. EMSOFT: Embedded
Software , LNCS, vol. 2211, 148–165.'
mla: De Alfaro, Luca, and Thomas A. Henzinger. “Interface Theories for Component-Based
Design.” Proceedings of the 1st International Workshop on Embedded Software,
vol. 2211, ACM, 2001, pp. 148–65, doi:10.1007/3-540-45449-7_11.
short: L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 1st International Workshop
on Embedded Software, ACM, 2001, pp. 148–165.
conference:
end_date: 2001-10-10
location: Tahoe City, CA, USA
name: 'EMSOFT: Embedded Software '
start_date: 2001-10-08
date_created: 2018-12-11T12:09:48Z
date_published: 2001-09-26T00:00:00Z
date_updated: 2023-05-08T12:11:20Z
day: '26'
doi: 10.1007/3-540-45449-7_11
extern: '1'
intvolume: ' 2211'
language:
- iso: eng
month: '09'
oa_version: None
page: 148 - 165
publication: Proceedings of the 1st International Workshop on Embedded Software
publication_identifier:
isbn:
- '9783540426738'
publication_status: published
publisher: ACM
publist_id: '84'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Interface theories for component-based design
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2211
year: '2001'
...
---
_id: '4632'
abstract:
- lang: eng
text: We present a compositional trace-based model for probabilistic systems. The
behavior of a system with probabilistic choice is a stochastic process, namely,
a probability distribution on traces, or “bundle.” Consequently, the semantics
of a system with both nondeterministic and probabilistic choice is a set of bundles.
The bundles of a composite system can be obtained by combining the bundles of
the components in a simple mathematical way. Refinement between systems is bundle
containment. We achieve assume-guarantee compositionality for bundle semantics
by introducing two scoping mechanisms. The first mechanism, which is standard
in compositional modeling, distinguishes inputs from outputs and hidden state.
The second mechanism, which arises in probabilistic systems, partitions the state
into probabilistically independent regions.
acknowledgement: This research was supported in part by the SRC contract 99-TJ-683.003,
the AFOSR MURI grant F49620-00-1-0327, the MARCO GSRC grant 98-DT-660, the NSF Theory
grant CCR-9988172, and the DARPA SEC grant F33615-C-98-3614.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- 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: Ranjit
full_name: Jhala, Ranjit
last_name: Jhala
citation:
ama: 'De Alfaro L, Henzinger TA, Jhala R. Compositional methods for probabilistic
systems. In: Proceedings of the 12th International Conference on on Concurrency
Theory. Vol 2154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2001:351-365.
doi:10.1007/3-540-44685-0_24'
apa: 'De Alfaro, L., Henzinger, T. A., & Jhala, R. (2001). Compositional methods
for probabilistic systems. In Proceedings of the 12th International Conference
on on Concurrency Theory (Vol. 2154, pp. 351–365). Aalborg, Denmark: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44685-0_24'
chicago: De Alfaro, Luca, Thomas A Henzinger, and Ranjit Jhala. “Compositional Methods
for Probabilistic Systems.” In Proceedings of the 12th International Conference
on on Concurrency Theory, 2154:351–65. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2001. https://doi.org/10.1007/3-540-44685-0_24.
ieee: L. De Alfaro, T. A. Henzinger, and R. Jhala, “Compositional methods for probabilistic
systems,” in Proceedings of the 12th International Conference on on Concurrency
Theory, Aalborg, Denmark, 2001, vol. 2154, pp. 351–365.
ista: 'De Alfaro L, Henzinger TA, Jhala R. 2001. Compositional methods for probabilistic
systems. Proceedings of the 12th International Conference on on Concurrency Theory.
CONCUR: Concurrency Theory, LNCS, vol. 2154, 351–365.'
mla: De Alfaro, Luca, et al. “Compositional Methods for Probabilistic Systems.”
Proceedings of the 12th International Conference on on Concurrency Theory,
vol. 2154, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001, pp. 351–65,
doi:10.1007/3-540-44685-0_24.
short: L. De Alfaro, T.A. Henzinger, R. Jhala, in:, Proceedings of the 12th International
Conference on on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2001, pp. 351–365.
conference:
end_date: 2001-08-25
location: Aalborg, Denmark
name: 'CONCUR: Concurrency Theory'
start_date: 2001-08-20
date_created: 2018-12-11T12:09:51Z
date_published: 2001-08-13T00:00:00Z
date_updated: 2023-05-08T10:24:59Z
day: '13'
doi: 10.1007/3-540-44685-0_24
extern: '1'
intvolume: ' 2154'
language:
- iso: eng
month: '08'
oa_version: None
page: 351 - 365
publication: Proceedings of the 12th International Conference on on Concurrency Theory
publication_identifier:
isbn:
- '9783540424970'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '75'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Compositional methods for probabilistic systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2154
year: '2001'
...
---
_id: '4633'
abstract:
- lang: eng
text: "A procedure for the analysis of state spaces is called symbolic if it manipulates
not individual states, but sets of states that are represented by constraints.
Such a procedure can be used for the analysis of infinite state spaces, provided
termination is guaranteed. We present symbolic procedures, and corresponding termination
criteria, for the solution of infinite-state games, which occur in the control
and modular verification of infinite-state systems. To characterize the termination
of symbolic procedures for solving infinite-state games, we classify these game
structures into four increasingly restrictive categories:\r\n1 \tClass 1 consists
of infinite-state structures for which all safety and reachability games can be
solved.\r\n2 \tClass 2 consists of infinite-state structures for which all ω-regular
games can be solved.\r\n3 \tClass 3 consists of infinite-state structures for
which all nested positive boolean combinations of ω-regular games can be solved.\r\n4
\ \tClass 4 consists of infinite-state structures for which all nested boolean
combinations of ω-regular games can be solved.\r\nWe give a structural characterization
for each class, using equivalence relations on the state spaces of games which
range from game versions of trace equivalence to a game version of bisimilarity.
We provide infinite-state examples for all four classes of games from control
problems for hybrid systems. We conclude by presenting symbolic algorithms for
the synthesis of winning strategies (“controller synthesis”) for infinitestate
games with arbitrary ω-regular objectives, and prove termination over all class-2
structures. This settles, in particular, the symbolic controller synthesis problem
for rectangular hybrid systems."
acknowledgement: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327,
the DARPA SEC grant F33615-C-98-3614, the MARCO GSRC grant 98-DT-660, the NSF Theory
grant CCR-9988172, and the NSF ITR grant CCR-0085949.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- 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: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: 'De Alfaro L, Henzinger TA, Majumdar R. Symbolic algorithms for infinite-state
games. In: Proceedings of the 12th International Conference on on Concurrency
Theory. Vol 2154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2001:536-550.
doi:10.1007/3-540-44685-0_36'
apa: 'De Alfaro, L., Henzinger, T. A., & Majumdar, R. (2001). Symbolic algorithms
for infinite-state games. In Proceedings of the 12th International Conference
on on Concurrency Theory (Vol. 2154, pp. 536–550). Aalborg, Denmark: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44685-0_36'
chicago: De Alfaro, Luca, Thomas A Henzinger, and Ritankar Majumdar. “Symbolic Algorithms
for Infinite-State Games.” In Proceedings of the 12th International Conference
on on Concurrency Theory, 2154:536–50. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2001. https://doi.org/10.1007/3-540-44685-0_36.
ieee: L. De Alfaro, T. A. Henzinger, and R. Majumdar, “Symbolic algorithms for infinite-state
games,” in Proceedings of the 12th International Conference on on Concurrency
Theory, Aalborg, Denmark, 2001, vol. 2154, pp. 536–550.
ista: 'De Alfaro L, Henzinger TA, Majumdar R. 2001. Symbolic algorithms for infinite-state
games. Proceedings of the 12th International Conference on on Concurrency Theory.
CONCUR: Concurrency Theory, LNCS, vol. 2154, 536–550.'
mla: De Alfaro, Luca, et al. “Symbolic Algorithms for Infinite-State Games.” Proceedings
of the 12th International Conference on on Concurrency Theory, vol. 2154,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2001, pp. 536–50, doi:10.1007/3-540-44685-0_36.
short: L. De Alfaro, T.A. Henzinger, R. Majumdar, in:, Proceedings of the 12th International
Conference on on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2001, pp. 536–550.
conference:
end_date: 2001-08-25
location: Aalborg, Denmark
name: 'CONCUR: Concurrency Theory'
start_date: 2001-08-20
date_created: 2018-12-11T12:09:52Z
date_published: 2001-08-13T00:00:00Z
date_updated: 2023-05-08T09:57:31Z
day: '13'
doi: 10.1007/3-540-44685-0_36
extern: '1'
intvolume: ' 2154'
language:
- iso: eng
month: '08'
oa_version: None
page: 536 - 550
publication: Proceedings of the 12th International Conference on on Concurrency Theory
publication_identifier:
isbn:
- '9783540424970'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '73'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Symbolic algorithms for infinite-state games
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2154
year: '2001'
...