---
_id: '3797'
article_processing_charge: No
author:
- first_name: Wolfgang
full_name: Bauer, Wolfgang
last_name: Bauer
- first_name: Marco
full_name: Kleine Berkenbusch, Marco
last_name: Kleine Berkenbusch
- first_name: Mark Tobias
full_name: Bollenbach, Mark Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
citation:
ama: 'Bauer W, Kleine Berkenbusch M, Bollenbach MT. Breaking atomic nuclei into
little pieces: evidence for a phase transition. Revista Mexicana De Fisica.
2003;49(4):1-6.'
apa: 'Bauer, W., Kleine Berkenbusch, M., & Bollenbach, M. T. (2003). Breaking
atomic nuclei into little pieces: evidence for a phase transition. Revista
Mexicana De Fisica. Sociedad Mexicana de Física.'
chicago: 'Bauer, Wolfgang, Marco Kleine Berkenbusch, and Mark Tobias Bollenbach.
“Breaking Atomic Nuclei into Little Pieces: Evidence for a Phase Transition.”
Revista Mexicana De Fisica. Sociedad Mexicana de Física, 2003.'
ieee: 'W. Bauer, M. Kleine Berkenbusch, and M. T. Bollenbach, “Breaking atomic nuclei
into little pieces: evidence for a phase transition,” Revista Mexicana De Fisica,
vol. 49, no. 4. Sociedad Mexicana de Física, pp. 1–6, 2003.'
ista: 'Bauer W, Kleine Berkenbusch M, Bollenbach MT. 2003. Breaking atomic nuclei
into little pieces: evidence for a phase transition. Revista Mexicana De Fisica.
49(4), 1–6.'
mla: 'Bauer, Wolfgang, et al. “Breaking Atomic Nuclei into Little Pieces: Evidence
for a Phase Transition.” Revista Mexicana De Fisica, vol. 49, no. 4, Sociedad
Mexicana de Física, 2003, pp. 1–6.'
short: W. Bauer, M. Kleine Berkenbusch, M.T. Bollenbach, Revista Mexicana De Fisica
49 (2003) 1–6.
date_created: 2018-12-11T12:05:13Z
date_published: 2003-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:16Z
day: '01'
extern: '1'
intvolume: ' 49'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 6
publication: Revista Mexicana De Fisica
publication_status: published
publisher: Sociedad Mexicana de Física
publist_id: '2413'
status: public
title: 'Breaking atomic nuclei into little pieces: evidence for a phase transition'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2003'
...
---
_id: '3897'
abstract:
- lang: eng
text: Many verification, planning, and control problems can be modeled as games
played on state-transition graphs by one or two players whose conflicting goals
are to form a path in the graph. The focus here is on simple stochastic parity
games, that is, two-player games with turn-based probabilistic transitions and
omega-regular objectives formalized as parity (Rabin chain) winning conditions.
An efficient translation from simple stochastic parity games to nonstochastic
parity games is given. As many algorithms are known for solving the latter, the
translation yields efficient algorithms for computing the states of a simple stochastic
parity game from which a player can win with probability 1. An important special
case of simple stochastic parity games are the Markov decision processes with
Buchi objectives. For this special case a first provably subquadratic algorithm
is given for computing the states from which the single player has a strategy
to achieve a Buchi objective with probability 1. For game graphs with m edges
the algorithm works in time O(mrootm). Interestingly, a similar technique sheds
light on the question of the computational complexity of solving simple Buchi
games and yields the first provably subquadratic algorithm, with a running time
of O(n(2)/log n) for game graphs with n vertices and O(n) edges.
acknowledgement: This research was supported in part by the DARPA grant F33615-C-98-3614,
the ONR grant N00014-02-1-0671, the NSF grants CCR-9988172 and CCR-0225610, and
the Polish KBN grant 7-T11C-027-20.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Marcin
full_name: Jurdziński, Marcin
last_name: Jurdziński
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Jurdziński M, Henzinger TA. Simple stochastic parity games.
In: Vol 2803. Springer; 2003:100-113. doi:10.1007/978-3-540-45220-1_11'
apa: 'Chatterjee, K., Jurdziński, M., & Henzinger, T. A. (2003). Simple stochastic
parity games (Vol. 2803, pp. 100–113). Presented at the CSL: Computer Science
Logic, Springer. https://doi.org/10.1007/978-3-540-45220-1_11'
chicago: Chatterjee, Krishnendu, Marcin Jurdziński, and Thomas A Henzinger. “Simple
Stochastic Parity Games,” 2803:100–113. Springer, 2003. https://doi.org/10.1007/978-3-540-45220-1_11.
ieee: 'K. Chatterjee, M. Jurdziński, and T. A. Henzinger, “Simple stochastic parity
games,” presented at the CSL: Computer Science Logic, 2003, vol. 2803, pp. 100–113.'
ista: 'Chatterjee K, Jurdziński M, Henzinger TA. 2003. Simple stochastic parity
games. CSL: Computer Science Logic, LNCS, vol. 2803, 100–113.'
mla: Chatterjee, Krishnendu, et al. Simple Stochastic Parity Games. Vol.
2803, Springer, 2003, pp. 100–13, doi:10.1007/978-3-540-45220-1_11.
short: K. Chatterjee, M. Jurdziński, T.A. Henzinger, in:, Springer, 2003, pp. 100–113.
conference:
name: 'CSL: Computer Science Logic'
date_created: 2018-12-11T12:05:46Z
date_published: 2003-08-18T00:00:00Z
date_updated: 2021-01-12T07:53:02Z
day: '18'
doi: 10.1007/978-3-540-45220-1_11
extern: 1
intvolume: ' 2803'
month: '08'
page: 100 - 113
publication_status: published
publisher: Springer
publist_id: '2259'
quality_controlled: 0
status: public
title: Simple stochastic parity games
type: conference
volume: 2803
year: '2003'
...
---
_id: '3898'
abstract:
- lang: eng
text: We study the problem of determining stack boundedness and the exact maximum
stack size for three classes of interrupt-driven programs. Interrupt-driven programs
axe used in many real-time applications that require responsive interrupt handling.
In order to ensure responsiveness, programmers often enable interrupt processing
in the body of lower-priority interrupt handlers. In such programs a programming
error can allow interrupt handlers to be interrupted in cyclic fashion to lead
to an unbounded stack, causing the system to crash. For a restricted class of
interrupt-driven programs, we show that there is a polynomial-time procedure to
check stack boundedness, while determining the exact maximum stack size is PSPACE-complete.
For a larger class of programs, the two problems are both PSPACE-complete, and
for the largest class of programs we consider, the two problems are PSPACE-hard
and can be solved in exponential time.
acknowledgement: Jens Palsberg, Di Ma, and Tian Zhao were supported by the NSF ITR
award 0112628. Thomas A. Henzinger, Krishnendu Chatterjee, and Rupak Majumdar were
supported by the AFOSR grant F49620-00-1-0327, the DARPA grants F33615-C-98-3614
and F33615-00-C-1693, the MARCO grant 98-DT-660, and the NSF grants CCR-0208875
and CCR-0085949.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Di
full_name: Ma, Di
last_name: Ma
- first_name: Ritankar
full_name: Majumdar, Ritankar S
last_name: Majumdar
- first_name: Tian
full_name: Zhao, Tian
last_name: Zhao
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jens
full_name: Palsberg, Jens
last_name: Palsberg
citation:
ama: 'Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. Stack size
analysis for interrupt-driven programs. In: Vol 2694. Springer; 2003:109-126.
doi:10.1007/3-540-44898-5_7'
apa: 'Chatterjee, K., Ma, D., Majumdar, R., Zhao, T., Henzinger, T. A., & Palsberg,
J. (2003). Stack size analysis for interrupt-driven programs (Vol. 2694, pp. 109–126).
Presented at the SAS: Static Analysis Symposium, Springer. https://doi.org/10.1007/3-540-44898-5_7'
chicago: Chatterjee, Krishnendu, Di Ma, Ritankar Majumdar, Tian Zhao, Thomas A Henzinger,
and Jens Palsberg. “Stack Size Analysis for Interrupt-Driven Programs,” 2694:109–26.
Springer, 2003. https://doi.org/10.1007/3-540-44898-5_7.
ieee: 'K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T. A. Henzinger, and J. Palsberg,
“Stack size analysis for interrupt-driven programs,” presented at the SAS: Static
Analysis Symposium, 2003, vol. 2694, pp. 109–126.'
ista: 'Chatterjee K, Ma D, Majumdar R, Zhao T, Henzinger TA, Palsberg J. 2003. Stack
size analysis for interrupt-driven programs. SAS: Static Analysis Symposium, LNCS,
vol. 2694, 109–126.'
mla: Chatterjee, Krishnendu, et al. Stack Size Analysis for Interrupt-Driven
Programs. Vol. 2694, Springer, 2003, pp. 109–26, doi:10.1007/3-540-44898-5_7.
short: K. Chatterjee, D. Ma, R. Majumdar, T. Zhao, T.A. Henzinger, J. Palsberg,
in:, Springer, 2003, pp. 109–126.
conference:
name: 'SAS: Static Analysis Symposium'
date_created: 2018-12-11T12:05:46Z
date_published: 2003-05-28T00:00:00Z
date_updated: 2021-01-12T07:53:02Z
day: '28'
doi: 10.1007/3-540-44898-5_7
extern: 1
intvolume: ' 2694'
month: '05'
page: 109 - 126
publication_status: published
publisher: Springer
publist_id: '2260'
quality_controlled: 0
status: public
title: Stack size analysis for interrupt-driven programs
type: conference
volume: 2694
year: '2003'
...
---
_id: '3993'
abstract:
- lang: eng
text: We present algorithms for constructing a hierarchy of increasingly coarse
Morse-Smale complexes that decompose a piecewise linear 2-manifold. While these
complexes are defined only in the smooth category, we extend the construction
to the piecewise linearcategory by ensuring structural integrity and simulating
differentiability. We then simplify Morse-Smale complexes by canceling pairs of
critical points in order of increasing persistence.
acknowledgement: Partially supported by ARO under Grant DAAG55-98-1-0177, NSF under
Grants CCR-97-12088, EIA-9972879 and CCR-00-86013.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Harer, John
last_name: Harer
- first_name: Afra
full_name: Zomorodian, Afra
last_name: Zomorodian
citation:
ama: Edelsbrunner H, Harer J, Zomorodian A. Hierarchical Morse-Smale complexes for
piecewise linear 2-manifolds. Discrete & Computational Geometry. 2003;30(1):87-107.
doi:10.1007/s00454-003-2926-5
apa: Edelsbrunner, H., Harer, J., & Zomorodian, A. (2003). Hierarchical Morse-Smale
complexes for piecewise linear 2-manifolds. Discrete & Computational Geometry.
Springer. https://doi.org/10.1007/s00454-003-2926-5
chicago: Edelsbrunner, Herbert, John Harer, and Afra Zomorodian. “Hierarchical Morse-Smale
Complexes for Piecewise Linear 2-Manifolds.” Discrete & Computational Geometry.
Springer, 2003. https://doi.org/10.1007/s00454-003-2926-5.
ieee: H. Edelsbrunner, J. Harer, and A. Zomorodian, “Hierarchical Morse-Smale complexes
for piecewise linear 2-manifolds,” Discrete & Computational Geometry,
vol. 30, no. 1. Springer, pp. 87–107, 2003.
ista: Edelsbrunner H, Harer J, Zomorodian A. 2003. Hierarchical Morse-Smale complexes
for piecewise linear 2-manifolds. Discrete & Computational Geometry. 30(1),
87–107.
mla: Edelsbrunner, Herbert, et al. “Hierarchical Morse-Smale Complexes for Piecewise
Linear 2-Manifolds.” Discrete & Computational Geometry, vol. 30, no.
1, Springer, 2003, pp. 87–107, doi:10.1007/s00454-003-2926-5.
short: H. Edelsbrunner, J. Harer, A. Zomorodian, Discrete & Computational Geometry
30 (2003) 87–107.
date_created: 2018-12-11T12:06:19Z
date_published: 2003-07-01T00:00:00Z
date_updated: 2021-01-12T07:53:43Z
day: '01'
doi: 10.1007/s00454-003-2926-5
extern: 1
intvolume: ' 30'
issue: '1'
month: '07'
page: 87 - 107
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '2134'
quality_controlled: 0
status: public
title: Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds
type: journal_article
volume: 30
year: '2003'
...
---
_id: '3994'
abstract:
- lang: eng
text: The body defined by a finite collection of disks is a subset of the plane
bounded by a tangent continuous curve, which we call the skin. We give analytic
formulas for the area, the perimeter, the area derivative, and the perimeter derivative
of the body. Given the filtrations of the Delaunay triangulation and the Voronoi
diagram of the disks, all formulas can be evaluated in time proportional to the
number of disks.
acknowledgement: NSF under grant DMS-98-73945, ARO under grant DAAG55-98-1-0177 and
by NSF under grants CCR- 97-12088, EIA-9972879, and CCR-00-86013.
author:
- first_name: Ho
full_name: Cheng, Ho-Lun
last_name: Cheng
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Cheng H, Edelsbrunner H. Area, perimeter and derivatives of a skin curve.
Computational Geometry: Theory and Applications. 2003;26(2):173-192. doi:10.1016/S0925-7721(02)00124-4'
apa: 'Cheng, H., & Edelsbrunner, H. (2003). Area, perimeter and derivatives
of a skin curve. Computational Geometry: Theory and Applications. Elsevier.
https://doi.org/10.1016/S0925-7721(02)00124-4'
chicago: 'Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives
of a Skin Curve.” Computational Geometry: Theory and Applications. Elsevier,
2003. https://doi.org/10.1016/S0925-7721(02)00124-4.'
ieee: 'H. Cheng and H. Edelsbrunner, “Area, perimeter and derivatives of a skin
curve,” Computational Geometry: Theory and Applications, vol. 26, no. 2.
Elsevier, pp. 173–192, 2003.'
ista: 'Cheng H, Edelsbrunner H. 2003. Area, perimeter and derivatives of a skin
curve. Computational Geometry: Theory and Applications. 26(2), 173–192.'
mla: 'Cheng, Ho, and Herbert Edelsbrunner. “Area, Perimeter and Derivatives of a
Skin Curve.” Computational Geometry: Theory and Applications, vol. 26,
no. 2, Elsevier, 2003, pp. 173–92, doi:10.1016/S0925-7721(02)00124-4.'
short: 'H. Cheng, H. Edelsbrunner, Computational Geometry: Theory and Applications
26 (2003) 173–192.'
date_created: 2018-12-11T12:06:20Z
date_published: 2003-10-01T00:00:00Z
date_updated: 2021-01-12T07:53:43Z
day: '01'
doi: 10.1016/S0925-7721(02)00124-4
extern: 1
intvolume: ' 26'
issue: '2'
month: '10'
page: 173 - 192
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '2135'
quality_controlled: 0
status: public
title: Area, perimeter and derivatives of a skin curve
type: journal_article
volume: 26
year: '2003'
...