---
_id: '11685'
abstract:
- lang: eng
text: We consider the problem of sampling URLs uniformly at random from the Web.
A tool for sampling URLs uniformly can be used to estimate various properties
of Web pages, such as the fraction of pages in various Internet domains or written
in various languages. Moreover, uniform URL sampling can be used to determine
the sizes of various search engines relative to the entire Web. In this paper,
we consider sampling approaches based on random walks of the Web graph. In particular,
we suggest ways of improving sampling based on random walks to make the samples
closer to uniform. We suggest a natural test bed based on random graphs for testing
the effectiveness of our procedures. We then use our sampling approach to estimate
the distribution of pages over various Internet domains and to estimate the coverage
of various search engine indexes.
article_processing_charge: No
article_type: original
author:
- 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: Allan
full_name: Heydon, Allan
last_name: Heydon
- first_name: Michael
full_name: Mitzenmacher, Michael
last_name: Mitzenmacher
- first_name: Marc
full_name: Najork, Marc
last_name: Najork
citation:
ama: Henzinger MH, Heydon A, Mitzenmacher M, Najork M. On near-uniform URL sampling.
Computer Networks. 2000;33(1-6):295-308. doi:10.1016/s1389-1286(00)00055-4
apa: Henzinger, M. H., Heydon, A., Mitzenmacher, M., & Najork, M. (2000). On
near-uniform URL sampling. Computer Networks. Elsevier. https://doi.org/10.1016/s1389-1286(00)00055-4
chicago: Henzinger, Monika H, Allan Heydon, Michael Mitzenmacher, and Marc Najork.
“On Near-Uniform URL Sampling.” Computer Networks. Elsevier, 2000. https://doi.org/10.1016/s1389-1286(00)00055-4.
ieee: M. H. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork, “On near-uniform
URL sampling,” Computer Networks, vol. 33, no. 1–6. Elsevier, pp. 295–308,
2000.
ista: Henzinger MH, Heydon A, Mitzenmacher M, Najork M. 2000. On near-uniform URL
sampling. Computer Networks. 33(1–6), 295–308.
mla: Henzinger, Monika H., et al. “On Near-Uniform URL Sampling.” Computer Networks,
vol. 33, no. 1–6, Elsevier, 2000, pp. 295–308, doi:10.1016/s1389-1286(00)00055-4.
short: M.H. Henzinger, A. Heydon, M. Mitzenmacher, M. Najork, Computer Networks
33 (2000) 295–308.
date_created: 2022-07-28T15:11:53Z
date_published: 2000-06-01T00:00:00Z
date_updated: 2022-09-12T09:09:13Z
day: '01'
doi: 10.1016/s1389-1286(00)00055-4
extern: '1'
intvolume: ' 33'
issue: 1-6
keyword:
- URL sampling
- Random walks
- Internet domain distribution
- Search engine size
language:
- iso: eng
month: '06'
oa_version: None
page: 295-308
publication: Computer Networks
publication_identifier:
issn:
- 1389-1286
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On near-uniform URL sampling
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2000'
...
---
_id: '11694'
abstract:
- lang: eng
text: We consider exploration problems where a robot has to construct a complete
map of an unknown environment. We assume that the environment is modeled by a
directed, strongly connected graph. The robot's task is to visit all nodes and
edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou
[Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990,
pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by
Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of
edges in the graph and d is the minimum number of edges that have to be added
to make the graph Eulerian. We give the 1rst subexponential algorithm for this
exploration problem, which achieves an upper bound of dO(logd)m. We also show
a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower
bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration
algorithms.
acknowledgement: We thank Prabhakar Raghavan for bringing to our attention the literature
on the s-t connectivity problem. We also thank an anonymous referee for many helpful
comments which improved the presentation of the paper.
article_processing_charge: No
article_type: original
author:
- first_name: Susanne
full_name: Albers, Susanne
last_name: Albers
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Albers S, Henzinger MH. Exploring unknown environments. SIAM Journal on
Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x
apa: 'Albers, S., & Henzinger, M. H. (2000). Exploring unknown environments.
SIAM Journal on Computing. El Paso, TX, United States: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/s009753979732428x'
chicago: Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.”
SIAM Journal on Computing. Society for Industrial and Applied Mathematics,
2000. https://doi.org/10.1137/s009753979732428x.
ieee: S. Albers and M. H. Henzinger, “Exploring unknown environments,” SIAM Journal
on Computing, vol. 29, no. 4. Society for Industrial and Applied Mathematics,
pp. 1164–1188, 2000.
ista: Albers S, Henzinger MH. 2000. Exploring unknown environments. SIAM Journal
on Computing. 29(4), 1164–1188.
mla: Albers, Susanne, and Monika H. Henzinger. “Exploring Unknown Environments.”
SIAM Journal on Computing, vol. 29, no. 4, Society for Industrial and Applied
Mathematics, 2000, pp. 1164–88, doi:10.1137/s009753979732428x.
short: S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.
conference:
end_date: 1997-05-06
location: El Paso, TX, United States
name: 'STOC97: 29th Annual Symposium on Theory of Computing'
start_date: 1997-05-04
date_created: 2022-07-29T09:04:36Z
date_published: 2000-07-01T00:00:00Z
date_updated: 2023-02-17T14:41:36Z
day: '01'
doi: 10.1137/s009753979732428x
extern: '1'
intvolume: ' 29'
issue: '4'
keyword:
- directed graph
- exploration algorithm
language:
- iso: eng
month: '07'
oa_version: None
page: 1164-1188
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Exploring unknown environments
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2000'
...
---
_id: '11770'
abstract:
- lang: eng
text: 'We compare several algorithms for identifying mirrored hosts on the World
Wide Web. The algorithms operate on the basis of URL strings and linkage data:
the type of information about Web pages easily available from Web proxies and
crawlers. Identification of mirrored hosts can improve Web-based information retrieval
in several ways: first, by identifying mirrored hosts, search engines can avoid
storing and returning duplicate documents. Second, several new information retrieval
techniques for the Web make inferences based on the explicit links among hypertext
documents—mirroring perturbs their graph model and degrades performance. Third,
mirroring information can be used to redirect users to alternate mirror sites
to compensate for various failures, and can thus improve the performance of Web
browsers and proxies. We evaluated four classes of “top-down” algorithms for detecting
mirrored host pairs (that is, algorithms that are based on page attributes such
as URL, IP address, and hyperlinks between pages, and not on the page content)
on a collection of 140 million URLs (on 230,000 hosts) and their associated connectivity
information. Our best approach is one which combines five algorithms and achieved
a precision of 0.57 for a recall of 0.86 considering 100,000 ranked host pairs.'
article_processing_charge: No
article_type: original
author:
- first_name: Krishna
full_name: Bharat, Krishna
last_name: Bharat
- first_name: Andrei
full_name: Broder, Andrei
last_name: Broder
- first_name: Jeffrey
full_name: Dean, Jeffrey
last_name: Dean
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Bharat K, Broder A, Dean J, Henzinger MH. A comparison of techniques to find
mirrored hosts on the WWW. Journal of the American Society for Information
Science. 2000;51(12):1114-1122. doi:10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
apa: Bharat, K., Broder, A., Dean, J., & Henzinger, M. H. (2000). A comparison
of techniques to find mirrored hosts on the WWW. Journal of the American Society
for Information Science. Wiley. https://doi.org/10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
chicago: Bharat, Krishna, Andrei Broder, Jeffrey Dean, and Monika H Henzinger. “A
Comparison of Techniques to Find Mirrored Hosts on the WWW.” Journal of the
American Society for Information Science. Wiley, 2000. https://doi.org/10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0.
ieee: K. Bharat, A. Broder, J. Dean, and M. H. Henzinger, “A comparison of techniques
to find mirrored hosts on the WWW,” Journal of the American Society for Information
Science, vol. 51, no. 12. Wiley, pp. 1114–1122, 2000.
ista: Bharat K, Broder A, Dean J, Henzinger MH. 2000. A comparison of techniques
to find mirrored hosts on the WWW. Journal of the American Society for Information
Science. 51(12), 1114–1122.
mla: Bharat, Krishna, et al. “A Comparison of Techniques to Find Mirrored Hosts
on the WWW.” Journal of the American Society for Information Science, vol.
51, no. 12, Wiley, 2000, pp. 1114–22, doi:10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0.
short: K. Bharat, A. Broder, J. Dean, M.H. Henzinger, Journal of the American Society
for Information Science 51 (2000) 1114–1122.
date_created: 2022-08-08T12:57:37Z
date_published: 2000-10-01T00:00:00Z
date_updated: 2023-02-10T08:27:19Z
day: '01'
doi: 10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
extern: '1'
intvolume: ' 51'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
month: '10'
oa: 1
oa_version: Published Version
page: 1114-1122
publication: Journal of the American Society for Information Science
publication_identifier:
issn:
- 0002-8231
- 1097-4571
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A comparison of techniques to find mirrored hosts on the WWW
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2000'
...
---
_id: '842'
article_processing_charge: No
article_type: original
author:
- first_name: Yuri
full_name: Wolf, Yuri
last_name: Wolf
- 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: Wolf Y, Kondrashov F, Koonin E. No footprints of primordial introns in a eukaryotic
genome. Trends in Genetics. 2000;16(8):333-334. doi:10.1016/S0168-9525(00)02059-X
apa: Wolf, Y., Kondrashov, F., & Koonin, E. (2000). No footprints of primordial
introns in a eukaryotic genome. Trends in Genetics. Elsevier. https://doi.org/10.1016/S0168-9525(00)02059-X
chicago: Wolf, Yuri, Fyodor Kondrashov, and Eugene Koonin. “No Footprints of Primordial
Introns in a Eukaryotic Genome.” Trends in Genetics. Elsevier, 2000. https://doi.org/10.1016/S0168-9525(00)02059-X.
ieee: Y. Wolf, F. Kondrashov, and E. Koonin, “No footprints of primordial introns
in a eukaryotic genome,” Trends in Genetics, vol. 16, no. 8. Elsevier,
pp. 333–334, 2000.
ista: Wolf Y, Kondrashov F, Koonin E. 2000. No footprints of primordial introns
in a eukaryotic genome. Trends in Genetics. 16(8), 333–334.
mla: Wolf, Yuri, et al. “No Footprints of Primordial Introns in a Eukaryotic Genome.”
Trends in Genetics, vol. 16, no. 8, Elsevier, 2000, pp. 333–34, doi:10.1016/S0168-9525(00)02059-X.
short: Y. Wolf, F. Kondrashov, E. Koonin, Trends in Genetics 16 (2000) 333–334.
date_created: 2018-12-11T11:48:48Z
date_published: 2000-08-01T00:00:00Z
date_updated: 2023-05-08T09:22:03Z
day: '01'
doi: 10.1016/S0168-9525(00)02059-X
extern: '1'
external_id:
pmid:
- '10904260 '
intvolume: ' 16'
issue: '8'
language:
- iso: eng
month: '08'
oa_version: None
page: 333 - 334
pmid: 1
publication: Trends in Genetics
publication_identifier:
issn:
- 0168-9479
publication_status: published
publisher: Elsevier
publist_id: '6806'
quality_controlled: '1'
scopus_import: '1'
status: public
title: No footprints of primordial introns in a eukaryotic genome
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 16
year: '2000'
...
---
_id: '8525'
abstract:
- lang: eng
text: Let M be a smooth compact manifold of dimension at least 2 and Diffr(M) be
the space of C r smooth diffeomorphisms of M. Associate to each diffeomorphism
f;isin; Diffr(M) the sequence P n (f) of the number of isolated periodic points
for f of period n. In this paper we exhibit an open set N in the space of diffeomorphisms
Diffr(M) such for a Baire generic diffeomorphism f∈N the number of periodic points
P n f grows with a period n faster than any following sequence of numbers {a n
} n ∈ Z + along a subsequence, i.e. P n (f)>a ni for some n i →∞ with i→∞. In
the cases of surface diffeomorphisms, i.e. dim M≡2, an open set N with a supergrowth
of the number of periodic points is a Newhouse domain. A proof of the man result
is based on the Gontchenko–Shilnikov–Turaev Theorem [GST]. A complete proof of
that theorem is also presented.
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
citation:
ama: Kaloshin V. Generic diffeomorphisms with superexponential growth of number
of periodic orbits. Communications in Mathematical Physics. 2000;211:253-271.
doi:10.1007/s002200050811
apa: Kaloshin, V. (2000). Generic diffeomorphisms with superexponential growth of
number of periodic orbits. Communications in Mathematical Physics. Springer
Nature. https://doi.org/10.1007/s002200050811
chicago: Kaloshin, Vadim. “Generic Diffeomorphisms with Superexponential Growth
of Number of Periodic Orbits.” Communications in Mathematical Physics.
Springer Nature, 2000. https://doi.org/10.1007/s002200050811.
ieee: V. Kaloshin, “Generic diffeomorphisms with superexponential growth of number
of periodic orbits,” Communications in Mathematical Physics, vol. 211.
Springer Nature, pp. 253–271, 2000.
ista: Kaloshin V. 2000. Generic diffeomorphisms with superexponential growth of
number of periodic orbits. Communications in Mathematical Physics. 211, 253–271.
mla: Kaloshin, Vadim. “Generic Diffeomorphisms with Superexponential Growth of Number
of Periodic Orbits.” Communications in Mathematical Physics, vol. 211,
Springer Nature, 2000, pp. 253–71, doi:10.1007/s002200050811.
short: V. Kaloshin, Communications in Mathematical Physics 211 (2000) 253–271.
date_created: 2020-09-18T10:50:20Z
date_published: 2000-04-01T00:00:00Z
date_updated: 2021-01-12T08:19:52Z
day: '01'
doi: 10.1007/s002200050811
extern: '1'
intvolume: ' 211'
keyword:
- Mathematical Physics
- Statistical and Nonlinear Physics
language:
- iso: eng
month: '04'
oa_version: None
page: 253-271
publication: Communications in Mathematical Physics
publication_identifier:
issn:
- 0010-3616
- 1432-0916
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Generic diffeomorphisms with superexponential growth of number of periodic
orbits
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 211
year: '2000'
...
---
_id: '1736'
abstract:
- lang: eng
text: A coding scheme called diode is compared with duobinary signalling and with
normal binary transmission. It is shown that the diode coding suppresses the FWM
products of a three channel DWDM system and this reduction against that achieved
with duobinary coding is presented. The results presented show how the average
level of the FWM products relative to the average levels of the three optical
carriers vary over the channel spacing range. The suppression observed is about
/ dB more than that achieved with duobinary modulation and is greater for narrow
channel spacing.
alternative_title:
- LEOS
article_processing_charge: No
author:
- first_name: Georgios
full_name: Katsaros, Georgios
id: 38DB5788-F248-11E8-B48F-1D18A9856A87
last_name: Katsaros
- first_name: Phil
full_name: Lane, Phil
last_name: Lane
- first_name: Michelle
full_name: Murphy, Michelle
last_name: Murphy
citation:
ama: 'Katsaros G, Lane P, Murphy M. Comparison of the impact of FWM on binary, duobinary
and dicode modulation in DWDM systems. In: Proceedings of the 2000 IEEE Annual
Meeting Conference . Vol 1. IEEE; 2000:27-28. doi:10.1109/LEOS.2000.890656'
apa: 'Katsaros, G., Lane, P., & Murphy, M. (2000). Comparison of the impact
of FWM on binary, duobinary and dicode modulation in DWDM systems. In Proceedings
of the 2000 IEEE Annual Meeting Conference (Vol. 1, pp. 27–28). Rio Grande,
PR, USA: IEEE. https://doi.org/10.1109/LEOS.2000.890656'
chicago: Katsaros, Georgios, Phil Lane, and Michelle Murphy. “Comparison of the
Impact of FWM on Binary, Duobinary and Dicode Modulation in DWDM Systems.” In
Proceedings of the 2000 IEEE Annual Meeting Conference , 1:27–28. IEEE,
2000. https://doi.org/10.1109/LEOS.2000.890656.
ieee: G. Katsaros, P. Lane, and M. Murphy, “Comparison of the impact of FWM on binary,
duobinary and dicode modulation in DWDM systems,” in Proceedings of the 2000
IEEE Annual Meeting Conference , Rio Grande, PR, USA, 2000, vol. 1, pp. 27–28.
ista: Katsaros G, Lane P, Murphy M. 2000. Comparison of the impact of FWM on binary,
duobinary and dicode modulation in DWDM systems. Proceedings of the 2000 IEEE
Annual Meeting Conference . Lasers and Electro Optics Society Annual Meeting,
LEOS, vol. 1, 27–28.
mla: Katsaros, Georgios, et al. “Comparison of the Impact of FWM on Binary, Duobinary
and Dicode Modulation in DWDM Systems.” Proceedings of the 2000 IEEE Annual
Meeting Conference , vol. 1, IEEE, 2000, pp. 27–28, doi:10.1109/LEOS.2000.890656.
short: G. Katsaros, P. Lane, M. Murphy, in:, Proceedings of the 2000 IEEE Annual
Meeting Conference , IEEE, 2000, pp. 27–28.
conference:
end_date: 2000-11-16
location: Rio Grande, PR, USA
name: Lasers and Electro Optics Society Annual Meeting
start_date: 2000-11-13
date_created: 2018-12-11T11:53:44Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2023-05-04T14:46:21Z
day: '01'
doi: 10.1109/LEOS.2000.890656
extern: '1'
intvolume: ' 1'
language:
- iso: eng
month: '01'
oa_version: None
page: 27 - 28
publication: 'Proceedings of the 2000 IEEE Annual Meeting Conference '
publication_identifier:
isbn:
- 078035947X
publication_status: published
publisher: IEEE
publist_id: '5388'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Comparison of the impact of FWM on binary, duobinary and dicode modulation
in DWDM systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '2000'
...
---
_id: '1957'
abstract:
- lang: eng
text: NADH:ubiquinone oxidoreductase (complex I) is the first and largest enzyme
of the mitochondrial respiratory chain. The low-resolution structure of the complex
is known from electron microscopy studies. The general shape of the complex is
in the form of an L, with one arm in the membrane and the other peripheral. We
have purified complex I from beef heart mitochondria and reconstituted the enzyme
into lipid bilayers. Under different conditions, several two-dimensional crystal
forms were obtained. Crystals belonging to space groups p2221 and c12 (unit cell
488 Å x 79 Å) were obtained at 22°C and contained only the membrane fragment of
complex I similar to hydrophobic subcomplex Iβ but lacking the ND5 subunit. A
crystal form with larger unit cell (534 Å x 81 Å, space group c12) produced at
4°C contained both the peripheral and membrane arms of the enzyme, except that
ND5 was missing. Projection maps from frozen hydrated samples were calculated
for all crystal forms. By comparing two different c12 crystal forms, extra electron
density in the projection map of large crystal form was assigned to the peripheral
arm of the enzyme. One of the features of the map is a deep, channel-like, cleft
next to peripheral arm. Comparison with available structures of the intact enzyme
indicates that large hydrophobic subunit ND5 is situated at the distal end of
the membrane domain. Possible locations of sub-unit ND4 and of other subunits
in the membrane domain are proposed. Implications of our findings for the mechanism
of proton pumping by complex I are discussed. (C) 2000 Academic Press.
acknowledgement: We thank Drs I. M. Fearnley and S. Y. Peak-Chew for performing peptide
mass mapping. We also thank Drs R. Henderson and G. F. X. Schertler for advice on
image processing and for valuable discussions.
article_processing_charge: No
article_type: original
author:
- first_name: Leonid A
full_name: Sazanov, Leonid A
id: 338D39FE-F248-11E8-B48F-1D18A9856A87
last_name: Sazanov
orcid: 0000-0002-0977-7989
- first_name: John
full_name: Walker, John
last_name: Walker
citation:
ama: Sazanov LA, Walker J. Cryo-electron crystallography of two sub-complexes of
bovine complex I reveals the relationship between the membrane and peripheral
arms. Journal of Molecular Biology. 2000;302(2):455-464. doi:10.1006/jmbi.2000.4079
apa: Sazanov, L. A., & Walker, J. (2000). Cryo-electron crystallography of two
sub-complexes of bovine complex I reveals the relationship between the membrane
and peripheral arms. Journal of Molecular Biology. Elsevier. https://doi.org/10.1006/jmbi.2000.4079
chicago: Sazanov, Leonid A, and John Walker. “Cryo-Electron Crystallography of Two
Sub-Complexes of Bovine Complex I Reveals the Relationship between the Membrane
and Peripheral Arms.” Journal of Molecular Biology. Elsevier, 2000. https://doi.org/10.1006/jmbi.2000.4079.
ieee: L. A. Sazanov and J. Walker, “Cryo-electron crystallography of two sub-complexes
of bovine complex I reveals the relationship between the membrane and peripheral
arms,” Journal of Molecular Biology, vol. 302, no. 2. Elsevier, pp. 455–464,
2000.
ista: Sazanov LA, Walker J. 2000. Cryo-electron crystallography of two sub-complexes
of bovine complex I reveals the relationship between the membrane and peripheral
arms. Journal of Molecular Biology. 302(2), 455–464.
mla: Sazanov, Leonid A., and John Walker. “Cryo-Electron Crystallography of Two
Sub-Complexes of Bovine Complex I Reveals the Relationship between the Membrane
and Peripheral Arms.” Journal of Molecular Biology, vol. 302, no. 2, Elsevier,
2000, pp. 455–64, doi:10.1006/jmbi.2000.4079.
short: L.A. Sazanov, J. Walker, Journal of Molecular Biology 302 (2000) 455–464.
date_created: 2018-12-11T11:54:55Z
date_published: 2000-09-15T00:00:00Z
date_updated: 2023-05-04T13:23:03Z
day: '15'
doi: 10.1006/jmbi.2000.4079
extern: '1'
external_id:
pmid:
- '10970745'
intvolume: ' 302'
issue: '2'
language:
- iso: eng
month: '09'
oa_version: None
page: 455 - 464
pmid: 1
publication: Journal of Molecular Biology
publication_identifier:
issn:
- 0022-2836
publication_status: published
publisher: Elsevier
publist_id: '5126'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cryo-electron crystallography of two sub-complexes of bovine complex I reveals
the relationship between the membrane and peripheral arms
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 302
year: '2000'
...
---
_id: '1958'
abstract:
- lang: eng
text: "\r\nComplex I (NADH:ubiquinone oxidoreductase) purified from bovine heart
mitochondria was treated with the detergent N,N-dimethyldodecylamine N-oxide (LDAO).
The enzyme dissociated into two known subcomplexes, Iα and Iβ, containing mostly
hydrophilic and hydrophobic subunits, and a previously undetected fragment referred
to as Iγ. Subcomplex Iγ contains the hydrophobic subunits ND1, ND2, ND3, and ND4L
which are encoded in the mitochondrial genome, and the nuclear-encoded subunit
KFYL. During size- exclusion chromatography in the presence of LDAO, subcomplex
Iα lost several subunits and formed another characterized subcomplex known as
Iλ. Similarly, subcomplex Iβ dissociated into two smaller subcomplexes, one of
which contains the hydrophobic subunits ND4 and ND5; subcomplex Iγ released a
fragment containing ND1 and ND2. These results suggest that in the intact complex
subunits ND1 and ND2 are likely to be in a different region of the membrane domain
than subunits ND4 and ND5. The compositions of the various subcomplexes and fragments
of complex I provide an organization of the subunits of the enzyme in the framework
of the known low resolution structure of the enzyme."
article_processing_charge: No
article_type: original
author:
- first_name: Leonid A
full_name: Sazanov, Leonid A
id: 338D39FE-F248-11E8-B48F-1D18A9856A87
last_name: Sazanov
orcid: 0000-0002-0977-7989
- first_name: Sew
full_name: Peak Chew, Sew
last_name: Peak Chew
- first_name: Ian
full_name: Fearnley, Ian
last_name: Fearnley
- first_name: John
full_name: Walker, John
last_name: Walker
citation:
ama: 'Sazanov LA, Peak Chew S, Fearnley I, Walker J. Resolution of the membrane
domain of bovine complex I into subcomplexes: implications for the structural
organization of the enzyme. Biochemistry. 2000;39(24):7229-7235. doi:10.1021/bi000335t'
apa: 'Sazanov, L. A., Peak Chew, S., Fearnley, I., & Walker, J. (2000). Resolution
of the membrane domain of bovine complex I into subcomplexes: implications for
the structural organization of the enzyme. Biochemistry. ACS. https://doi.org/10.1021/bi000335t'
chicago: 'Sazanov, Leonid A, Sew Peak Chew, Ian Fearnley, and John Walker. “Resolution
of the Membrane Domain of Bovine Complex I into Subcomplexes: Implications for
the Structural Organization of the Enzyme.” Biochemistry. ACS, 2000. https://doi.org/10.1021/bi000335t.'
ieee: 'L. A. Sazanov, S. Peak Chew, I. Fearnley, and J. Walker, “Resolution of the
membrane domain of bovine complex I into subcomplexes: implications for the structural
organization of the enzyme,” Biochemistry, vol. 39, no. 24. ACS, pp. 7229–7235,
2000.'
ista: 'Sazanov LA, Peak Chew S, Fearnley I, Walker J. 2000. Resolution of the membrane
domain of bovine complex I into subcomplexes: implications for the structural
organization of the enzyme. Biochemistry. 39(24), 7229–7235.'
mla: 'Sazanov, Leonid A., et al. “Resolution of the Membrane Domain of Bovine Complex
I into Subcomplexes: Implications for the Structural Organization of the Enzyme.”
Biochemistry, vol. 39, no. 24, ACS, 2000, pp. 7229–35, doi:10.1021/bi000335t.'
short: L.A. Sazanov, S. Peak Chew, I. Fearnley, J. Walker, Biochemistry 39 (2000)
7229–7235.
date_created: 2018-12-11T11:54:55Z
date_published: 2000-05-24T00:00:00Z
date_updated: 2023-05-04T14:14:53Z
day: '24'
doi: 10.1021/bi000335t
extern: '1'
external_id:
pmid:
- '10852722'
intvolume: ' 39'
issue: '24'
language:
- iso: eng
month: '05'
oa_version: None
page: 7229 - 7235
pmid: 1
publication: Biochemistry
publication_identifier:
issn:
- 0006-2960
publication_status: published
publisher: ACS
publist_id: '5127'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Resolution of the membrane domain of bovine complex I into subcomplexes: implications
for the structural organization of the enzyme'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 39
year: '2000'
...
---
_id: '2325'
alternative_title:
- Contemporary Mathematics
author:
- first_name: Robert
full_name: Robert Seiringer
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: 'Seiringer R. Inequalities for Schrödinger operators and applications to the
stability of matter problem . In: Vol 529. American Mathematical Society; 2000:53-72.
doi:10.1090/conm/529'
apa: Seiringer, R. (2000). Inequalities for Schrödinger operators and applications
to the stability of matter problem (Vol. 529, pp. 53–72). Presented at the Arizona
School of Analysis With Applications, American Mathematical Society. https://doi.org/10.1090/conm/529
chicago: Seiringer, Robert. “Inequalities for Schrödinger Operators and Applications
to the Stability of Matter Problem ,” 529:53–72. American Mathematical Society,
2000. https://doi.org/10.1090/conm/529.
ieee: R. Seiringer, “Inequalities for Schrödinger operators and applications to
the stability of matter problem ,” presented at the Arizona School of Analysis
With Applications, 2000, vol. 529, pp. 53–72.
ista: Seiringer R. 2000. Inequalities for Schrödinger operators and applications
to the stability of matter problem . Arizona School of Analysis With Applications,
Contemporary Mathematics, vol. 529, 53–72.
mla: Seiringer, Robert. Inequalities for Schrödinger Operators and Applications
to the Stability of Matter Problem . Vol. 529, American Mathematical Society,
2000, pp. 53–72, doi:10.1090/conm/529.
short: R. Seiringer, in:, American Mathematical Society, 2000, pp. 53–72.
conference:
name: Arizona School of Analysis With Applications
date_created: 2018-12-11T11:57:00Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:47Z
day: '01'
doi: 10.1090/conm/529
extern: 1
intvolume: ' 529'
month: '01'
page: 53 - 72
publication_status: published
publisher: American Mathematical Society
publist_id: '4602'
quality_controlled: 0
status: public
title: 'Inequalities for Schrödinger operators and applications to the stability of
matter problem '
type: conference
volume: 529
year: '2000'
...
---
_id: '2342'
abstract:
- lang: eng
text: In the theoretical description of recent experiments with dilute Bose gases
confined in external potentials the Gross-Pitaevskii equation plays an important
role. Its status as an approximation for the quantum mechanical many-body ground
state problem has recently been rigorously clarified. A summary of this work is
presented here.
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
- first_name: Élliott
full_name: Lieb, Élliott
last_name: Lieb
- first_name: Jakob
full_name: Yngvason, Jakob
last_name: Yngvason
citation:
ama: 'Seiringer R, Lieb É, Yngvason J. The ground state energy and density of interacting
bosons in a trap. In: Proceedings of the International Symposium on Quantum
Theory and Symmetries. World Scientific Publishing; 2000:101-110.'
apa: Seiringer, R., Lieb, É., & Yngvason, J. (2000). The ground state energy
and density of interacting bosons in a trap. In Proceedings of the International
Symposium on Quantum Theory and Symmetries (pp. 101–110). World Scientific
Publishing.
chicago: Seiringer, Robert, Élliott Lieb, and Jakob Yngvason. “The Ground State
Energy and Density of Interacting Bosons in a Trap.” In Proceedings of the
International Symposium on Quantum Theory and Symmetries, 101–10. World Scientific
Publishing, 2000.
ieee: R. Seiringer, É. Lieb, and J. Yngvason, “The ground state energy and density
of interacting bosons in a trap,” in Proceedings of the International Symposium
on Quantum Theory and Symmetries, 2000, pp. 101–110.
ista: 'Seiringer R, Lieb É, Yngvason J. 2000. The ground state energy and density
of interacting bosons in a trap. Proceedings of the International Symposium on
Quantum Theory and Symmetries. ISQTS: Quantum Theory and Symmetries, 101–110.'
mla: Seiringer, Robert, et al. “The Ground State Energy and Density of Interacting
Bosons in a Trap.” Proceedings of the International Symposium on Quantum Theory
and Symmetries, World Scientific Publishing, 2000, pp. 101–10.
short: R. Seiringer, É. Lieb, J. Yngvason, in:, Proceedings of the International
Symposium on Quantum Theory and Symmetries, World Scientific Publishing, 2000,
pp. 101–110.
conference:
name: 'ISQTS: Quantum Theory and Symmetries'
date_created: 2018-12-11T11:57:06Z
date_published: 2000-06-01T00:00:00Z
date_updated: 2023-05-03T13:00:35Z
day: '01'
extern: '1'
external_id:
arxiv:
- math-ph/9911026
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/9911026
month: '06'
oa: 1
oa_version: None
page: 101 - 110
publication: Proceedings of the International Symposium on Quantum Theory and Symmetries
publication_identifier:
isbn:
- '9789810242374 '
publication_status: published
publisher: World Scientific Publishing
publist_id: '4584'
quality_controlled: '1'
status: public
title: The ground state energy and density of interacting bosons in a trap
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2000'
...
---
_id: '2343'
abstract:
- lang: eng
text: We study the energy levels of a single particle in a homogeneous magnetic
field and in an axially symmetric external potential. For potentials that are
superharmonic off the central axis, we find a general 'pseudoconcave' ordering
of the ground state energies of the Hamiltonian restricted to the sectors with
fixed angular momentum. The physical applications include atoms and ions in strong
magnetic fields. There the energies are monotone increasing and concave in angular
momentum. In the case of a periodic chain of atoms, the pseudoconcavity extends
to the entire lowest band of Bloch functions.
author:
- first_name: Bernhard
full_name: Baumgartner, Bernhard
last_name: Baumgartner
- first_name: Robert
full_name: Robert Seiringer
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Baumgartner B, Seiringer R. On the ordering of energy levels in homogeneous
magnetic fields. Letters in Mathematical Physics. 2000;54(3):213-226. doi: 10.1023/A:1010978807635
apa: Baumgartner, B., & Seiringer, R. (2000). On the ordering of energy levels
in homogeneous magnetic fields. Letters in Mathematical Physics. Springer.
https://doi.org/ 10.1023/A:1010978807635
chicago: Baumgartner, Bernhard, and Robert Seiringer. “On the Ordering of Energy
Levels in Homogeneous Magnetic Fields.” Letters in Mathematical Physics.
Springer, 2000. https://doi.org/
10.1023/A:1010978807635.
ieee: B. Baumgartner and R. Seiringer, “On the ordering of energy levels in homogeneous
magnetic fields,” Letters in Mathematical Physics, vol. 54, no. 3. Springer,
pp. 213–226, 2000.
ista: Baumgartner B, Seiringer R. 2000. On the ordering of energy levels in homogeneous
magnetic fields. Letters in Mathematical Physics. 54(3), 213–226.
mla: Baumgartner, Bernhard, and Robert Seiringer. “On the Ordering of Energy Levels
in Homogeneous Magnetic Fields.” Letters in Mathematical Physics, vol.
54, no. 3, Springer, 2000, pp. 213–26, doi:
10.1023/A:1010978807635.
short: B. Baumgartner, R. Seiringer, Letters in Mathematical Physics 54 (2000) 213–226.
date_created: 2018-12-11T11:57:06Z
date_published: 2000-11-01T00:00:00Z
date_updated: 2021-01-12T06:56:54Z
day: '01'
doi: ' 10.1023/A:1010978807635'
extern: 1
intvolume: ' 54'
issue: '3'
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/0011031
month: '11'
oa: 1
page: 213 - 226
publication: Letters in Mathematical Physics
publication_status: published
publisher: Springer
publist_id: '4582'
quality_controlled: 0
status: public
title: On the ordering of energy levels in homogeneous magnetic fields
type: journal_article
volume: 54
year: '2000'
...
---
_id: '2344'
abstract:
- lang: eng
text: The ground-state properties of interacting Bose gases in external potentials,
as considered in recent experiments, are usually described by means of the Gross-Pitaevskii
energy functional. We present here a rigorous proof of the asymptotic exactness
of this approximation for the ground-state energy and particle density of a dilute
Bose gas with a positive interaction.
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. Bosons in a trap: A rigorous derivation of
the Gross-Pitaevskii energy functional. Physical Review A - Atomic, Molecular,
and Optical Physics. 2000;61(4):436021-4360213. doi:10.1103/PhysRevA.61.043602'
apa: 'Lieb, É., Seiringer, R., & Yngvason, J. (2000). Bosons in a trap: A rigorous
derivation of the Gross-Pitaevskii energy functional. Physical Review A - Atomic,
Molecular, and Optical Physics. American Physical Society. https://doi.org/10.1103/PhysRevA.61.043602'
chicago: 'Lieb, Élliott, Robert Seiringer, and Jakob Yngvason. “Bosons in a Trap:
A Rigorous Derivation of the Gross-Pitaevskii Energy Functional.” Physical
Review A - Atomic, Molecular, and Optical Physics. American Physical Society,
2000. https://doi.org/10.1103/PhysRevA.61.043602.'
ieee: 'É. Lieb, R. Seiringer, and J. Yngvason, “Bosons in a trap: A rigorous derivation
of the Gross-Pitaevskii energy functional,” Physical Review A - Atomic, Molecular,
and Optical Physics, vol. 61, no. 4. American Physical Society, pp. 436021–4360213,
2000.'
ista: 'Lieb É, Seiringer R, Yngvason J. 2000. Bosons in a trap: A rigorous derivation
of the Gross-Pitaevskii energy functional. Physical Review A - Atomic, Molecular,
and Optical Physics. 61(4), 436021–4360213.'
mla: 'Lieb, Élliott, et al. “Bosons in a Trap: A Rigorous Derivation of the Gross-Pitaevskii
Energy Functional.” Physical Review A - Atomic, Molecular, and Optical Physics,
vol. 61, no. 4, American Physical Society, 2000, pp. 436021–4360213, doi:10.1103/PhysRevA.61.043602.'
short: É. Lieb, R. Seiringer, J. Yngvason, Physical Review A - Atomic, Molecular,
and Optical Physics 61 (2000) 436021–4360213.
date_created: 2018-12-11T11:57:07Z
date_published: 2000-04-01T00:00:00Z
date_updated: 2023-05-03T12:47:08Z
day: '01'
doi: 10.1103/PhysRevA.61.043602
extern: '1'
external_id:
arxiv:
- math-ph/9908027
intvolume: ' 61'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math-ph/9908027
month: '04'
oa: 1
oa_version: Published Version
page: 436021 - 4360213
publication: Physical Review A - Atomic, Molecular, and Optical Physics
publication_identifier:
issn:
- 0556-2791
publication_status: published
publisher: American Physical Society
publist_id: '4583'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Bosons in a trap: A rigorous derivation of the Gross-Pitaevskii energy functional'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 61
year: '2000'
...
---
_id: '2418'
abstract:
- lang: eng
text: For an absolutely continuous probability measure μ on Rd and a nonnegative
integer k, let sk(μ, 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 sk(μ, 0), and we characterize the measures
in Rd which attain this bound. 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 for simplicial convex polytopes.
article_processing_charge: No
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. Origin-embracing distributions or a continuous analogue
of the Upper Bound Theorem. In: Proceedings of the 16th Annual Symposium on
Computational Geometry. ACM; 2000:50-56. doi:10.1145/336154.336176'
apa: 'Wagner, U., & Welzl, E. (2000). Origin-embracing distributions or a continuous
analogue of the Upper Bound Theorem. In Proceedings of the 16th annual symposium
on Computational geometry (pp. 50–56). Clear Water Bay Kowloon, Hong Kong:
ACM. https://doi.org/10.1145/336154.336176'
chicago: Wagner, Uli, and Emo Welzl. “Origin-Embracing Distributions or a Continuous
Analogue of the Upper Bound Theorem.” In Proceedings of the 16th Annual Symposium
on Computational Geometry, 50–56. ACM, 2000. https://doi.org/10.1145/336154.336176.
ieee: U. Wagner and E. Welzl, “Origin-embracing distributions or a continuous analogue
of the Upper Bound Theorem,” in Proceedings of the 16th annual symposium on
Computational geometry, Clear Water Bay Kowloon, Hong Kong, 2000, pp. 50–56.
ista: 'Wagner U, Welzl E. 2000. Origin-embracing distributions or a continuous analogue
of the Upper Bound Theorem. Proceedings of the 16th annual symposium on Computational
geometry. SCG: Symposium on Computational Geometry, 50–56.'
mla: Wagner, Uli, and Emo Welzl. “Origin-Embracing Distributions or a Continuous
Analogue of the Upper Bound Theorem.” Proceedings of the 16th Annual Symposium
on Computational Geometry, ACM, 2000, pp. 50–56, doi:10.1145/336154.336176.
short: U. Wagner, E. Welzl, in:, Proceedings of the 16th Annual Symposium on Computational
Geometry, ACM, 2000, pp. 50–56.
conference:
end_date: 2000-04-14
location: Clear Water Bay Kowloon, Hong Kong
name: 'SCG: Symposium on Computational Geometry'
start_date: 2000-06-12
date_created: 2018-12-11T11:57:33Z
date_published: 2000-05-01T00:00:00Z
date_updated: 2023-05-03T12:41:02Z
day: '01'
doi: 10.1145/336154.336176
extern: '1'
language:
- iso: eng
month: '05'
oa_version: None
page: 50 - 56
publication: Proceedings of the 16th annual symposium on Computational geometry
publication_identifier:
isbn:
- '9781581132243'
publication_status: published
publisher: ACM
publist_id: '4507'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Origin-embracing distributions or a continuous analogue of the Upper Bound
Theorem
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2000'
...
---
_id: '4598'
abstract:
- lang: eng
text: A hybrid system is a dynamical system with both discrete and continuous state
changes. For analysis purposes, it is often useful to abstract a system in a way
that preserves the properties being analyzed while hiding the details that are
of no interest. We show that interesting classes of hybrid systems can be abstracted
to purely discrete systems while preserving all properties that are definable
in temporal logic. The classes that permit discrete abstractions fall into two
categories. Either the continuous dynamics must be restricted, as is the case
for timed and rectangular hybrid systems, or the discrete dynamics must be restricted,
as is the case for o-minimal hybrid systems. In this paper, we survey and unify
results from both areas.
acknowledgement: The authors would like to thank the reviewers for their detailed
comments.
article_processing_charge: No
article_type: original
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- 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: Gerardo
full_name: Lafferriere, Gerardo
last_name: Lafferriere
- first_name: George
full_name: Pappas, George
last_name: Pappas
citation:
ama: Alur R, Henzinger TA, Lafferriere G, Pappas G. Discrete abstractions of hybrid
systems. Proceedings of the IEEE. 2000;88(7):971-984. doi:10.1109/5.871304
apa: Alur, R., Henzinger, T. A., Lafferriere, G., & Pappas, G. (2000). Discrete
abstractions of hybrid systems. Proceedings of the IEEE. IEEE. https://doi.org/10.1109/5.871304
chicago: Alur, Rajeev, Thomas A Henzinger, Gerardo Lafferriere, and George Pappas.
“Discrete Abstractions of Hybrid Systems.” Proceedings of the IEEE. IEEE,
2000. https://doi.org/10.1109/5.871304
.
ieee: R. Alur, T. A. Henzinger, G. Lafferriere, and G. Pappas, “Discrete abstractions
of hybrid systems,” Proceedings of the IEEE, vol. 88, no. 7. IEEE, pp.
971–984, 2000.
ista: Alur R, Henzinger TA, Lafferriere G, Pappas G. 2000. Discrete abstractions
of hybrid systems. Proceedings of the IEEE. 88(7), 971–984.
mla: Alur, Rajeev, et al. “Discrete Abstractions of Hybrid Systems.” Proceedings
of the IEEE, vol. 88, no. 7, IEEE, 2000, pp. 971–84, doi:10.1109/5.871304 .
short: R. Alur, T.A. Henzinger, G. Lafferriere, G. Pappas, Proceedings of the IEEE
88 (2000) 971–984.
date_created: 2018-12-11T12:09:41Z
date_published: 2000-07-01T00:00:00Z
date_updated: 2023-04-13T13:32:11Z
day: '01'
doi: '10.1109/5.871304 '
extern: '1'
intvolume: ' 88'
issue: '7'
language:
- iso: eng
month: '07'
oa_version: None
page: 971 - 984
publication: Proceedings of the IEEE
publication_identifier:
issn:
- 0018-9219
publication_status: published
publisher: IEEE
publist_id: '107'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discrete abstractions of hybrid systems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 88
year: '2000'
...
---
_id: '4627'
abstract:
- lang: eng
text: 'We consider two-player games, which are played on a finite state space for
an infinite number of rounds. The games are concurrent, that is, in each round,
the two players choose their moves independently and simultaneously; the current
state and the two moves determine a successor state. We consider omega-regular
winning conditions on the resulting infinite state sequence. To model the independent
choice of moves, both players are allowed to use randomization for selecting their
moves. This gives rise to the following qualitative modes of winning, which can
be studied without numerical considerations concerning probabilities: sure-win
(player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure
winning with probability 1), limit-win (player 1 can ensure winning with probability
arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability
bounded away from 0), positive-win (player 1 can ensure winning with positive
probability), and exist-win (player 1 can ensure that at least one possible outcome
of the game satisfies the winning condition).We provide algorithms for computing
the sets of winning states for each of these winning modes. In particular, we
solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the
game structure and m is the number of pairs in the Rabin-chain condition. While
this complexity is in line with traditional turn-based games, where in each state
only one of the two players has a choice of moves, our algorithms are considerably
more involved than those for turn-based games are. This is because concurrent
games violate two of the most fundamental properties of turn-based games. First,
concurrent games are not determined, but rather exhibit a more general duality
property, which involves multiple modes of winning. Second, winning strategies
for concurrent games may require infinite memory.'
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. Concurrent omega-regular games. In: Proceedings
of the 15th Annual IEEE Symposium on Logic in Computer Science. IEEE; 2000:141-154.
doi:10.1109/LICS.2000.855763'
apa: 'De Alfaro, L., & Henzinger, T. A. (2000). Concurrent omega-regular games.
In Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science
(pp. 141–154). Santa Barbara, CA, USA: IEEE. https://doi.org/10.1109/LICS.2000.855763'
chicago: De Alfaro, Luca, and Thomas A Henzinger. “Concurrent Omega-Regular Games.”
In Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science,
141–54. IEEE, 2000. https://doi.org/10.1109/LICS.2000.855763.
ieee: L. De Alfaro and T. A. Henzinger, “Concurrent omega-regular games,” in Proceedings
of the 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara,
CA, USA, 2000, pp. 141–154.
ista: 'De Alfaro L, Henzinger TA. 2000. Concurrent omega-regular games. Proceedings
of the 15th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in
Computer Science, 141–154.'
mla: De Alfaro, Luca, and Thomas A. Henzinger. “Concurrent Omega-Regular Games.”
Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science,
IEEE, 2000, pp. 141–54, doi:10.1109/LICS.2000.855763.
short: L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 15th Annual IEEE Symposium
on Logic in Computer Science, IEEE, 2000, pp. 141–154.
conference:
end_date: 2000-06-28
location: Santa Barbara, CA, USA
name: 'LICS: Logic in Computer Science'
start_date: 2000-06-26
date_created: 2018-12-11T12:09:50Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2023-04-13T13:24:29Z
day: '01'
doi: 10.1109/LICS.2000.855763
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 141 - 154
publication: Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science
publication_identifier:
isbn:
- '0769507255'
publication_status: published
publisher: IEEE
publist_id: '82'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent omega-regular games
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2000'
...
---
_id: '4637'
abstract:
- lang: eng
text: "In the synchronous composition of processes, one process may prevent another
process from proceeding unless compositions without a well-defined product behavior
are ruled out. They can be ruled out semantically, by insisting on the existence
of certain fixed points, or syntactically, by equipping processes with types,
which make the dependencies between input and output signals transparent. We classify
various typing mechanisms and study their effects on the control problem.\r\nA
static type enforces fixed, acyclic dependencies between input and output ports.
For example, synchronous hardware without combinational loops can be typed statically.
A dynamic type may vary the dependencies from state to state, while maintaining
acyclicity, as in level-sensitive latches. Then, two dynamically typed processes
can be syntactically compatible, if all pairs of possible dependencies are compatible,
or semantically compatible, if in each state the combined dependencies remain
acyclic. For a given plant process and control objective, there may be a controller
of a static type, or only a controller of a syntactically compatible dynamic type,
or only a controller of a semantically compatible dynamic type. We show this to
be a strict hierarchy of possibilities, and we present algorithms and determine
the complexity of the corresponding control problems.\r\nFurthermore, we consider
versions of the control problem in which the type of the controller (static or
dynamic) is given. We show that the solution of these fixed-type control problems
requires the evaluation of partially ordered (Henkin) quantifiers on boolean formulas,
and is therefore harder (nondeterministic exponential time) than more traditional
control questions"
acknowledgement: This research was supported in part by the DARPA grants NAG2-1214
and F33615-C-98-3614, the SRC contract 99-TJ-683.003, the MARCO grant 98-DT-660,
and the NSF CAREER award CCR-9501708.
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: Freddy
full_name: Mang, Freddy
last_name: Mang
citation:
ama: 'De Alfaro L, Henzinger TA, Mang F. The control of synchronous systems. In:
Proceedings of the 11th International Conference on Concurrency Theory.
Vol 1877. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2000:458-473. doi:10.1007/3-540-44618-4_33'
apa: 'De Alfaro, L., Henzinger, T. A., & Mang, F. (2000). The control of synchronous
systems. In Proceedings of the 11th International Conference on Concurrency
Theory (Vol. 1877, pp. 458–473). University Park, PA, USA: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44618-4_33'
chicago: De Alfaro, Luca, Thomas A Henzinger, and Freddy Mang. “The Control of Synchronous
Systems.” In Proceedings of the 11th International Conference on Concurrency
Theory, 1877:458–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2000.
https://doi.org/10.1007/3-540-44618-4_33.
ieee: L. De Alfaro, T. A. Henzinger, and F. Mang, “The control of synchronous systems,”
in Proceedings of the 11th International Conference on Concurrency Theory,
University Park, PA, USA, 2000, vol. 1877, pp. 458–473.
ista: 'De Alfaro L, Henzinger TA, Mang F. 2000. The control of synchronous systems.
Proceedings of the 11th International Conference on Concurrency Theory. CONCUR:
Concurrency Theory, LNCS, vol. 1877, 458–473.'
mla: De Alfaro, Luca, et al. “The Control of Synchronous Systems.” Proceedings
of the 11th International Conference on Concurrency Theory, vol. 1877, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2000, pp. 458–73, doi:10.1007/3-540-44618-4_33.
short: L. De Alfaro, T.A. Henzinger, F. Mang, in:, Proceedings of the 11th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2000, pp. 458–473.
conference:
end_date: 2000-08-25
location: University Park, PA, USA
name: 'CONCUR: Concurrency Theory'
start_date: 2000-08-22
date_created: 2018-12-11T12:09:53Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2023-04-13T11:00:46Z
day: '01'
doi: 10.1007/3-540-44618-4_33
extern: '1'
intvolume: ' 1877'
language:
- iso: eng
month: '01'
oa_version: None
page: 458 - 473
publication: Proceedings of the 11th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783540678977'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '69'
quality_controlled: '1'
status: public
title: The control of synchronous systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1877
year: '2000'
...
---
_id: '4638'
abstract:
- lang: eng
text: "Any formal method or tool is almost certainly more often applied in situations
where the outcome is failure (a counterexample) rather than success (a correctness
proof). We present a method for symbolic model checking that can lead to significant
time and memory savings for model-checking runs that fail, while occurring only
a small overhead for model-checking runs that succeed. Our method discovers an
error as soon as it cannot be prevented, which can be long before it actually
occurs; for example, the violation of an invariant may become unpreventable many
transitions before the invariant is violated.\r\nThe key observation is that “unpreventability”
is a local property of a single module: an error is unpreventable in a module
state if no environment can prevent it. Therefore, unpreventability is inexpensive
to compute for each module, yet can save much work in the state exploration of
the global, compound system. Based on different degrees of information available
about the environment, we define and implement several notions of “unpreventability,”
including the standard notion of uncontrollability from discrete-event control.
We present experimental results for two examples, a distributed database protocol
and a wireless communication protocol."
acknowledgement: This research was supported in part by the DARPA (NASA) grant NAG2-1214,
the SRC contract 99-TJ-683.003, the MARCO grant 98-DT-660, the DARPA (MARCO) grant
MDA972-99-1-0001, and the NSF CAREER award CCR-9501708.
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: Freddy
full_name: Mang, Freddy
last_name: Mang
citation:
ama: 'De Alfaro L, Henzinger TA, Mang F. Detecting errors before reaching them.
In: Proceedings of the 12th International Conference on Computer Aided Verification.
Vol 1855. Springer; 2000:186-201. doi:10.1007/10722167_17'
apa: 'De Alfaro, L., Henzinger, T. A., & Mang, F. (2000). Detecting errors before
reaching them. In Proceedings of the 12th International Conference on Computer
Aided Verification (Vol. 1855, pp. 186–201). Chicago, IL, USA: Springer. https://doi.org/10.1007/10722167_17'
chicago: De Alfaro, Luca, Thomas A Henzinger, and Freddy Mang. “Detecting Errors
before Reaching Them.” In Proceedings of the 12th International Conference
on Computer Aided Verification, 1855:186–201. Springer, 2000. https://doi.org/10.1007/10722167_17.
ieee: L. De Alfaro, T. A. Henzinger, and F. Mang, “Detecting errors before reaching
them,” in Proceedings of the 12th International Conference on Computer Aided
Verification, Chicago, IL, USA, 2000, vol. 1855, pp. 186–201.
ista: 'De Alfaro L, Henzinger TA, Mang F. 2000. Detecting errors before reaching
them. Proceedings of the 12th International Conference on Computer Aided Verification.
CAV: Computer-Aided Verification, LNCS, vol. 1855, 186–201.'
mla: De Alfaro, Luca, et al. “Detecting Errors before Reaching Them.” Proceedings
of the 12th International Conference on Computer Aided Verification, vol.
1855, Springer, 2000, pp. 186–201, doi:10.1007/10722167_17.
short: L. De Alfaro, T.A. Henzinger, F. Mang, in:, Proceedings of the 12th International
Conference on Computer Aided Verification, Springer, 2000, pp. 186–201.
conference:
end_date: 2000-07-19
location: Chicago, IL, USA
name: 'CAV: Computer-Aided Verification'
start_date: 2000-07-15
date_created: 2018-12-11T12:09:53Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2023-04-13T13:18:06Z
day: '01'
doi: 10.1007/10722167_17
extern: '1'
intvolume: ' 1855'
language:
- iso: eng
month: '01'
oa_version: None
page: 186 - 201
publication: Proceedings of the 12th International Conference on Computer Aided Verification
publication_identifier:
isbn:
- '9783540677703'
publication_status: published
publisher: Springer
publist_id: '70'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Detecting errors before reaching them
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1855
year: '2000'
...
---
_id: '1455'
abstract:
- lang: eng
text: First, a special case of Knaster's problem is proved implying that each symmetric
convex body in ℝ3 admits an inscribed cube. It is deduced from a theorem in equivariant
topology, which says that there is no S4 - equivariant map from SO(3) to S2, where
S4 acts on SO(3) on the right as the rotation group of the cube, and on S2 on
the right as the symmetry group of the regular tetrahedron. Some generalizations
are also given. Second, it is shown how the above non-existence theorem yields
Makeev's conjecture in ℝ3 that each set in ℝ3 of diameter 1 can be covered by
a rhombic dodecahedron, which has distance 1 between its opposite faces. This
reveals an unexpected connection between inscribing cubes into symmetric bodies
and covering sets by rhombic dodecahedra. Finally, a possible application of our
second theorem to the Borsuk problem in ℝ3 is pointed out.
acknowledgement: The research of the first author was partially supported by Trinity
College, Cambridge, and that of all the authors by grants 23444, T-030012 and A
046/96, respectively, from the Hungarian National Foundation for Scientific Research.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Tamas
full_name: Hausel, Tamas
id: 4A0666D8-F248-11E8-B48F-1D18A9856A87
last_name: Hausel
- first_name: Endre
full_name: Makai, Endre
last_name: Makai
- first_name: András
full_name: Szücs, András
last_name: Szücs
citation:
ama: Hausel T, Makai E, Szücs A. Inscribing cubes and covering by rhombic dodecahedra
via equivariant topology. Mathematika. 2000;47(1-2):371-397. doi:10.1112/S0025579300015965
apa: Hausel, T., Makai, E., & Szücs, A. (2000). Inscribing cubes and covering
by rhombic dodecahedra via equivariant topology. Mathematika. University
College London. https://doi.org/10.1112/S0025579300015965
chicago: Hausel, Tamás, Endre Makai, and András Szücs. “Inscribing Cubes and Covering
by Rhombic Dodecahedra via Equivariant Topology.” Mathematika. University
College London, 2000. https://doi.org/10.1112/S0025579300015965.
ieee: T. Hausel, E. Makai, and A. Szücs, “Inscribing cubes and covering by rhombic
dodecahedra via equivariant topology,” Mathematika, vol. 47, no. 1–2. University
College London, pp. 371–397, 2000.
ista: Hausel T, Makai E, Szücs A. 2000. Inscribing cubes and covering by rhombic
dodecahedra via equivariant topology. Mathematika. 47(1–2), 371–397.
mla: Hausel, Tamás, et al. “Inscribing Cubes and Covering by Rhombic Dodecahedra
via Equivariant Topology.” Mathematika, vol. 47, no. 1–2, University College
London, 2000, pp. 371–97, doi:10.1112/S0025579300015965.
short: T. Hausel, E. Makai, A. Szücs, Mathematika 47 (2000) 371–397.
date_created: 2018-12-11T11:52:07Z
date_published: 2000-06-01T00:00:00Z
date_updated: 2023-05-08T08:56:46Z
day: '01'
doi: 10.1112/S0025579300015965
extern: '1'
external_id:
arxiv:
- math/9906066
intvolume: ' 47'
issue: 1-2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/math/9906066
month: '06'
oa: 1
oa_version: Preprint
page: 371 - 397
publication: Mathematika
publication_identifier:
issn:
- 0025-5793
publication_status: published
publisher: University College London
publist_id: '5745'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inscribing cubes and covering by rhombic dodecahedra via equivariant topology
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 47
year: '2000'
...
---
_id: '13437'
abstract:
- lang: eng
text: Liquid/liquid Phase Transfer Catalysis (PTC) reaction of 4-chlorobutyronitrile
with nonenolisable aldehydes leads via an addition-cyclisation reaction sequence
to derivatives of tetrahydrofuran-3-carbonitrile.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Mieczysław
full_name: Macogonkosza, Mieczysław
last_name: Macogonkosza
- first_name: Jacek
full_name: Przyborowski, Jacek
last_name: Przyborowski
- first_name: Rafal
full_name: Klajn, Rafal
id: 8e84690e-1e48-11ed-a02b-a1e6fb8bb53b
last_name: Klajn
- first_name: Andrzej
full_name: Kwast, Andrzej
last_name: Kwast
citation:
ama: Macogonkosza M, Przyborowski J, Klajn R, Kwast A. Simple synthesis of 2-substituted
Tetrahydrofuran-3-carbonitriles. Synlett. 2000;2000(12):1773-1774. doi:10.1055/s-2000-8670
apa: Macogonkosza, M., Przyborowski, J., Klajn, R., & Kwast, A. (2000). Simple
synthesis of 2-substituted Tetrahydrofuran-3-carbonitriles. Synlett. Georg
Thieme Verlag. https://doi.org/10.1055/s-2000-8670
chicago: Macogonkosza, Mieczysław, Jacek Przyborowski, Rafal Klajn, and Andrzej
Kwast. “Simple Synthesis of 2-Substituted Tetrahydrofuran-3-Carbonitriles.” Synlett.
Georg Thieme Verlag, 2000. https://doi.org/10.1055/s-2000-8670.
ieee: M. Macogonkosza, J. Przyborowski, R. Klajn, and A. Kwast, “Simple synthesis
of 2-substituted Tetrahydrofuran-3-carbonitriles,” Synlett, vol. 2000,
no. 12. Georg Thieme Verlag, pp. 1773–1774, 2000.
ista: Macogonkosza M, Przyborowski J, Klajn R, Kwast A. 2000. Simple synthesis of
2-substituted Tetrahydrofuran-3-carbonitriles. Synlett. 2000(12), 1773–1774.
mla: Macogonkosza, Mieczysław, et al. “Simple Synthesis of 2-Substituted Tetrahydrofuran-3-Carbonitriles.”
Synlett, vol. 2000, no. 12, Georg Thieme Verlag, 2000, pp. 1773–74, doi:10.1055/s-2000-8670.
short: M. Macogonkosza, J. Przyborowski, R. Klajn, A. Kwast, Synlett 2000 (2000)
1773–1774.
date_created: 2023-08-01T10:39:48Z
date_published: 2000-12-01T00:00:00Z
date_updated: 2023-08-02T07:54:46Z
day: '01'
doi: 10.1055/s-2000-8670
extern: '1'
intvolume: ' 2000'
issue: '12'
keyword:
- Organic Chemistry
language:
- iso: eng
month: '12'
oa_version: None
page: 1773-1774
publication: Synlett
publication_identifier:
eissn:
- 1437-2096
issn:
- 0936-5214
publication_status: published
publisher: Georg Thieme Verlag
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple synthesis of 2-substituted Tetrahydrofuran-3-carbonitriles
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2000
year: '2000'
...
---
_id: '11802'
abstract:
- lang: eng
text: In this paper we survey algorithmic aspects of Web information retrieval.
As an example, we discuss ranking of search engine results using connectivity
analysis.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. Web information retrieval - an algorithmic perspective. In:
8th Annual European Symposium on Algorithms. Vol 1879. Springer Nature;
2000:1–8. doi:10.1007/3-540-45253-2_1'
apa: 'Henzinger, M. H. (2000). Web information retrieval - an algorithmic perspective.
In 8th Annual European Symposium on Algorithms (Vol. 1879, pp. 1–8). Saarbrücken,
Germany: Springer Nature. https://doi.org/10.1007/3-540-45253-2_1'
chicago: Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.”
In 8th Annual European Symposium on Algorithms, 1879:1–8. Springer Nature,
2000. https://doi.org/10.1007/3-540-45253-2_1.
ieee: M. H. Henzinger, “Web information retrieval - an algorithmic perspective,”
in 8th Annual European Symposium on Algorithms, Saarbrücken, Germany, 2000,
vol. 1879, pp. 1–8.
ista: 'Henzinger MH. 2000. Web information retrieval - an algorithmic perspective.
8th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms,
LNCS, vol. 1879, 1–8.'
mla: Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.”
8th Annual European Symposium on Algorithms, vol. 1879, Springer Nature,
2000, pp. 1–8, doi:10.1007/3-540-45253-2_1.
short: M.H. Henzinger, in:, 8th Annual European Symposium on Algorithms, Springer
Nature, 2000, pp. 1–8.
conference:
end_date: 2000-09-08
location: Saarbrücken, Germany
name: 'ESA: European Symposium on Algorithms'
start_date: 2000-09-05
date_created: 2022-08-11T13:25:07Z
date_published: 2000-09-01T00:00:00Z
date_updated: 2023-02-13T12:08:21Z
day: '01'
doi: 10.1007/3-540-45253-2_1
extern: '1'
intvolume: ' 1879'
language:
- iso: eng
month: '09'
oa_version: None
page: 1–8
publication: 8th Annual European Symposium on Algorithms
publication_identifier:
eisbn:
- '9783540452539'
eissn:
- 1611-3349
isbn:
- '9783540410041'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Web information retrieval - an algorithmic perspective
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1879
year: '2000'
...