--- _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' ...