[{"publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"month":"06","doi":"10.1007/BF01840404","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF01840404"}],"quality_controlled":"1","publist_id":"2049","extern":"1","author":[{"last_name":"Dobkin","first_name":"David","full_name":"Dobkin, David"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Overmars","first_name":"Mark","full_name":"Overmars, Mark"}],"volume":5,"date_created":"2018-12-11T12:06:47Z","date_updated":"2022-02-21T10:55:13Z","acknowledgement":"The first author is pleased to acknowledge support by the National Science Foundation under Grant CCR-8700917. The research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the National Science Foundatio","year":"1990","publisher":"Springer","publication_status":"published","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"1990-06-01T00:00:00Z","citation":{"ama":"Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons. Algorithmica. 1990;5(4):561-571. doi:10.1007/BF01840404","ista":"Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons. Algorithmica. 5(4), 561–571.","ieee":"D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,” Algorithmica, vol. 5, no. 4. Springer, pp. 561–571, 1990.","apa":"Dobkin, D., Edelsbrunner, H., & Overmars, M. (1990). Searching for empty convex polygons. Algorithmica. Springer. https://doi.org/10.1007/BF01840404","mla":"Dobkin, David, et al. “Searching for Empty Convex Polygons.” Algorithmica, vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:10.1007/BF01840404.","short":"D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.","chicago":"Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for Empty Convex Polygons.” Algorithmica. Springer, 1990. https://doi.org/10.1007/BF01840404."},"publication":"Algorithmica","page":"561 - 571","article_type":"original","issue":"4","abstract":[{"lang":"eng","text":"A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned."}],"type":"journal_article","oa_version":"None","_id":"4075","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 5","title":"Searching for empty convex polygons","status":"public"},{"author":[{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","last_name":"Barton","first_name":"Nicholas H"},{"full_name":"Clark, A.","last_name":"Clark","first_name":"A."}],"oa_version":"None","date_created":"2018-12-11T12:08:11Z","date_updated":"2022-02-16T10:49:05Z","year":"1990","_id":"4311","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","editor":[{"full_name":"Wöhrmann, Klaus","last_name":"Wöhrmann","first_name":"Klaus"},{"first_name":"Subodh","last_name":"Jain","full_name":"Jain, Subodh"}],"publisher":"Springer","status":"public","title":"Population structure and processes in evolution","publication_status":"published","publist_id":"1748","extern":"1","type":"book_chapter","date_published":"1990-01-01T00:00:00Z","doi":"10.1007/978-3-642-74474-7_5","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://link.springer.com/book/10.1007/978-3-642-74474-7"}],"citation":{"ista":"Barton NH, Clark A. 1990.Population structure and processes in evolution. In: Population biology: Ecological and evolutionary viewpoints. , 115–174.","apa":"Barton, N. H., & Clark, A. (1990). Population structure and processes in evolution. In K. Wöhrmann & S. Jain (Eds.), Population biology: Ecological and evolutionary viewpoints (pp. 115–174). Springer. https://doi.org/10.1007/978-3-642-74474-7_5","ieee":"N. H. Barton and A. Clark, “Population structure and processes in evolution,” in Population biology: Ecological and evolutionary viewpoints, K. Wöhrmann and S. Jain, Eds. Springer, 1990, pp. 115–174.","ama":"Barton NH, Clark A. Population structure and processes in evolution. In: Wöhrmann K, Jain S, eds. Population Biology: Ecological and Evolutionary Viewpoints. Springer; 1990:115-174. doi:10.1007/978-3-642-74474-7_5","chicago":"Barton, Nicholas H, and A. Clark. “Population Structure and Processes in Evolution.” In Population Biology: Ecological and Evolutionary Viewpoints, edited by Klaus Wöhrmann and Subodh Jain, 115–74. Springer, 1990. https://doi.org/10.1007/978-3-642-74474-7_5.","mla":"Barton, Nicholas H., and A. Clark. “Population Structure and Processes in Evolution.” Population Biology: Ecological and Evolutionary Viewpoints, edited by Klaus Wöhrmann and Subodh Jain, Springer, 1990, pp. 115–74, doi:10.1007/978-3-642-74474-7_5.","short":"N.H. Barton, A. Clark, in:, K. Wöhrmann, S. Jain (Eds.), Population Biology: Ecological and Evolutionary Viewpoints, Springer, 1990, pp. 115–174."},"publication":"Population biology: Ecological and evolutionary viewpoints","page":"115 - 174","quality_controlled":"1","article_processing_charge":"No","publication_identifier":{"isbn":[" 978-3642744761"]},"day":"01","month":"01"},{"intvolume":" 346","publisher":"Nature Publishing Group","publication_status":"published","title":"The language of the genes","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4310","year":"1990","volume":346,"oa_version":"None","date_updated":"2022-02-16T10:51:50Z","date_created":"2018-12-11T12:08:11Z","author":[{"first_name":"Nicholas H","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H"},{"full_name":"Jones, Steve","last_name":"Jones","first_name":"Steve"}],"type":"journal_article","extern":"1","publist_id":"1749","page":"415 - 416","quality_controlled":"1","article_type":"original","main_file_link":[{"url":"https://www.nature.com/articles/346415a0"}],"citation":{"ama":"Barton NH, Jones S. The language of the genes. Nature. 1990;346:415-416. doi:10.1038/346415a0","apa":"Barton, N. H., & Jones, S. (1990). The language of the genes. Nature. Nature Publishing Group. https://doi.org/10.1038/346415a0","ieee":"N. H. Barton and S. Jones, “The language of the genes,” Nature, vol. 346. Nature Publishing Group, pp. 415–416, 1990.","ista":"Barton NH, Jones S. 1990. The language of the genes. Nature. 346, 415–416.","short":"N.H. Barton, S. Jones, Nature 346 (1990) 415–416.","mla":"Barton, Nicholas H., and Steve Jones. “The Language of the Genes.” Nature, vol. 346, Nature Publishing Group, 1990, pp. 415–16, doi:10.1038/346415a0.","chicago":"Barton, Nicholas H, and Steve Jones. “The Language of the Genes.” Nature. Nature Publishing Group, 1990. https://doi.org/10.1038/346415a0."},"publication":"Nature","language":[{"iso":"eng"}],"date_published":"1990-08-02T00:00:00Z","doi":"10.1038/346415a0","scopus_import":"1","publication_identifier":{"eissn":["1476-4687"],"issn":["0028-0836"]},"article_processing_charge":"No","day":"02","month":"08"},{"language":[{"iso":"eng"}],"date_published":"1990-01-01T00:00:00Z","doi":"10.1109/JCIT.1990.128356","conference":{"location":"Jerusalem, Israel","start_date":"1990-10-22","end_date":"1990-10-25","name":"JCIT: Jerusalem Conference on Information Technology"},"page":"717 - 730","quality_controlled":"1","citation":{"short":"T.A. Henzinger, Z. Manna, A. Pnueli, in:, Proceedings of the 5th Jerusalem Conference on Information Technology, IEEE, 1990, pp. 717–730.","mla":"Henzinger, Thomas A., et al. “An Interleaving Model for Real Time.” Proceedings of the 5th Jerusalem Conference on Information Technology, IEEE, 1990, pp. 717–30, doi:10.1109/JCIT.1990.128356.","chicago":"Henzinger, Thomas A, Zohar Manna, and Amir Pnueli. “An Interleaving Model for Real Time.” In Proceedings of the 5th Jerusalem Conference on Information Technology, 717–30. IEEE, 1990. https://doi.org/10.1109/JCIT.1990.128356.","ama":"Henzinger TA, Manna Z, Pnueli A. An interleaving model for real time. In: Proceedings of the 5th Jerusalem Conference on Information Technology. IEEE; 1990:717-730. doi:10.1109/JCIT.1990.128356","ieee":"T. A. Henzinger, Z. Manna, and A. Pnueli, “An interleaving model for real time,” in Proceedings of the 5th Jerusalem Conference on Information Technology, Jerusalem, Israel, 1990, pp. 717–730.","apa":"Henzinger, T. A., Manna, Z., & Pnueli, A. (1990). An interleaving model for real time. In Proceedings of the 5th Jerusalem Conference on Information Technology (pp. 717–730). Jerusalem, Israel: IEEE. https://doi.org/10.1109/JCIT.1990.128356","ista":"Henzinger TA, Manna Z, Pnueli A. 1990. An interleaving model for real time. Proceedings of the 5th Jerusalem Conference on Information Technology. JCIT: Jerusalem Conference on Information Technology, 717–730."},"main_file_link":[{"url":"https://ieeexplore.ieee.org/abstract/document/128356"}],"publication":" Proceedings of the 5th Jerusalem Conference on Information Technology","article_processing_charge":"No","publication_identifier":{"isbn":["0-8186-2078-1"]},"day":"01","month":"01","scopus_import":"1","oa_version":"None","date_updated":"2022-02-15T15:51:25Z","date_created":"2018-12-11T12:09:14Z","author":[{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Manna","first_name":"Zohar","full_name":"Manna, Zohar"},{"first_name":"Amir","last_name":"Pnueli","full_name":"Pnueli, Amir"}],"publisher":"IEEE","publication_status":"published","title":"An interleaving model for real time","status":"public","_id":"4510","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"Sponsors: IBM graduate fellowship, National Science Foundation grant CCR-89-11512, National Science Foundation CCR-89-13641, Defense Advanced Research Projects Agency under contract N00039-84-C-0211, United States Air Force Office of Scientific Research under contract AFOSR-90-0057, European Community ESPRIT Basic Research Action project 3096 (SPEC).","year":"1990","extern":"1","publist_id":"220","abstract":[{"lang":"eng","text":"The interleaving model is both adequate and sufficiently abstract to allow for the practical specification and verification of many properties of concurrent systems. We incorporate real time into this model by defining the abstract notion of a real-time transition system as a conservative extension of traditional transition systems: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound real-time requirements for transitions.\r\nWe present proof rules to establish lower and upper real-time bounds for response properties of real-time transition systems. This proof system can be used to verify bounded-invariance and bounded-response properties, such as timely termination of shared-variables multi-process systems, whose semantics is defined in terms of real-time transition systems."}],"type":"conference"},{"publist_id":"209","abstract":[{"text":"We introduce a novel extension of propositional modal logic that is interpreted over Kripke structures in which a value is associated with every possible world. These values are. however, not treated as full first-order objects: they can be accessed only by a very restricted form of quantification: the \"freeze\" quantifier binds a variable to the value of the current world. We present a complete proof system for this (\"half-order\") modal logic. As a special case, we obtain the real-time temporal logic TPTL of [AH891: the models are restricted to infinite sequences of states, whose values are monotonically increasing natural numbers. The ordering relation between states is interpreted as temporal precedence. while the value associated with a state is interpreted as its \"rear time. We extend our proof system to be complete for TPTL. and demonstrate how it can be used to derive real-time properties. ","lang":"eng"}],"extern":"1","type":"conference","author":[{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"}],"oa_version":"None","date_created":"2018-12-11T12:09:17Z","date_updated":"2022-02-15T15:11:03Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4522","year":"1990","acknowledgement":"Many thanks to Rajeev Alur, Adam Grove, Zohar Manna, and Amir Pnueli for their continuous discussions and support.","publisher":"ACM","title":"Half-order modal logic: How to prove real-time properties","status":"public","publication_status":"published","article_processing_charge":"No","publication_identifier":{"isbn":["978-0-89791-404-8"]},"month":"01","day":"01","scopus_import":"1","doi":"10.1145/93385.93429","date_published":"1990-01-01T00:00:00Z","conference":{"location":"Quebec City, Canada","start_date":"1990-08-22","end_date":"1990-08-24","name":"PODC: Principles of Distributed Computing"},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/93385.93429"}],"citation":{"ista":"Henzinger TA. 1990. Half-order modal logic: How to prove real-time properties. Proceedings of the 9th annual ACM symposium on Principles of distributed computing. PODC: Principles of Distributed Computing, 281–296.","ieee":"T. A. Henzinger, “Half-order modal logic: How to prove real-time properties,” in Proceedings of the 9th annual ACM symposium on Principles of distributed computing, Quebec City, Canada, 1990, pp. 281–296.","apa":"Henzinger, T. A. (1990). Half-order modal logic: How to prove real-time properties. In Proceedings of the 9th annual ACM symposium on Principles of distributed computing (pp. 281–296). Quebec City, Canada: ACM. https://doi.org/10.1145/93385.93429","ama":"Henzinger TA. Half-order modal logic: How to prove real-time properties. In: Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing. ACM; 1990:281-296. doi:10.1145/93385.93429","chicago":"Henzinger, Thomas A. “Half-Order Modal Logic: How to Prove Real-Time Properties.” In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, 281–96. ACM, 1990. https://doi.org/10.1145/93385.93429.","mla":"Henzinger, Thomas A. “Half-Order Modal Logic: How to Prove Real-Time Properties.” Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, ACM, 1990, pp. 281–96, doi:10.1145/93385.93429.","short":"T.A. Henzinger, in:, Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, ACM, 1990, pp. 281–296."},"publication":"Proceedings of the 9th annual ACM symposium on Principles of distributed computing","page":"281 - 296","quality_controlled":"1"},{"type":"conference","abstract":[{"text":"A unifying framework for the study of real-time logics is developed. In analogy to the untimed case, the underlying classical theory of timed state sequences is identified, it is shown to be nonelementarily decidable, and its complexity and expressiveness are used as a point of reference. Two orthogonal extensions of PTL (timed propositional temporal logic and metric temporal logic) that inherit its appeal are defined: they capture elementary, yet expressively complete, fragments of the theory of timed state sequences, and thus are excellent candidates for practical real-time specification languages","lang":"eng"}],"publist_id":"112","extern":"1","_id":"4597","year":"1990","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_status":"published","status":"public","title":"Real-time logics: Complexity and expressiveness","publisher":"IEEE","author":[{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"}],"date_created":"2018-12-11T12:09:40Z","date_updated":"2022-02-15T14:35:30Z","oa_version":"None","scopus_import":"1","month":"08","day":"06","article_processing_charge":"No","publication_identifier":{"isbn":["0-8186-2073-0"]},"publication":" 5th Annual IEEE Symposium on Logic in Computer Science","citation":{"short":"R. Alur, T.A. Henzinger, in:, 5th Annual IEEE Symposium on Logic in Computer Science, IEEE, 1990, pp. 390–401.","mla":"Alur, Rajeev, and Thomas A. Henzinger. “Real-Time Logics: Complexity and Expressiveness.” 5th Annual IEEE Symposium on Logic in Computer Science, IEEE, 1990, pp. 390–401, doi:10.1109/LICS.1990.113764.","chicago":"Alur, Rajeev, and Thomas A Henzinger. “Real-Time Logics: Complexity and Expressiveness.” In 5th Annual IEEE Symposium on Logic in Computer Science, 390–401. IEEE, 1990. https://doi.org/10.1109/LICS.1990.113764.","ama":"Alur R, Henzinger TA. Real-time logics: Complexity and expressiveness. In: 5th Annual IEEE Symposium on Logic in Computer Science. IEEE; 1990:390-401. doi:10.1109/LICS.1990.113764","apa":"Alur, R., & Henzinger, T. A. (1990). Real-time logics: Complexity and expressiveness. In 5th Annual IEEE Symposium on Logic in Computer Science (pp. 390–401). Philadelphia, PA, USA: IEEE. https://doi.org/10.1109/LICS.1990.113764","ieee":"R. Alur and T. A. Henzinger, “Real-time logics: Complexity and expressiveness,” in 5th Annual IEEE Symposium on Logic in Computer Science, Philadelphia, PA, USA, 1990, pp. 390–401.","ista":"Alur R, Henzinger TA. 1990. Real-time logics: Complexity and expressiveness. 5th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 390–401."},"main_file_link":[{"url":"https://ieeexplore.ieee.org/document/113764"}],"quality_controlled":"1","page":"390 - 401","conference":{"location":"Philadelphia, PA, USA","start_date":"1990-06-04","end_date":"1990-06-07","name":"LICS: Logic in Computer Science"},"date_published":"1990-08-06T00:00:00Z","doi":"10.1109/LICS.1990.113764","language":[{"iso":"eng"}]}]