---
_id: '4594'
abstract:
- lang: eng
text: |
The authors introduce two-way timed automata-timed automata that can move back and forth while reading a timed word. Two-wayness in its unrestricted form leads, like nondeterminism, to the undecidability of language inclusion. However, if they restrict the number of times an input symbol may be revisited, then two-wayness is both harmless and desirable. The authors show that the resulting class of bounded two-way deterministic timed automata is closed under all boolean operations, has decidable (PSPACE-complete) emptiness and inclusion problems, and subsumes all decidable real-time logics we know. They obtain a strict hierarchy of real-time properties: deterministic timed automata can accept more languages as the bound on the number of times an input symbol may be revisited is increased. This hierarchy is also enforced by the number of alternations between past and future operators in temporal logic. The combination of the results leads to a decision procedure for a real-time logic with past operators
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Alur R, Henzinger TA. Back to the future: Towards a theory of timed regular
languages. In: IEEE; 1992:177-186. doi:10.1109/SFCS.1992.267774'
apa: 'Alur, R., & Henzinger, T. A. (1992). Back to the future: Towards a theory
of timed regular languages (pp. 177–186). Presented at the FOCS: Foundations of
Computer Science, IEEE. https://doi.org/10.1109/SFCS.1992.267774'
chicago: 'Alur, Rajeev, and Thomas A Henzinger. “Back to the Future: Towards a Theory
of Timed Regular Languages,” 177–86. IEEE, 1992. https://doi.org/10.1109/SFCS.1992.267774.'
ieee: 'R. Alur and T. A. Henzinger, “Back to the future: Towards a theory of timed
regular languages,” presented at the FOCS: Foundations of Computer Science, 1992,
pp. 177–186.'
ista: 'Alur R, Henzinger TA. 1992. Back to the future: Towards a theory of timed
regular languages. FOCS: Foundations of Computer Science 177–186.'
mla: 'Alur, Rajeev, and Thomas A. Henzinger. *Back to the Future: Towards a Theory
of Timed Regular Languages*. IEEE, 1992, pp. 177–86, doi:10.1109/SFCS.1992.267774.'
short: R. Alur, T.A. Henzinger, in:, IEEE, 1992, pp. 177–186.
conference:
name: 'FOCS: Foundations of Computer Science'
date_created: 2018-12-11T12:09:39Z
date_published: 1992-01-01T00:00:00Z
date_updated: 2019-08-02T12:38:34Z
day: '01'
doi: 10.1109/SFCS.1992.267774
extern: 1
main_file_link:
- open_access: '0'
url: http://pub.ist.ac.at/~tah/Publications/back_to_the_future.pdf
month: '01'
page: 177 - 186
publication_status: published
publisher: IEEE
publist_id: '115'
quality_controlled: 0
status: public
title: 'Back to the future: Towards a theory of timed regular languages'
type: conference
year: '1992'
...
---
_id: '3566'
alternative_title:
- DIMACS Series in Discrete Mathematics and Theoretical Computer Science
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 'Edelsbrunner H, Sharir M. A hyperplane incidence problem with applications
to counting distances. In: *Applied Geometry and Discrete Mathematics: The Victor
Klee Festschrift*. Vol 4. American Mathematical Society; 1991:253-263.'
apa: 'Edelsbrunner, H., & Sharir, M. (1991). A hyperplane incidence problem
with applications to counting distances. In *Applied Geometry and Discrete Mathematics:
The Victor Klee Festschrift* (Vol. 4, pp. 253–263). American Mathematical Society.'
chicago: 'Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem
with Applications to Counting Distances.” In *Applied Geometry and Discrete
Mathematics: The Victor Klee Festschrift*, 4:253–63. American Mathematical
Society, 1991.'
ieee: 'H. Edelsbrunner and M. Sharir, “A hyperplane incidence problem with applications
to counting distances,” in *Applied Geometry and Discrete Mathematics: The Victor
Klee Festschrift*, vol. 4, American Mathematical Society, 1991, pp. 253–263.'
ista: 'Edelsbrunner H, Sharir M. 1991. A hyperplane incidence problem with applications
to counting distances. Applied Geometry and Discrete Mathematics: The Victor Klee
Festschrift. , DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, vol. 4. 253–263.'
mla: 'Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with
Applications to Counting Distances.” *Applied Geometry and Discrete Mathematics:
The Victor Klee Festschrift*, vol. 4, American Mathematical Society, 1991,
pp. 253–63.'
short: 'H. Edelsbrunner, M. Sharir, in:, Applied Geometry and Discrete Mathematics:
The Victor Klee Festschrift, American Mathematical Society, 1991, pp. 253–263.'
date_created: 2018-12-11T12:04:00Z
date_published: 1991-04-01T00:00:00Z
date_updated: 2019-04-26T07:22:30Z
day: '01'
extern: 1
intvolume: ' 4'
main_file_link:
- open_access: '0'
url: http://www.cs.duke.edu/~edels/Papers/1991-B-01-HyperplaneIncidence.pdf
month: '04'
page: 253 - 263
publication: 'Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift'
publication_status: published
publisher: American Mathematical Society
publist_id: '2819'
quality_controlled: 0
status: public
title: A hyperplane incidence problem with applications to counting distances
type: book_chapter
volume: 4
year: '1991'
...
---
_id: '3648'
abstract:
- lang: eng
text: 'We investigate the probability of fixation of a chromosome rearrangement
in a subdivided population, concentrating on the limit where migration is so large
relative to selection (m ≫ s) that the population can be thought of as being continuously
distributed. We study two demes, and one- and two-dimensional populations. For
two demes, the probability of fixation in the limit of high migration approximates
that of a population with twice the size of a single deme: migration therefore
greatly reduces the fixation probability. However, this behavior does not extend
to a large array of demes. Then, the fixation probability depends primarily on
neighborhood size (Nb), and may be appreciable even with strong selection and
free gene flow (≈exp(-B·Nb) in one dimension, ≈exp(-B\cdotNb) in two dimensions).
Our results are close to those for the more tractable case of a polygenic character
under disruptive selection.'
author:
- first_name: Nicholas H
full_name: Nicholas Barton
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Shahin
full_name: Rouhani, Shahin
last_name: Rouhani
citation:
ama: Barton NH, Rouhani S. The probability of fixation of a new karyotype in a continuous
population. *Evolution*. 1991;45(3):499-517.
apa: Barton, N. H., & Rouhani, S. (1991). The probability of fixation of a new
karyotype in a continuous population. *Evolution*, *45*(3), 499–517.
chicago: 'Barton, Nicholas H, and Shahin Rouhani. “The Probability of Fixation of
a New Karyotype in a Continuous Population.” *Evolution* 45, no. 3 (1991):
499–517.'
ieee: N. H. Barton and S. Rouhani, “The probability of fixation of a new karyotype
in a continuous population,” *Evolution*, vol. 45, no. 3, pp. 499–517, 1991.
ista: Barton NH, Rouhani S. 1991. The probability of fixation of a new karyotype
in a continuous population. Evolution. 45(3), 499–517.
mla: Barton, Nicholas H., and Shahin Rouhani. “The Probability of Fixation of a
New Karyotype in a Continuous Population.” *Evolution*, vol. 45, no. 3, Wiley-Blackwell,
1991, pp. 499–517.
short: N.H. Barton, S. Rouhani, Evolution 45 (1991) 499–517.
date_created: 2018-12-11T12:04:25Z
date_published: 1991-05-01T00:00:00Z
date_updated: 2019-04-26T07:22:32Z
day: '01'
extern: 1
intvolume: ' 45'
issue: '3'
main_file_link:
- open_access: '0'
url: http://www.jstor.org/stable/2409908
month: '05'
page: 499 - 517
publication: Evolution
publication_status: published
publisher: Wiley-Blackwell
publist_id: '2735'
quality_controlled: 0
status: public
title: The probability of fixation of a new karyotype in a continuous population
type: journal_article
volume: 45
year: '1991'
...
---
_id: '4052'
abstract:
- lang: eng
text: This paper describes an effective procedure for stratifying a real semi-algebraic
set into cells of constant description size. The attractive feature of our method
is that the number of cells produced is singly exponential in the number of input
variables. This compares favorably with the doubly exponential size of Collins'
decomposition. Unlike Collins' construction, however, our scheme does not produce
a cell complex but only a smooth stratification. Nevertheless, we are able to
apply our results in interesting ways to problems of point location and geometric
optimization.
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas J
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. A singly exponential stratification
scheme for real semi-algebraic varieties and its applications. *Theoretical
Computer Science*. 1991;84(1):77-105. doi:10.1016/0304-3975(91)90261-Y
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1991). A singly
exponential stratification scheme for real semi-algebraic varieties and its applications.
*Theoretical Computer Science*, *84*(1), 77–105. https://doi.org/10.1016/0304-3975(91)90261-Y
chicago: 'Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties
and Its Applications.” *Theoretical Computer Science* 84, no. 1 (1991): 77–105.
https://doi.org/10.1016/0304-3975(91)90261-Y.'
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “A singly exponential
stratification scheme for real semi-algebraic varieties and its applications,”
*Theoretical Computer Science*, vol. 84, no. 1, pp. 77–105, 1991.
ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential
stratification scheme for real semi-algebraic varieties and its applications.
Theoretical Computer Science. 84(1), 77–105.
mla: Chazelle, Bernard, et al. “A Singly Exponential Stratification Scheme for Real
Semi-Algebraic Varieties and Its Applications.” *Theoretical Computer Science*,
vol. 84, no. 1, Elsevier, 1991, pp. 77–105, doi:10.1016/0304-3975(91)90261-Y.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Theoretical Computer
Science 84 (1991) 77–105.
date_created: 2018-12-11T12:06:39Z
date_published: 1991-07-22T00:00:00Z
date_updated: 2019-04-26T07:22:39Z
day: '22'
doi: 10.1016/0304-3975(91)90261-Y
extern: 1
intvolume: ' 84'
issue: '1'
month: '07'
page: 77 - 105
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '2073'
quality_controlled: 0
status: public
title: A singly exponential stratification scheme for real semi-algebraic varieties
and its applications
type: journal_article
volume: 84
year: '1991'
...
---
_id: '4057'
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Edelsbrunner H. Corrigendum. *Journal of Computer and System Sciences*.
1991;42(2):249-251. doi:10.1016/0022-0000(91)90013-U
apa: Edelsbrunner, H. (1991). Corrigendum. *Journal of Computer and System Sciences*,
*42*(2), 249–251. https://doi.org/10.1016/0022-0000(91)90013-U
chicago: 'Edelsbrunner, Herbert. “Corrigendum.” *Journal of Computer and System
Sciences* 42, no. 2 (1991): 249–51. https://doi.org/10.1016/0022-0000(91)90013-U.'
ieee: H. Edelsbrunner, “Corrigendum,” *Journal of Computer and System Sciences*,
vol. 42, no. 2, pp. 249–251, 1991.
ista: Edelsbrunner H. 1991. Corrigendum. Journal of Computer and System Sciences.
42(2), 249–251.
mla: Edelsbrunner, Herbert. “Corrigendum.” *Journal of Computer and System Sciences*,
vol. 42, no. 2, Elsevier, 1991, pp. 249–51, doi:10.1016/0022-0000(91)90013-U.
short: H. Edelsbrunner, Journal of Computer and System Sciences 42 (1991) 249–251.
date_created: 2018-12-11T12:06:41Z
date_published: 1991-04-01T00:00:00Z
date_updated: 2019-04-26T07:22:39Z
day: '01'
doi: 10.1016/0022-0000(91)90013-U
extern: 1
intvolume: ' 42'
issue: '2'
month: '04'
page: 249 - 251
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '2071'
quality_controlled: 0
status: public
title: Corrigendum
type: journal_article
volume: 42
year: '1991'
...