[{"abstract":[{"lang":"eng","text":"This paper presents insertions-only algorithms for maintaining the exact and/or approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact sizekin timeO(1) and a cut of sizekin time linear in its size. For the minimum edge cut problem and for any 0 < ε ≤ 1, the amortized time per insertion isO(1/ε2) for a (2 + ε)-approximation,O((log λ)((log n)/ε)2) for a (1 + ε)-approximation, andO(λ log n) for the exact size, wherenis the number of nodes in the graph and λ is the size of the minimum cut. The (2 + ε)-approximation algorithm and the exact algorithm are deterministic; the (1 + ε)-approximation algorithm is randomized. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time. This is a factor of κ faster than the best algorithm for computing the exact size, which takes time. We give an insertions-only algorithm for maintaining a (2 + ε)-approximation of the minimum vertex cut with amortized insertion timeO(n/ε)."}],"day":"01","publication_identifier":{"issn":["0196-6774"]},"doi":"10.1006/jagm.1997.0855","type":"journal_article","date_published":"1997-07-01T00:00:00Z","citation":{"apa":"Henzinger, M. H. (1997). A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. Elsevier. https://doi.org/10.1006/jagm.1997.0855","ama":"Henzinger MH. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 1997;24(1):194-220. doi:10.1006/jagm.1997.0855","chicago":"Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms. Elsevier, 1997. https://doi.org/10.1006/jagm.1997.0855.","ieee":"M. H. Henzinger, “A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity,” Journal of Algorithms, vol. 24, no. 1. Elsevier, pp. 194–220, 1997.","mla":"Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms, vol. 24, no. 1, Elsevier, 1997, pp. 194–220, doi:10.1006/jagm.1997.0855.","short":"M.H. Henzinger, Journal of Algorithms 24 (1997) 194–220.","ista":"Henzinger MH. 1997. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 24(1), 194–220."},"year":"1997","date_updated":"2022-09-12T09:15:38Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","extern":"1","volume":24,"intvolume":" 24","month":"07","title":"A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity","article_processing_charge":"No","date_created":"2022-08-08T12:18:38Z","oa_version":"None","publication_status":"published","issue":"1","author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"scopus_import":"1","publication":"Journal of Algorithms","_id":"11765","article_type":"original","publisher":"Elsevier","language":[{"iso":"eng"}],"quality_controlled":"1","page":"194-220"},{"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"08","publication":"Journal of Computer and System Sciences","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1006/jcss.1997.1493"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0022-0000"]},"oa":1,"date_published":"1997-08-01T00:00:00Z","type":"journal_article","publisher":"Elsevier","article_type":"original","page":"3-23","quality_controlled":"1","publication_status":"published","date_created":"2022-08-08T12:28:45Z","article_processing_charge":"No","title":"Faster shortest-path algorithms for planar graphs","intvolume":" 55","_id":"11767","scopus_import":"1","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Klein, Philip","last_name":"Klein","first_name":"Philip"},{"last_name":"Rao","first_name":"Satish","full_name":"Rao, Satish"},{"first_name":"Sairam","last_name":"Subramanian","full_name":"Subramanian, Sairam"}],"issue":"1","volume":55,"extern":"1","doi":"10.1006/jcss.1997.1493","day":"01","abstract":[{"text":"We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.","lang":"eng"}],"date_updated":"2022-09-12T10:46:21Z","year":"1997","citation":{"chicago":"Henzinger, Monika H, Philip Klein, Satish Rao, and Sairam Subramanian. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences. Elsevier, 1997. https://doi.org/10.1006/jcss.1997.1493.","ieee":"M. H. Henzinger, P. Klein, S. Rao, and S. Subramanian, “Faster shortest-path algorithms for planar graphs,” Journal of Computer and System Sciences, vol. 55, no. 1. Elsevier, pp. 3–23, 1997.","apa":"Henzinger, M. H., Klein, P., Rao, S., & Subramanian, S. (1997). Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1006/jcss.1997.1493","ama":"Henzinger MH, Klein P, Rao S, Subramanian S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 1997;55(1):3-23. doi:10.1006/jcss.1997.1493","ista":"Henzinger MH, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.","mla":"Henzinger, Monika H., et al. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences, vol. 55, no. 1, Elsevier, 1997, pp. 3–23, doi:10.1006/jcss.1997.1493.","short":"M.H. Henzinger, P. Klein, S. Rao, S. Subramanian, Journal of Computer and System Sciences 55 (1997) 3–23."}},{"citation":{"ama":"Hunt BR, Kaloshin V. How projections affect the dimension spectrum of fractal measures. Nonlinearity. 1997;10(5):1031-1046. doi:10.1088/0951-7715/10/5/002","apa":"Hunt, B. R., & Kaloshin, V. (1997). How projections affect the dimension spectrum of fractal measures. Nonlinearity. IOP Publishing. https://doi.org/10.1088/0951-7715/10/5/002","chicago":"Hunt, Brian R, and Vadim Kaloshin. “How Projections Affect the Dimension Spectrum of Fractal Measures.” Nonlinearity. IOP Publishing, 1997. https://doi.org/10.1088/0951-7715/10/5/002.","ieee":"B. R. Hunt and V. Kaloshin, “How projections affect the dimension spectrum of fractal measures,” Nonlinearity, vol. 10, no. 5. IOP Publishing, pp. 1031–1046, 1997.","mla":"Hunt, Brian R., and Vadim Kaloshin. “How Projections Affect the Dimension Spectrum of Fractal Measures.” Nonlinearity, vol. 10, no. 5, IOP Publishing, 1997, pp. 1031–46, doi:10.1088/0951-7715/10/5/002.","short":"B.R. Hunt, V. Kaloshin, Nonlinearity 10 (1997) 1031–1046.","ista":"Hunt BR, Kaloshin V. 1997. How projections affect the dimension spectrum of fractal measures. Nonlinearity. 10(5), 1031–1046."},"year":"1997","date_updated":"2021-01-12T08:19:53Z","type":"journal_article","date_published":"1997-06-19T00:00:00Z","day":"19","publication_identifier":{"issn":["0951-7715","1361-6544"]},"doi":"10.1088/0951-7715/10/5/002","abstract":[{"lang":"eng","text":"We introduce a new potential-theoretic definition of the dimension spectrum of a probability measure for q > 1 and explain its relation to prior definitions. We apply this definition to prove that if and is a Borel probability measure with compact support in , then under almost every linear transformation from to , the q-dimension of the image of is ; in particular, the q-dimension of is preserved provided . We also present results on the preservation of information dimension and pointwise dimension. Finally, for and q > 2 we give examples for which is not preserved by any linear transformation into . All results for typical linear transformations are also proved for typical (in the sense of prevalence) continuously differentiable functions."}],"volume":10,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","extern":"1","publication":"Nonlinearity","_id":"8527","issue":"5","author":[{"last_name":"Hunt","first_name":"Brian R","full_name":"Hunt, Brian R"},{"id":"FE553552-CDE8-11E9-B324-C0EBE5697425","full_name":"Kaloshin, Vadim","orcid":"0000-0002-6051-2628","last_name":"Kaloshin","first_name":"Vadim"}],"article_processing_charge":"No","date_created":"2020-09-18T10:50:41Z","publication_status":"published","oa_version":"None","intvolume":" 10","title":"How projections affect the dimension spectrum of fractal measures","month":"06","quality_controlled":"1","page":"1031-1046","keyword":["Mathematical Physics","General Physics and Astronomy","Applied Mathematics","Statistical and Nonlinear Physics"],"language":[{"iso":"eng"}],"publisher":"IOP Publishing","article_type":"original"},{"date_updated":"2021-01-12T08:19:54Z","year":"1997","citation":{"ista":"Kaloshin V. 1997. Prevalence in the space of finitely smooth maps. Functional Analysis and Its Applications. 31(2), 95–99.","mla":"Kaloshin, Vadim. “Prevalence in the Space of Finitely Smooth Maps.” Functional Analysis and Its Applications, vol. 31, no. 2, Springer Nature, 1997, pp. 95–99, doi:10.1007/bf02466014.","short":"V. Kaloshin, Functional Analysis and Its Applications 31 (1997) 95–99.","ieee":"V. Kaloshin, “Prevalence in the space of finitely smooth maps,” Functional Analysis and Its Applications, vol. 31, no. 2. Springer Nature, pp. 95–99, 1997.","chicago":"Kaloshin, Vadim. “Prevalence in the Space of Finitely Smooth Maps.” Functional Analysis and Its Applications. Springer Nature, 1997. https://doi.org/10.1007/bf02466014.","ama":"Kaloshin V. Prevalence in the space of finitely smooth maps. Functional Analysis and Its Applications. 1997;31(2):95-99. doi:10.1007/bf02466014","apa":"Kaloshin, V. (1997). Prevalence in the space of finitely smooth maps. Functional Analysis and Its Applications. Springer Nature. https://doi.org/10.1007/bf02466014"},"date_published":"1997-03-30T00:00:00Z","type":"journal_article","doi":"10.1007/bf02466014","publication_identifier":{"issn":["0016-2663","1573-8485"]},"day":"30","abstract":[{"text":"In the present paper, we give a definition of prevalent (\"metrically prevalent\" ) sets in nonlinear function\r\nspaces. A subset of a Euclidean space is said to be metrically prevalent if its complement has measure zero.\r\nThere is no natural way to generalize the definition of a set of measure zero in a finite-dimensional space\r\nto the infinite-dimensional case [6]. Therefore, it is necessary to give a special definition of a metrically\r\nprevalent set (set of full measure) in an infinite-dimensional space. There are various ways to do so. We\r\nsuggest one of the possible ways to define the class of metrically prevalent sets in the space of smooth maps\r\nof one smooth manifold into another. It is shown in this paper that the class of metrically prevalent sets\r\nhas natural properties; in particular, the intersection of finitely many metrically prevalent sets is metrically\r\nprevalent. The main result of the paper is a prevalent version of Thorn's transversality theorem.\r\nIt is common practice in singularity theory and the theory of dynamical systems to say that a property\r\nholds for \"almost every\" map (or flow) if it holds for a residual set, i.e., a set that contains a countable\r\nintersection of open dense sets in the corresponding function space. However, even in finite-dimensional\r\nspaces such a set can have arbitrarily small (say, zero) Lebesgue measure. We prove that Thorn's transversality theorem holds for an essentially \"thicker\" set than a residual set. It seems reasonable to revise from\r\nthe prevalent point of view the classical results of singularity theory and theory of dynamical systems,\r\nincluding the multijet transversality theorem, Mather's stability theorem, Kupka-Smale's theorem for dynamical systems, etc. We shall do this elsewhere. The notion of prevalence in linear Banach spaces was\r\nintroduced and investigated in [8]. One of the possible ways to define a class of prevalent sets in the space\r\nof smooth maps of manifolds, which essentially differs from that presented in this paper, is given in [7].\r\nDefinitions of typicalness based on the Lebesgue measure in a finite-dimensional space were suggested\r\nby Kolmogorov [10] and Arnold [11]. These definitions were cited and discussed in [9]. Here we only point\r\nout that the finite-dimensional analog of Arnold's definition allows prevalent sets to have arbitrarily small\r\nmeasure, whereas the prevalent sets in the sense of the finite-dimensional analog of the definition given in\r\nthe present paper are necessarily of full measure. Our definition is a modification of that due to Arnold.\r\nI wish to thank Yu. S. Illyashenko for constant attention to this work and useful discussions and\r\nR. I. Bogdanov for help in the preparation of this paper. ","lang":"eng"}],"volume":31,"extern":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"8528","publication":"Functional Analysis and Its Applications","author":[{"id":"FE553552-CDE8-11E9-B324-C0EBE5697425","full_name":"Kaloshin, Vadim","orcid":"0000-0002-6051-2628","last_name":"Kaloshin","first_name":"Vadim"}],"issue":"2","publication_status":"published","oa_version":"None","date_created":"2020-09-18T10:50:54Z","article_processing_charge":"No","title":"Prevalence in the space of finitely smooth maps","month":"03","intvolume":" 31","page":"95-99","quality_controlled":"1","language":[{"iso":"eng"}],"keyword":["Applied Mathematics","Analysis"],"publisher":"Springer Nature","article_type":"original"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","page":"74 - 88","quality_controlled":"1","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:09:36Z","title":"Modularity for timed and hybrid systems","alternative_title":["LNCS"],"intvolume":" 1243","_id":"4583","scopus_import":"1","author":[{"last_name":"Alur","first_name":"Rajeev","full_name":"Alur, Rajeev"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"volume":1243,"acknowledgement":"This research was supported in part by the ONR YIP award N00014-95-1-0520, by the NSF CAREER award CCR-9501708, by the NSF grant CCR-9504469, by the AFOSR contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA grant NAG2-892, and by the SRC contract 95-DC-324.036.","extern":"1","doi":"10.1007/3-540-63141-0_6","day":"01","abstract":[{"lang":"eng","text":"In a trace-based world, the modular specification, verification, and control of live systems require each module to be receptive; that is, each module must be able to meet its liveness assumptions no matter how the other modules behave. In a real-time world, liveness is automatically present in the form of diverging time. The receptiveness condition, then, translates to the requirement that a module must be able to let time diverge no matter how the environment behaves. We study the receptiveness condition for real-time systems by extending the model of reactive modules to timed and hybrid modules. We define the receptiveness of such a module as the existence of a winning strategy in a game of the module against its environment. By solving the game on region graphs, we present an (optimal) Exptime algorithm for checking the receptiveness of prepositional timed modules. By giving a fixpoint characterization of the game, we present a symbolic procedure for checking the receptiveness of linear hybrid modules. Finally, we present an assume-guarantee principle for reasoning about timed and hybrid modules, and a method for synthesizing receptive controllers of timed and hybrid modules."}],"date_updated":"2022-08-17T08:47:55Z","year":"1997","citation":{"ama":"Alur R, Henzinger TA. Modularity for timed and hybrid systems. In: 8th International Conference on Concurrency Theory. Vol 1243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 1997:74-88. doi:10.1007/3-540-63141-0_6","apa":"Alur, R., & Henzinger, T. A. (1997). Modularity for timed and hybrid systems. In 8th International Conference on Concurrency Theory (Vol. 1243, pp. 74–88). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-63141-0_6","chicago":"Alur, Rajeev, and Thomas A Henzinger. “Modularity for Timed and Hybrid Systems.” In 8th International Conference on Concurrency Theory, 1243:74–88. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1997. https://doi.org/10.1007/3-540-63141-0_6.","ieee":"R. Alur and T. A. Henzinger, “Modularity for timed and hybrid systems,” in 8th International Conference on Concurrency Theory, Warsaw, Poland, 1997, vol. 1243, pp. 74–88.","short":"R. Alur, T.A. Henzinger, in:, 8th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1997, pp. 74–88.","mla":"Alur, Rajeev, and Thomas A. Henzinger. “Modularity for Timed and Hybrid Systems.” 8th International Conference on Concurrency Theory, vol. 1243, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1997, pp. 74–88, doi:10.1007/3-540-63141-0_6.","ista":"Alur R, Henzinger TA. 1997. Modularity for timed and hybrid systems. 8th International Conference on Concurrency Theory. CONCUR: Concurrency Theory, LNCS, vol. 1243, 74–88."},"conference":{"start_date":"1997-07-01","name":"CONCUR: Concurrency Theory","location":"Warsaw, Poland","end_date":"1997-07-04"},"language":[{"iso":"eng"}],"oa_version":"None","month":"01","publication":"8th International Conference on Concurrency Theory","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication_identifier":{"isbn":["9783540691884"]},"publist_id":"124","date_published":"1997-01-01T00:00:00Z","type":"conference"},{"title":"Real-time system = discrete system + clock variables","intvolume":" 1","publication_status":"published","date_created":"2018-12-11T12:09:36Z","article_processing_charge":"No","author":[{"full_name":"Alur, Rajeev","first_name":"Rajeev","last_name":"Alur"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"}],"issue":"1-2","_id":"4584","scopus_import":"1","article_type":"original","publisher":"Springer","page":"86 - 109","quality_controlled":"1","abstract":[{"lang":"eng","text":"This paper introduces, gently but rigorously, the clock approach to real-time programming. We present with mathematical precision, assuming no prerequisites other than familiarity with logical and programming notations, the concepts that are necessary for understanding, writing, and executing clock programs. In keeping with an expository style, all references are clustered in bibliographic remarks at the end of each section. The first appendix presents proof rules for verifying temporal properties of clock programs. The second appendix points to selected literature on formal methods and tools for programming with clocks. In particular, the timed automaton, which is a finite-state machine equipped with clocks, has become a standard paradigm for real-time model checking; it underlies the tools HyTech, Kronos, and Uppaal, which are discussed elsewhere in this volume."}],"doi":"10.1007/s100090050007","day":"01","date_updated":"2022-08-17T08:27:20Z","year":"1997","citation":{"chicago":"Alur, Rajeev, and Thomas A Henzinger. “Real-Time System = Discrete System + Clock Variables.” Software Tools For Technology Transfer. Springer, 1997. https://doi.org/10.1007/s100090050007.","ieee":"R. Alur and T. A. Henzinger, “Real-time system = discrete system + clock variables,” Software Tools For Technology Transfer, vol. 1, no. 1–2. Springer, pp. 86–109, 1997.","ama":"Alur R, Henzinger TA. Real-time system = discrete system + clock variables. Software Tools For Technology Transfer. 1997;1(1-2):86-109. doi:10.1007/s100090050007","apa":"Alur, R., & Henzinger, T. A. (1997). Real-time system = discrete system + clock variables. Software Tools For Technology Transfer. Springer. https://doi.org/10.1007/s100090050007","ista":"Alur R, Henzinger TA. 1997. Real-time system = discrete system + clock variables. Software Tools For Technology Transfer. 1(1–2), 86–109.","mla":"Alur, Rajeev, and Thomas A. Henzinger. “Real-Time System = Discrete System + Clock Variables.” Software Tools For Technology Transfer, vol. 1, no. 1–2, Springer, 1997, pp. 86–109, doi:10.1007/s100090050007.","short":"R. Alur, T.A. Henzinger, Software Tools For Technology Transfer 1 (1997) 86–109."},"extern":"1","volume":1,"acknowledgement":"The authors thank Rance Cleaveland, Limor Fix, David Karr, Peter Kopke, Fred Schneider, and Bernhard Steffen for helpful comments.","month":"01","oa_version":"None","publication":"Software Tools For Technology Transfer","language":[{"iso":"eng"}],"publist_id":"123","publication_identifier":{"issn":["1433-2779"]},"date_published":"1997-01-01T00:00:00Z","type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public"},{"language":[{"iso":"eng"}],"page":"702 - 707","quality_controlled":"1","conference":{"name":"CDC: Decision and Control","start_date":"1997-12-12","location":"San Diego, CA, USA","end_date":"1997-12-12"},"publisher":"IEEE","author":[{"last_name":"Alur","first_name":"Rajeev","full_name":"Alur, Rajeev"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Wong Toi, Howard","last_name":"Wong Toi","first_name":"Howard"}],"publication":"Proceedings of the 36th IEEE Conference on Decision and Control","_id":"4605","scopus_import":"1","title":"Symbolic analysis of hybrid systems","month":"12","oa_version":"None","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:09:43Z","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","date_published":"1997-12-01T00:00:00Z","type":"conference","date_updated":"2022-08-17T08:08:36Z","year":"1997","citation":{"ista":"Alur R, Henzinger TA, Wong Toi H. 1997. Symbolic analysis of hybrid systems. Proceedings of the 36th IEEE Conference on Decision and Control. CDC: Decision and Control, 702–707.","mla":"Alur, Rajeev, et al. “Symbolic Analysis of Hybrid Systems.” Proceedings of the 36th IEEE Conference on Decision and Control, IEEE, 1997, pp. 702–07, doi:10.1109/CDC.1997.650717 .","short":"R. Alur, T.A. Henzinger, H. Wong Toi, in:, Proceedings of the 36th IEEE Conference on Decision and Control, IEEE, 1997, pp. 702–707.","chicago":"Alur, Rajeev, Thomas A Henzinger, and Howard Wong Toi. “Symbolic Analysis of Hybrid Systems.” In Proceedings of the 36th IEEE Conference on Decision and Control, 702–7. IEEE, 1997. https://doi.org/10.1109/CDC.1997.650717 .","ieee":"R. Alur, T. A. Henzinger, and H. Wong Toi, “Symbolic analysis of hybrid systems,” in Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, 1997, pp. 702–707.","ama":"Alur R, Henzinger TA, Wong Toi H. Symbolic analysis of hybrid systems. In: Proceedings of the 36th IEEE Conference on Decision and Control. IEEE; 1997:702-707. doi:10.1109/CDC.1997.650717 ","apa":"Alur, R., Henzinger, T. A., & Wong Toi, H. (1997). Symbolic analysis of hybrid systems. In Proceedings of the 36th IEEE Conference on Decision and Control (pp. 702–707). San Diego, CA, USA: IEEE. https://doi.org/10.1109/CDC.1997.650717 "},"abstract":[{"text":"A hybrid system is a dynamical system whose behavior exhibits both discrete and continuous change. A hybrid automaton is a mathematical model for hybrid systems, which combines, in a single formalism, automaton transitions for capturing discrete change with differential equations for capturing continuous change. In this survey, we demonstrate symbolic algorithms for the verification of and controller synthesis for linear hybrid automata, a subclass of hybrid automata that can be analyzed automatically","lang":"eng"}],"publist_id":"101","doi":"10.1109/CDC.1997.650717 ","day":"01","publication_identifier":{"isbn":["0780341872"]}},{"abstract":[{"text":"We present a verification algorithm for duration properties of real-time systems. While simple real-time properties constrain the total elapsed time between events, duration properties constrain the accumulated satisfaction time of state predicates. We formalize the concept of durations by introducing duration measures for timed automata. A duration measure assigns to each finite run of a timed automaton a real number —the duration of the run— which may be the accumulated satisfaction time of a state predicate along the run. Given a timed automaton with a duration measure, an initial and a final state, and an arithmetic constraint, the duration-bounded reachability problem asks if there is a run of the automaton from the initial state to the final state such that the duration of the run satisfies the constraint. Our main result is an (optimal) PSPACE decision procedure for the duration-bounded reachability problem.","lang":"eng"}],"day":"01","doi":"10.1023/A:1008626013578","citation":{"apa":"Alur, R., Courcoubetis, C., & Henzinger, T. A. (1997). Computing accumulated delays in real-time systems. Formal Methods in System Design. Springer. https://doi.org/10.1023/A:1008626013578","ama":"Alur R, Courcoubetis C, Henzinger TA. Computing accumulated delays in real-time systems. Formal Methods in System Design. 1997;11(2):137-156. doi:10.1023/A:1008626013578","ieee":"R. Alur, C. Courcoubetis, and T. A. Henzinger, “Computing accumulated delays in real-time systems,” Formal Methods in System Design, vol. 11, no. 2. Springer, pp. 137–156, 1997.","chicago":"Alur, Rajeev, Costas Courcoubetis, and Thomas A Henzinger. “Computing Accumulated Delays in Real-Time Systems.” Formal Methods in System Design. Springer, 1997. https://doi.org/10.1023/A:1008626013578.","mla":"Alur, Rajeev, et al. “Computing Accumulated Delays in Real-Time Systems.” Formal Methods in System Design, vol. 11, no. 2, Springer, 1997, pp. 137–56, doi:10.1023/A:1008626013578.","short":"R. Alur, C. Courcoubetis, T.A. Henzinger, Formal Methods in System Design 11 (1997) 137–156.","ista":"Alur R, Courcoubetis C, Henzinger TA. 1997. Computing accumulated delays in real-time systems. Formal Methods in System Design. 11(2), 137–156."},"year":"1997","date_updated":"2022-08-16T13:43:41Z","extern":"1","acknowledgement":"A preliminary version of this paper appeared in the Proceedings of the Fifth International Conference on Computer-Aided Verification (CAV 93), Springer-Verlag LNCS 818, pp. 181–193, 1993. We thank Sergio Yovine for a careful reading of the manuscript. This reaserch was partially supported by the BRA ESPRIT project REACT, by the ONR YIP\r\naward N00014-95-1-0520, by the NSF CAREER award CCR-9501708, by the NSF grants CCR-9200794 and CCR-9504469, by the AFOSR contract F49620-93-1-0056, and by the ARPA grant NAG2-892.","volume":11,"intvolume":" 11","title":"Computing accumulated delays in real-time systems","article_processing_charge":"No","date_created":"2018-12-11T12:09:43Z","publication_status":"published","issue":"2","author":[{"last_name":"Alur","first_name":"Rajeev","full_name":"Alur, Rajeev"},{"last_name":"Courcoubetis","first_name":"Costas","full_name":"Courcoubetis, Costas"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"}],"scopus_import":"1","_id":"4607","article_type":"original","publisher":"Springer","quality_controlled":"1","page":"137 - 156","publist_id":"98","publication_identifier":{"issn":["0925-9856"]},"type":"journal_article","date_published":"1997-01-01T00:00:00Z","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","month":"01","oa_version":"None","publication":"Formal Methods in System Design","language":[{"iso":"eng"}]},{"publication_identifier":{"isbn":["9783540631668"]},"publist_id":"99","type":"conference","date_published":"1997-01-01T00:00:00Z","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","month":"01","publication":"9th International Conference on Computer Aided Verification","conference":{"name":"CAV: Computer Aided Verification","start_date":"1997-06-22","end_date":"1997-06-25","location":"Haifa, Israel"},"language":[{"iso":"eng"}],"day":"01","doi":"10.1007/3-540-63166-6_34","abstract":[{"lang":"eng","text":"State space explosion is a fundamental obstacle in formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reductions and symbolic state space search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable states. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable states as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first search for the analysis of asynchronous network protocols, and symbolic breadth-first search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy."}],"citation":{"mla":"Alur, Rajeev, et al. “Partial-Order Reduction in Symbolic State-Space Exploration.” 9th International Conference on Computer Aided Verification, vol. 1254, Springer, 1997, pp. 340–51, doi:10.1007/3-540-63166-6_34.","short":"R. Alur, R. Brayton, T.A. Henzinger, S. Qadeer, S. Rajamani, in:, 9th International Conference on Computer Aided Verification, Springer, 1997, pp. 340–351.","ista":"Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. 1997. Partial-order reduction in symbolic state-space exploration. 9th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 1254, 340–351.","apa":"Alur, R., Brayton, R., Henzinger, T. A., Qadeer, S., & Rajamani, S. (1997). Partial-order reduction in symbolic state-space exploration. In 9th International Conference on Computer Aided Verification (Vol. 1254, pp. 340–351). Haifa, Israel: Springer. https://doi.org/10.1007/3-540-63166-6_34","ama":"Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. Partial-order reduction in symbolic state-space exploration. In: 9th International Conference on Computer Aided Verification. Vol 1254. Springer; 1997:340-351. doi:10.1007/3-540-63166-6_34","chicago":"Alur, Rajeev, Robert Brayton, Thomas A Henzinger, Shaz Qadeer, and Sriram Rajamani. “Partial-Order Reduction in Symbolic State-Space Exploration.” In 9th International Conference on Computer Aided Verification, 1254:340–51. Springer, 1997. https://doi.org/10.1007/3-540-63166-6_34.","ieee":"R. Alur, R. Brayton, T. A. Henzinger, S. Qadeer, and S. Rajamani, “Partial-order reduction in symbolic state-space exploration,” in 9th International Conference on Computer Aided Verification, Haifa, Israel, 1997, vol. 1254, pp. 340–351."},"year":"1997","date_updated":"2022-08-16T14:09:54Z","acknowledgement":"This research was supported in part by the ONR YIP award N00014-95-1-0520, by the NSF CAREER award CCR-9501708, by the NSF grant CCR-9504469, by the AFOSR contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA grant NAG2-892, and by the Semiconductor Research Corporation contracts DC-324.036 and DC-324.005.","volume":1254,"extern":"1","article_processing_charge":"No","date_created":"2018-12-11T12:09:44Z","publication_status":"published","intvolume":" 1254","title":"Partial-order reduction in symbolic state-space exploration","alternative_title":["LNCS"],"scopus_import":"1","_id":"4608","author":[{"last_name":"Alur","first_name":"Rajeev","full_name":"Alur, Rajeev"},{"last_name":"Brayton","first_name":"Robert","full_name":"Brayton, Robert"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"full_name":"Qadeer, Shaz","first_name":"Shaz","last_name":"Qadeer"},{"first_name":"Sriram","last_name":"Rajamani","full_name":"Rajamani, Sriram"}],"publisher":"Springer","quality_controlled":"1","page":"340 - 351"},{"author":[{"full_name":"Alur, Rajeev","first_name":"Rajeev","last_name":"Alur"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Kupferman, Orna","last_name":"Kupferman","first_name":"Orna"}],"scopus_import":"1","publication":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science","_id":"4609","title":"Alternating-time temporal logic","month":"01","date_created":"2018-12-11T12:09:44Z","article_processing_charge":"No","publication_status":"published","oa_version":"None","language":[{"iso":"eng"}],"quality_controlled":"1","page":"100 - 109","conference":{"location":"Washington, DC, United States","end_date":"1997-10-22","name":"FOCS: Foundations of Computer Science","start_date":"1997-10-19"},"publisher":"Association for Computing Machinery (ACM)","type":"conference","date_published":"1997-01-01T00:00:00Z","citation":{"apa":"Alur, R., Henzinger, T. A., & Kupferman, O. (1997). Alternating-time temporal logic. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (pp. 100–109). Washington, DC, United States: Association for Computing Machinery (ACM). https://doi.org/10.1145/585265.585270","ama":"Alur R, Henzinger TA, Kupferman O. Alternating-time temporal logic. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Association for Computing Machinery (ACM); 1997:100-109. doi:10.1145/585265.585270","chicago":"Alur, Rajeev, Thomas A Henzinger, and Orna Kupferman. “Alternating-Time Temporal Logic.” In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 100–109. Association for Computing Machinery (ACM), 1997. https://doi.org/10.1145/585265.585270.","ieee":"R. Alur, T. A. Henzinger, and O. Kupferman, “Alternating-time temporal logic,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Washington, DC, United States, 1997, pp. 100–109.","mla":"Alur, Rajeev, et al. “Alternating-Time Temporal Logic.” Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Association for Computing Machinery (ACM), 1997, pp. 100–09, doi:10.1145/585265.585270.","short":"R. Alur, T.A. Henzinger, O. Kupferman, in:, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Association for Computing Machinery (ACM), 1997, pp. 100–109.","ista":"Alur R, Henzinger TA, Kupferman O. 1997. Alternating-time temporal logic. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science, 100–109."},"year":"1997","date_updated":"2022-09-05T07:32:05Z","publist_id":"100","abstract":[{"lang":"eng","text":"Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by system moves; branching-time temporal logic allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic: alternating-time temporal logic offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator “eventually” with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. Also the problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas"}],"publication_identifier":{"issn":["0004-5411"]},"day":"01","doi":"10.1145/585265.585270","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","acknowledgement":"We thank Luca de Alfaro, Kousha Etessami, Salvatore La Torre, P. Madhusudan, Amir Pnueli, Moshe Vardi, Thomas Wilke, and Mihalis Yannakakis for helpful discussions. We also thank Freddy Mang for comments on a draft of this manuscript."},{"citation":{"ama":"Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs. In: 24th International Colloquium on Automata, Languages and Programming. Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214","apa":"Henzinger, M. H., & King, V. (1997). Maintaining minimum spanning trees in dynamic graphs. In 24th International Colloquium on Automata, Languages and Programming (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature. https://doi.org/10.1007/3-540-63165-8_214","ieee":"M. H. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic graphs,” in 24th International Colloquium on Automata, Languages and Programming, Bologna, Italy, 1997, vol. 1256, pp. 594–604.","chicago":"Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.","mla":"Henzinger, Monika H., and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” 24th International Colloquium on Automata, Languages and Programming, vol. 1256, Springer Nature, 1997, pp. 594–604, doi:10.1007/3-540-63165-8_214.","short":"M.H. Henzinger, V. King, in:, 24th International Colloquium on Automata, Languages and Programming, Springer Nature, 1997, pp. 594–604.","ista":"Henzinger MH, King V. 1997. Maintaining minimum spanning trees in dynamic graphs. 24th International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1256, 594–604."},"year":"1997","date_updated":"2023-02-14T07:49:03Z","type":"conference","date_published":"1997-07-01T00:00:00Z","publication_identifier":{"isbn":["9783540631651"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783540691945"]},"day":"01","doi":"10.1007/3-540-63165-8_214","abstract":[{"text":"We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.","lang":"eng"}],"volume":1256,"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","scopus_import":"1","_id":"11803","publication":"24th International Colloquium on Automata, Languages and Programming","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"}],"article_processing_charge":"No","date_created":"2022-08-11T13:35:06Z","oa_version":"None","publication_status":"published","intvolume":" 1256","title":"Maintaining minimum spanning trees in dynamic graphs","alternative_title":["LNCS"],"month":"07","quality_controlled":"1","page":"594–604","language":[{"iso":"eng"}],"publisher":"Springer Nature","conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"1997-07-07","end_date":"1997-07-11","location":"Bologna, Italy"}},{"abstract":[{"text":"This paper describes the DIGlTAL Continuous Profiling Infrastmcture, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works on unmodified executable& and collects profiles for entire systems, including user programs, shared libraries, and the operating system kernel. Samples are collected at a high rate (over 5200 samples/secper333-MHz processor), yet with low overhead (l-3% slowdown for most workloads). Analysis tools supplied with the profiling system use the sample data to produce an accurate accounting, down to the level of pipeline stalls incurred by individual instructions, of where time is being spent. When instructions incur stalls, the tools identify possible reasons, such as cache misses, branch mispredictions, and functional unit contention. The fine-grained instruction-level analysis guides users and automated optimizers to the causes of performance\r\nproblems and provides important insights for fixing them. ","lang":"eng"}],"doi":"10.1145/269005.266637","day":"01","date_updated":"2023-02-21T16:30:27Z","year":"1997","citation":{"ista":"Anderson JM, Berc LM, Dean J, Ghemawat S, Henzinger MH, Leung S-TA, Sites RL, Vandevoorde MT, Waldspurger CA, Weihl WE. 1997. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 31(5), 1–14.","short":"J.M. Anderson, L.M. Berc, J. Dean, S. Ghemawat, M.H. Henzinger, S.-T.A. Leung, R.L. Sites, M.T. Vandevoorde, C.A. Waldspurger, W.E. Weihl, ACM SIGOPS Operating Systems Review 31 (1997) 1–14.","mla":"Anderson, Jennifer M., et al. “Continuous Profiling: Where Have All the Cycles Gone?” ACM SIGOPS Operating Systems Review, vol. 31, no. 5, Association for Computing Machinery, 1997, pp. 1–14, doi:10.1145/269005.266637.","chicago":"Anderson, Jennifer M., Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika H Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. “Continuous Profiling: Where Have All the Cycles Gone?” ACM SIGOPS Operating Systems Review. Association for Computing Machinery, 1997. https://doi.org/10.1145/269005.266637.","ieee":"J. M. Anderson et al., “Continuous profiling: Where have all the cycles gone?,” ACM SIGOPS Operating Systems Review, vol. 31, no. 5. Association for Computing Machinery, pp. 1–14, 1997.","ama":"Anderson JM, Berc LM, Dean J, et al. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 1997;31(5):1-14. doi:10.1145/269005.266637","apa":"Anderson, J. M., Berc, L. M., Dean, J., Ghemawat, S., Henzinger, M. H., Leung, S.-T. A., … Weihl, W. E. (1997). Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. Association for Computing Machinery. https://doi.org/10.1145/269005.266637"},"extern":"1","volume":31,"title":"Continuous profiling: Where have all the cycles gone?","intvolume":" 31","publication_status":"published","date_created":"2022-08-16T07:07:03Z","article_processing_charge":"No","author":[{"full_name":"Anderson, Jennifer M.","last_name":"Anderson","first_name":"Jennifer M."},{"last_name":"Berc","first_name":"Lance M.","full_name":"Berc, Lance M."},{"full_name":"Dean, Jeffrey","last_name":"Dean","first_name":"Jeffrey"},{"last_name":"Ghemawat","first_name":"Sanjay","full_name":"Ghemawat, Sanjay"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Leung","first_name":"Shun-Tak A.","full_name":"Leung, Shun-Tak A."},{"full_name":"Sites, Richard L.","first_name":"Richard L.","last_name":"Sites"},{"last_name":"Vandevoorde","first_name":"Mark T.","full_name":"Vandevoorde, Mark T."},{"full_name":"Waldspurger, Carl A.","last_name":"Waldspurger","first_name":"Carl A."},{"last_name":"Weihl","first_name":"William E.","full_name":"Weihl, William E."}],"issue":"5","_id":"11849","scopus_import":"1","article_type":"original","publisher":"Association for Computing Machinery","page":"1-14","quality_controlled":"1","oa":1,"publication_identifier":{"issn":["0163-5980"]},"date_published":"1997-12-01T00:00:00Z","type":"journal_article","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11849"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://doi.org/10.1145/269005.266637","open_access":"1"}],"month":"12","oa_version":"Published Version","publication":"ACM SIGOPS Operating Systems Review","language":[{"iso":"eng"}]},{"year":"1997","citation":{"ieee":"M. H. Henzinger and M. Thorup, “Sampling to provide or to bound: With applications to fully dynamic graph algorithms,” Random Structures and Algorithms, vol. 11, no. 4. Wiley, pp. 369–379, 1997.","chicago":"Henzinger, Monika H, and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” Random Structures and Algorithms. Wiley, 1997. https://doi.org/10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x.","ama":"Henzinger MH, Thorup M. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 1997;11(4):369-379. doi:10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x","apa":"Henzinger, M. H., & Thorup, M. (1997). Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x","ista":"Henzinger MH, Thorup M. 1997. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 11(4), 369–379.","mla":"Henzinger, Monika H., and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” Random Structures and Algorithms, vol. 11, no. 4, Wiley, 1997, pp. 369–79, doi:10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x.","short":"M.H. Henzinger, M. Thorup, Random Structures and Algorithms 11 (1997) 369–379."},"date_updated":"2023-02-17T14:05:02Z","type":"journal_article","date_published":"1997-12-07T00:00:00Z","day":"07","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"doi":"10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x","abstract":[{"text":"In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a (small) upper bound on the size of R that holds with high probability. We give an optimal algorithm for this problem. This algorithm improves the time per operation for various dynamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log3n) to O(log2n).","lang":"eng"}],"volume":11,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","extern":"1","scopus_import":"1","_id":"11883","publication":"Random Structures and Algorithms","issue":"4","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Thorup, Mikkel","first_name":"Mikkel","last_name":"Thorup"}],"date_created":"2022-08-17T07:21:55Z","article_processing_charge":"No","publication_status":"published","oa_version":"None","intvolume":" 11","month":"12","title":"Sampling to provide or to bound: With applications to fully dynamic graph algorithms","quality_controlled":"1","page":"369-379","language":[{"iso":"eng"}],"publisher":"Wiley","article_type":"original"},{"page":"204 - 215","quality_controlled":"1","article_type":"original","publisher":"Society for Neuroscience","author":[{"last_name":"Götz","first_name":"Thomas","full_name":"Götz, Thomas"},{"last_name":"Kraushaar","first_name":"Udo","full_name":"Kraushaar, Udo"},{"full_name":"Geiger, Jörg","last_name":"Geiger","first_name":"Jörg"},{"full_name":"Lubke, Joachim","first_name":"Joachim","last_name":"Lubke"},{"full_name":"Berger, Thomas","last_name":"Berger","first_name":"Thomas"},{"id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","full_name":"Jonas, Peter M","first_name":"Peter M","last_name":"Jonas"}],"issue":"1","_id":"3482","pmid":1,"scopus_import":"1","title":"Functional properties of AMPA and NMDA receptors expressed in identified types of basal ganglia neurons","intvolume":" 17","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:03:34Z","extern":"1","volume":17,"acknowledgement":"This work was supported by Deutsche Forschungsgemeinschaft Grant BE1859 to T.B. and SFB505/C5 to P.J. We thank Mrs. B. Plessow-Freudenberg for help with the immunocytochemistry, Dr. M. Ha¨usser for advice concerning the \r\n reparation of midbrain slices, and Drs. J. Bischofberger, G. B. Landwehrmeyer, and M. Martina for critically reading this manuscript.","external_id":{"pmid":["8987749"]},"date_updated":"2022-08-22T08:48:45Z","citation":{"chicago":"Götz, Thomas, Udo Kraushaar, Jörg Geiger, Joachim Lubke, Thomas Berger, and Peter M Jonas. “Functional Properties of AMPA and NMDA Receptors Expressed in Identified Types of Basal Ganglia Neurons.” Journal of Neuroscience. Society for Neuroscience, 1997. https://doi.org/10.1523/JNEUROSCI.17-01-00204.1997.","ieee":"T. Götz, U. Kraushaar, J. Geiger, J. Lubke, T. Berger, and P. M. Jonas, “Functional properties of AMPA and NMDA receptors expressed in identified types of basal ganglia neurons,” Journal of Neuroscience, vol. 17, no. 1. Society for Neuroscience, pp. 204–215, 1997.","ama":"Götz T, Kraushaar U, Geiger J, Lubke J, Berger T, Jonas PM. Functional properties of AMPA and NMDA receptors expressed in identified types of basal ganglia neurons. Journal of Neuroscience. 1997;17(1):204-215. doi:10.1523/JNEUROSCI.17-01-00204.1997","apa":"Götz, T., Kraushaar, U., Geiger, J., Lubke, J., Berger, T., & Jonas, P. M. (1997). Functional properties of AMPA and NMDA receptors expressed in identified types of basal ganglia neurons. Journal of Neuroscience. Society for Neuroscience. https://doi.org/10.1523/JNEUROSCI.17-01-00204.1997","ista":"Götz T, Kraushaar U, Geiger J, Lubke J, Berger T, Jonas PM. 1997. Functional properties of AMPA and NMDA receptors expressed in identified types of basal ganglia neurons. Journal of Neuroscience. 17(1), 204–215.","mla":"Götz, Thomas, et al. “Functional Properties of AMPA and NMDA Receptors Expressed in Identified Types of Basal Ganglia Neurons.” Journal of Neuroscience, vol. 17, no. 1, Society for Neuroscience, 1997, pp. 204–15, doi:10.1523/JNEUROSCI.17-01-00204.1997.","short":"T. Götz, U. Kraushaar, J. Geiger, J. Lubke, T. Berger, P.M. Jonas, Journal of Neuroscience 17 (1997) 204–215."},"year":"1997","abstract":[{"text":"AMPA- and NMDA-type glutamate receptors (AMPARs and NMDARs) mediate excitatory synoptic transmission in the basal ganglia and may contribute to excitotoxic injury. We investigated the functional properties of AMPARs and NMDARs expressed by six main types of basal ganglia neurons in acute rat brain slices (principal neurons and cholinergic interneurons of striatum, GABAergic and dopaminergic neurons of substantia nigra, globus pallidus neurons, and subthalamic nucleus neurons) using fast application of glutamate to nucleated and outside-out membrane patches, AMPARs in different types of basal ganglia neurons were functionally distinct. Those expressed in striatal principal neurons exhibited the slowest gating (desensitization time constant τ = 11.5 msec, 1 mM glutamate, 22°C), whereas those in striatal cholinergic interneurons showed the fastest gating (desensitization time constant τ = 3.6 msec). The lowest Ca2+ permeability of AMPARs was observed in nigral dopaminergic neurons (P(CA)/P(NA) = 0.10), whereas the highest Ca2+ permeability was found in subthalamic nucleus neurons (P(Ca)/P(Na) = 1.17). NMDARs of different types of basal ganglia neurons were less variable in their functional properties; those expressed in nigral dopaminergic neurons exhibited the slowest gating (deactivation time constant of predominant fast component τ1 150 msec, 100 μM glutamate), and those of globus pallidus neurons showed the fastest gating (τ1 = 67 msec). The Mg2+ block of NMDARs was similar; the average chord conductance ratio g(+60mv)/g(+40mV) was 0.18-0.22 in 100 μM external Mg2+. Hence, AMPARs expressed in different types of basal ganglia neurons are markedly diverse, whereas NMDARs are less variable in functional properties that are relevant for excitatory synoptic transmission and neuronal vulnerability.","lang":"eng"}],"doi":"10.1523/JNEUROSCI.17-01-00204.1997","day":"01","language":[{"iso":"eng"}],"publication":"Journal of Neuroscience","month":"01","oa_version":"Published Version","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6793708/","open_access":"1"}],"date_published":"1997-01-01T00:00:00Z","type":"journal_article","publist_id":"2905","oa":1,"publication_identifier":{"issn":["0270-6474"]}},{"_id":"3483","pmid":1,"scopus_import":"1","author":[{"full_name":"Ceranik, Katya","first_name":"Katya","last_name":"Ceranik"},{"full_name":"Bender, Roland","last_name":"Bender","first_name":"Roland"},{"full_name":"Geiger, Jörg","last_name":"Geiger","first_name":"Jörg"},{"full_name":"Monyer, Hannah","last_name":"Monyer","first_name":"Hannah"},{"id":"353C1B58-F248-11E8-B48F-1D18A9856A87","full_name":"Jonas, Peter M","orcid":"0000-0001-5001-4804","last_name":"Jonas","first_name":"Peter M"},{"last_name":"Frotscher","first_name":"Michael","full_name":"Frotscher, Michael"},{"last_name":"Lubke","first_name":"Joachim","full_name":"Lubke, Joachim"}],"issue":"14","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:03:34Z","title":"A novel type of GABAergic interneuron connecting the input and the output regions of the hippocampus.","intvolume":" 17","page":"5380 - 5394","quality_controlled":"1","publisher":"Society for Neuroscience","article_type":"original","date_updated":"2022-08-22T08:18:54Z","year":"1997","citation":{"mla":"Ceranik, Katya, et al. “A Novel Type of GABAergic Interneuron Connecting the Input and the Output Regions of the Hippocampus.” Journal of Neuroscience, vol. 17, no. 14, Society for Neuroscience, 1997, pp. 5380–94, doi:10.1523/JNEUROSCI.17-14-05380.1997.","short":"K. Ceranik, R. Bender, J. Geiger, H. Monyer, P.M. Jonas, M. Frotscher, J. Lubke, Journal of Neuroscience 17 (1997) 5380–5394.","ista":"Ceranik K, Bender R, Geiger J, Monyer H, Jonas PM, Frotscher M, Lubke J. 1997. A novel type of GABAergic interneuron connecting the input and the output regions of the hippocampus. Journal of Neuroscience. 17(14), 5380–5394.","apa":"Ceranik, K., Bender, R., Geiger, J., Monyer, H., Jonas, P. M., Frotscher, M., & Lubke, J. (1997). A novel type of GABAergic interneuron connecting the input and the output regions of the hippocampus. Journal of Neuroscience. Society for Neuroscience. https://doi.org/10.1523/JNEUROSCI.17-14-05380.1997","ama":"Ceranik K, Bender R, Geiger J, et al. A novel type of GABAergic interneuron connecting the input and the output regions of the hippocampus. Journal of Neuroscience. 1997;17(14):5380-5394. doi:10.1523/JNEUROSCI.17-14-05380.1997","chicago":"Ceranik, Katya, Roland Bender, Jörg Geiger, Hannah Monyer, Peter M Jonas, Michael Frotscher, and Joachim Lubke. “A Novel Type of GABAergic Interneuron Connecting the Input and the Output Regions of the Hippocampus.” Journal of Neuroscience. Society for Neuroscience, 1997. https://doi.org/10.1523/JNEUROSCI.17-14-05380.1997.","ieee":"K. Ceranik et al., “A novel type of GABAergic interneuron connecting the input and the output regions of the hippocampus.,” Journal of Neuroscience, vol. 17, no. 14. Society for Neuroscience, pp. 5380–5394, 1997."},"external_id":{"pmid":["9204922"]},"doi":"10.1523/JNEUROSCI.17-14-05380.1997","day":"15","abstract":[{"text":"The main excitatory pathway of the hippocampal formation is controlled by a network of morphologically distinct populations of GABAergic interneurons. Here we describe a novel type of GABAergic interneuron located in the outer molecular layer (OML) of the rat dentate gyrus with a long- range forward projection from the dentate gyrus to the subiculum across the hippocampal fissure, OML interneurons were recorded in hippocampal slices by using the whole-cell patch-clamp configuration. During recording, cells were filled with biocytin for subsequent light and electron microscopic analysis. Neurons projecting to the subiculum were distributed throughout the entire OML. They had round or ovoid somata and a multipolar dendritic morphology. Two axonal domains could be distinguished: an extensive, tangential distribution within the OML and a long-range vertical and tangential projection to layer 1 and stratum pyramidale of the subiculum. Symmetric synaptic contacts were established by these interneurons on dendritic shafts in the OML and subiculum. OML interneurons were characterized physiologically by short action potential duration and marked afterhyperpolarization that followed the spike. On sustained current injection, they generated high- frequency (up to 130 Hz, 34°C) trains of action potentials with only little adaptation. In situ hybridization and single-call RT-PCR analysis for GAD67 mRNA confirmed the GABAergic nature of OML interneurons. GABAergic interneurons in the OML projecting to the subiculum connect the input and output regions of the hippocampus. Hence, they could mediate long-range feed- forward inhibition and may participate in an oscillating cross-regional interneuron network that may synchronize the activity of spatially distributed principal neurons in the dentate gyrus and the subiculum.","lang":"eng"}],"acknowledgement":"This work was supported by the Deutsche Forschungsgemeinschaft (SFB 505/A3 and Leibniz program to M.F., SFB 505/C5 to P.J., and DFG 432/3 to H.M.) We thank Drs. H. Scharfman, M. Häusser, and I. Vida for critically reading an earlier version of this manuscript. We are also grateful to B. Joch, S. Nestel, M. Winter, and U. Amtmann for excellent technical assistance.","volume":17,"extern":"1","publication":"Journal of Neuroscience","oa_version":"Published Version","month":"07","language":[{"iso":"eng"}],"date_published":"1997-07-15T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["0270-6474"]},"oa":1,"publist_id":"2904","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6793821/","open_access":"1"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public"},{"month":"06","oa_version":"None","publication":"Neuron","language":[{"iso":"eng"}],"oa":1,"publist_id":"2903","publication_identifier":{"issn":["0896-6273"]},"type":"journal_article","date_published":"1997-06-01T00:00:00Z","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/S0896627300803396?via%3Dihub","open_access":"1"}],"intvolume":" 18","title":"Submillisecond AMPA receptor-mediated signaling at a principal neuron-interneuron synapse","date_created":"2018-12-11T12:03:34Z","article_processing_charge":"No","publication_status":"published","issue":"6","author":[{"full_name":"Geiger, Jörg","last_name":"Geiger","first_name":"Jörg"},{"first_name":"Joachim","last_name":"Lubke","full_name":"Lubke, Joachim"},{"first_name":"Arnd","last_name":"Roth","full_name":"Roth, Arnd"},{"first_name":"Michael","last_name":"Frotscher","full_name":"Frotscher, Michael"},{"last_name":"Jonas","first_name":"Peter M","full_name":"Jonas, Peter M","orcid":"0000-0001-5001-4804","id":"353C1B58-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"3484","pmid":1,"article_type":"original","publisher":"Elsevier","quality_controlled":"1","page":"1009 - 1023","abstract":[{"lang":"eng","text":"Glutamatergic transmission at a principal neuroninterneuron synapse was investigated by dual whole-cell patch-clamp recording in rat hippocampal slices combined with morphological analysis. Evoked EPSPs with rapid time course (half duration ≃ 4 ms; 34°C) were generated at multiple synaptic contacts established on the interneuron dendrites close to the soma. The underlying postsynaptic conductance change showed a submillisecond rise and decay, due to the precise timing of glutamate release and the rapid deactivation of the postsynaptic AMPA receptors. Simulations based on a compartmental model of the interneuron indicated that the rapid postsynaptic conductance change determines the shape and the somatodendritic integration of EPSPs, thus enabling interneurons to detect synchronous principal neuron activity."}],"day":"01","doi":"10.1016/S0896-6273(00)80339-6","external_id":{"pmid":["9208867 "]},"year":"1997","citation":{"ama":"Geiger J, Lubke J, Roth A, Frotscher M, Jonas PM. Submillisecond AMPA receptor-mediated signaling at a principal neuron-interneuron synapse. Neuron. 1997;18(6):1009-1023. doi:10.1016/S0896-6273(00)80339-6","apa":"Geiger, J., Lubke, J., Roth, A., Frotscher, M., & Jonas, P. M. (1997). Submillisecond AMPA receptor-mediated signaling at a principal neuron-interneuron synapse. Neuron. Elsevier. https://doi.org/10.1016/S0896-6273(00)80339-6","ieee":"J. Geiger, J. Lubke, A. Roth, M. Frotscher, and P. M. Jonas, “Submillisecond AMPA receptor-mediated signaling at a principal neuron-interneuron synapse,” Neuron, vol. 18, no. 6. Elsevier, pp. 1009–1023, 1997.","chicago":"Geiger, Jörg, Joachim Lubke, Arnd Roth, Michael Frotscher, and Peter M Jonas. “Submillisecond AMPA Receptor-Mediated Signaling at a Principal Neuron-Interneuron Synapse.” Neuron. Elsevier, 1997. https://doi.org/10.1016/S0896-6273(00)80339-6.","mla":"Geiger, Jörg, et al. “Submillisecond AMPA Receptor-Mediated Signaling at a Principal Neuron-Interneuron Synapse.” Neuron, vol. 18, no. 6, Elsevier, 1997, pp. 1009–23, doi:10.1016/S0896-6273(00)80339-6.","short":"J. Geiger, J. Lubke, A. Roth, M. Frotscher, P.M. Jonas, Neuron 18 (1997) 1009–1023.","ista":"Geiger J, Lubke J, Roth A, Frotscher M, Jonas PM. 1997. Submillisecond AMPA receptor-mediated signaling at a principal neuron-interneuron synapse. Neuron. 18(6), 1009–1023."},"date_updated":"2022-08-22T08:41:54Z","extern":"1","volume":18,"acknowledgement":"We thank Drs. J. Bischofberger, M. Ha¨usser, and I. Vida for critically T.F. reading the manuscript; S. Nestel, B. Joch, M. Winter, B. Freudenberg, and K. Zipfel for excellent technical assistance; and B. Hillers Hestrin, S. for typing. Supported by the DFG (SFB 505/C5 to P. J. and Leibniz program to M. F.)"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1160038/"}],"oa":1,"publist_id":"2902","publication_identifier":{"issn":["0022-3751"]},"type":"journal_article","date_published":"1997-12-15T00:00:00Z","language":[{"iso":"eng"}],"month":"12","oa_version":"Published Version","publication":"Journal of Physiology","extern":"1","acknowledgement":"We thank Drs J. Bischofberger and J. R. P. Geiger for critically reading the manuscript, Mrs B. Plessow-Freudenberg and K. Zipfel for technical assistance, and Mrs B. Hillers for typing. This work was supported by the German Israeli Foundation grant I 0352–073.01/94 to P. J.","volume":505,"abstract":[{"lang":"eng","text":"1. GABAergic interneurones differ from glutamatergic principal neurones in their ability to discharge high-frequency trains of action potentials without adaptation. To examine whether Na+ channel gating contributed to these differences, Na+ currents were recorded in nucleated patches from interneurones (dentate gyrus basket cells, BCs) and principal neurones (CA1 pyramidal cells, PCs) of rat hippocampal slices. 2. The voltage dependence of Na+ channel activation in BCs and PCs was similar. The slope factors of the activation curves, fitted with Boltzmann functions raised to the third power, were 11.5 and 11.8 mV, and the mid-point potentials were -25.1 and -23.9 mV, respectively. 3. Whereas the time course of Na+ channel activation (-30 to +40 mV) was similar, the deactivation kinetics (-100 to -40 mV) were faster in BCs than in PCs (tail current decay time constants, 0.13 and 0.20 ms, respectively, at -40 mV). 4. Na+ channels in BCs and PCs differed in the voltage dependence of inactivation. The slope factors of the steady-state inactivation curves fitted with Boltzmann functions were 6.7 and 10.7 mV, and the mid-point potentials were -58.3 and -62.9 mV, respectively. 5. The onset of Na+ channel inactivation at -55 mV was slower in BC's than in PCs; the inactivation time constants were 18.6 and 9.3 ms, respectively. At more positive potentials the differences in inactivation onset were smaller. 6. The time course of recovery of Na+ channels from inactivation induced by a 30 ms pulse was fast and mono-exponential (τ = 2.0 ms at -120 mV) in BCs, whereas it was slower and biexponential in PCs (τ1 = 2.0 ms and τ2 = 133 ms; amplitude contribution of the slow component, 15%). 7. We conclude that Na+ channels of BCs and PCs differ in gating properties that contribute to the characteristic action potential patterns of the two types of neurones."}],"day":"15","doi":"10.1111/j.1469-7793.1997.593ba.x","external_id":{"pmid":["9457638"]},"year":"1997","citation":{"ista":"Martina M, Jonas PM. 1997. Functional differences in Na+ channel gating between fast-spiking interneurones and principal neurones in rat hippocampus. Journal of Physiology. 505(3), 593–603.","short":"M. Martina, P.M. Jonas, Journal of Physiology 505 (1997) 593–603.","mla":"Martina, Marco, and Peter M. Jonas. “Functional Differences in Na+ Channel Gating between Fast-Spiking Interneurones and Principal Neurones in Rat Hippocampus.” Journal of Physiology, vol. 505, no. 3, Wiley-Blackwell, 1997, pp. 593–603, doi:10.1111/j.1469-7793.1997.593ba.x.","ieee":"M. Martina and P. M. Jonas, “Functional differences in Na+ channel gating between fast-spiking interneurones and principal neurones in rat hippocampus,” Journal of Physiology, vol. 505, no. 3. Wiley-Blackwell, pp. 593–603, 1997.","chicago":"Martina, Marco, and Peter M Jonas. “Functional Differences in Na+ Channel Gating between Fast-Spiking Interneurones and Principal Neurones in Rat Hippocampus.” Journal of Physiology. Wiley-Blackwell, 1997. https://doi.org/10.1111/j.1469-7793.1997.593ba.x.","apa":"Martina, M., & Jonas, P. M. (1997). Functional differences in Na+ channel gating between fast-spiking interneurones and principal neurones in rat hippocampus. Journal of Physiology. Wiley-Blackwell. https://doi.org/10.1111/j.1469-7793.1997.593ba.x","ama":"Martina M, Jonas PM. Functional differences in Na+ channel gating between fast-spiking interneurones and principal neurones in rat hippocampus. Journal of Physiology. 1997;505(3):593-603. doi:10.1111/j.1469-7793.1997.593ba.x"},"date_updated":"2022-08-22T08:25:26Z","article_type":"original","publisher":"Wiley-Blackwell","quality_controlled":"1","page":"593 - 603","intvolume":" 505","title":"Functional differences in Na+ channel gating between fast-spiking interneurones and principal neurones in rat hippocampus","article_processing_charge":"No","date_created":"2018-12-11T12:03:34Z","publication_status":"published","issue":"3","author":[{"full_name":"Martina, Marco","last_name":"Martina","first_name":"Marco"},{"last_name":"Jonas","first_name":"Peter M","full_name":"Jonas, Peter M","orcid":"0000-0001-5001-4804","id":"353C1B58-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"3485","pmid":1},{"language":[{"iso":"eng"}],"publication":"Journal of Physiology","month":"10","oa_version":"Published Version","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1159916/"}],"type":"journal_article","date_published":"1997-10-15T00:00:00Z","publist_id":"2901","oa":1,"publication_identifier":{"issn":["0022-3751"]},"quality_controlled":"1","page":"359 - 365","article_type":"original","publisher":"Wiley-Blackwell","issue":"Pt 2","author":[{"last_name":"Bischofberger","first_name":"Joseph","full_name":"Bischofberger, Joseph"},{"id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","full_name":"Jonas, Peter M","first_name":"Peter M","last_name":"Jonas"}],"pmid":1,"_id":"3486","intvolume":" 504","title":"Action potential propagation into the presynaptic dendrites of rat mitral cells","date_created":"2018-12-11T12:03:35Z","article_processing_charge":"No","publication_status":"published","extern":"1","acknowledgement":"We thank Drs J. R. P. Geiger, M. Martina, and D. Schild for critically reading the manuscript, and Mrs B. Plessow-Freudenberg for technical assistance. This work was supported by DFG grant BI 642/1-1 and German Israeli Foundation grant I 0352-073.01/94.","volume":504,"external_id":{"pmid":["9365910"]},"citation":{"ieee":"J. Bischofberger and P. M. Jonas, “Action potential propagation into the presynaptic dendrites of rat mitral cells,” Journal of Physiology, vol. 504, no. Pt 2. Wiley-Blackwell, pp. 359–365, 1997.","chicago":"Bischofberger, Joseph, and Peter M Jonas. “Action Potential Propagation into the Presynaptic Dendrites of Rat Mitral Cells.” Journal of Physiology. Wiley-Blackwell, 1997. https://doi.org/10.1111/j.1469-7793.1997.359be.x.","apa":"Bischofberger, J., & Jonas, P. M. (1997). Action potential propagation into the presynaptic dendrites of rat mitral cells. Journal of Physiology. Wiley-Blackwell. https://doi.org/10.1111/j.1469-7793.1997.359be.x","ama":"Bischofberger J, Jonas PM. Action potential propagation into the presynaptic dendrites of rat mitral cells. Journal of Physiology. 1997;504(Pt 2):359-365. doi:10.1111/j.1469-7793.1997.359be.x","ista":"Bischofberger J, Jonas PM. 1997. Action potential propagation into the presynaptic dendrites of rat mitral cells. Journal of Physiology. 504(Pt 2), 359–365.","mla":"Bischofberger, Joseph, and Peter M. Jonas. “Action Potential Propagation into the Presynaptic Dendrites of Rat Mitral Cells.” Journal of Physiology, vol. 504, no. Pt 2, Wiley-Blackwell, 1997, pp. 359–65, doi:10.1111/j.1469-7793.1997.359be.x.","short":"J. Bischofberger, P.M. Jonas, Journal of Physiology 504 (1997) 359–365."},"year":"1997","date_updated":"2022-08-19T12:02:21Z","abstract":[{"lang":"eng","text":"1. Dendritic patch-clamp recordings were obtained from mitral cells in rat olfactory bulb slices, up to 350 μm from the soma. Simultaneous dendritic and somatic whole-cell recordings indicated that action potentials (APs) evoked by somatic or dendritic current injection were initiated near the soma. Both the large amplitude (100.7 ± 1.1 mV) and the short duration (1.38 ± 0.07 ms) of the AP were maintained as the AP propagated back into the primary mitral cell dendrites. 2. Outside-out patches isolated from mitral cell dendrites contained voltage-gated Na+ channels (peak conductance density, 90 pS μm-2 at -10 mV). When an AP was used as a somatic voltage-clamp command in the presence of 1 μM tetrodotoxin (TTX), the amplitude of the dendritic potential was attenuated to 48 ± 14 mV. This shows that dendritic Na+ channels support the active back-propagation of APs. 3. Dendritic patches contained voltage-gated K+ channels with high density (conductance density, 513 pS μm-2 at 30 mV. Dendritic K+ currents were reduced to 35% by 1 mM external tetraethylammonium chloride (TEACl). When an AP was used as a somatic voltage clamp command in the presence of TEACl, the dendritic potential was markedly prolonged. This indicates that dendritic K+ channels mediate the fast repolarization of dendritic APs. 4. We conclude that voltage gated Na+ and K+ channels support dendritic APs with large amplitudes and short durations that may trigger fast transmitter release at dendrodendritic synapses in the olfactory bulb."}],"day":"15","doi":"10.1111/j.1469-7793.1997.359be.x"},{"page":"1187 - 1203","quality_controlled":"1","article_type":"original","publisher":"Elsevier","author":[{"last_name":"Bragin","first_name":"Anatol","full_name":"Bragin, Anatol"},{"id":"3FA14672-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5193-4036","full_name":"Csicsvari, Jozsef L","first_name":"Jozsef L","last_name":"Csicsvari"},{"last_name":"Penttonen","first_name":"Markku","full_name":"Penttonen, Markku"},{"last_name":"Buzsáki","first_name":"György","full_name":"Buzsáki, György"}],"issue":"4","pmid":1,"_id":"3541","title":"Epileptic afterdischarge in the hippocampal-entorhinal system: Current source density and unit studies","intvolume":" 76","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:03:52Z","extern":"1","volume":76,"acknowledgement":"We thank K. Wise and J. Hetke for providing us the silicon probes, J. J. Chrobak, S. L-W. Leung, G. G. Somjen and R. D. Traub for their comments on the manuscript. This work was supported by NINDS (NS34994; 1P41RR09754; NS33310) and the Whitehall Foundation. M. Penttonen was a visiting scholar at Rutgers University, supported by the Finnish Academy of Sciences and the A. I. Virtanen Institute.","external_id":{"pmid":["9027878"]},"date_updated":"2022-08-19T11:53:06Z","citation":{"apa":"Bragin, A., Csicsvari, J. L., Penttonen, M., & Buzsáki, G. (1997). Epileptic afterdischarge in the hippocampal-entorhinal system: Current source density and unit studies. Neuroscience. Elsevier. https://doi.org/10.1016/S0306-4522(96)00446-0","ama":"Bragin A, Csicsvari JL, Penttonen M, Buzsáki G. Epileptic afterdischarge in the hippocampal-entorhinal system: Current source density and unit studies. Neuroscience. 1997;76(4):1187-1203. doi:10.1016/S0306-4522(96)00446-0","ieee":"A. Bragin, J. L. Csicsvari, M. Penttonen, and G. Buzsáki, “Epileptic afterdischarge in the hippocampal-entorhinal system: Current source density and unit studies,” Neuroscience, vol. 76, no. 4. Elsevier, pp. 1187–1203, 1997.","chicago":"Bragin, Anatol, Jozsef L Csicsvari, Markku Penttonen, and György Buzsáki. “Epileptic Afterdischarge in the Hippocampal-Entorhinal System: Current Source Density and Unit Studies.” Neuroscience. Elsevier, 1997. https://doi.org/10.1016/S0306-4522(96)00446-0.","mla":"Bragin, Anatol, et al. “Epileptic Afterdischarge in the Hippocampal-Entorhinal System: Current Source Density and Unit Studies.” Neuroscience, vol. 76, no. 4, Elsevier, 1997, pp. 1187–203, doi:10.1016/S0306-4522(96)00446-0.","short":"A. Bragin, J.L. Csicsvari, M. Penttonen, G. Buzsáki, Neuroscience 76 (1997) 1187–1203.","ista":"Bragin A, Csicsvari JL, Penttonen M, Buzsáki G. 1997. Epileptic afterdischarge in the hippocampal-entorhinal system: Current source density and unit studies. Neuroscience. 76(4), 1187–1203."},"year":"1997","abstract":[{"text":"The contribution of the various hippocampal regions to the maintenance of epileptic activity, induced by stimulation of the perforant path or commissural system, was examined in the awake rat. Combination of multiple-site recordings with silicon probes, current source density analysis and unit recordings allowed for a high spatial resolution of the field events. Following perforant path stimulation, seizures began in the dentate gyrus, followed by events in the CA3-CA1 regions. After commissural stimulation, rhythmic bursts in the CA3-CA1 circuitry preceded the activation of the dentate gyrus. Correlation of events in the different subregions indicated that the sustained rhythmic afterdischarge (2-6 Hz) could not be explained by a cycle-by-cycle excitation of principal cell populations in the hippocampal-entorhinal loop. The primary afterdischarge always terminated in the CA1 region, followed by the dentate gyrus, CA3 region and the entorhinal cortex. The duration and pattern of the hippocampal afterdischarge was essentially unaffected by removal of the entorhinal cortex. The emergence of large population spike bursts coincided with a decreased discharge of interneurons in both CAI and hilar regions. The majority of hilar interneurons displayed a strong amplitude decrement prior to the onset of population spike phase of the afterdischarge. These findings suggest that (i) afterdischarges can independently arise in the CA3-CA1 and entorhinal-dentate gyrus circuitries, (ii) reverberation of excitation in the hippocampal-entorhinal loop is not critical for the maintenance of afterdischarges and (iii) decreased activity of the interneuronal network may release population bursting of principal cells. ","lang":"eng"}],"doi":"10.1016/S0306-4522(96)00446-0","day":"15","language":[{"iso":"eng"}],"publication":"Neuroscience","month":"01","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","date_published":"1997-01-15T00:00:00Z","type":"journal_article","publist_id":"2844","publication_identifier":{"issn":["0306-4522"]}},{"day":"01","doi":"10.1093/genetics/146.1.427","abstract":[{"text":"This paper derives the long-term effective size, Ne, for a general model of population subdivision, allowing for differential deme fitness, variable emigration and immigration rates, extinction, colonization, and correlations across generations in these processes. We show that various long-term measures of Ne are equivalent. The effective size of a metapopulation can be expressed in a variety of ways. At a demographic equilibrium, Ne can be derived from the demography by combining information about the ultimate contribution of each deme to the future genetic make-up of the population and Wright's FST's. The effective size is given by Ne = 1/(1 + var (upsilon) ((1 - FST)/Nin), where n is the number of demes, theta i is the eventual contribution of individuals in deme i to the whole population (scaled such that sigma theta i = n), and < > denotes an average weighted by theta i. This formula is applied to a catastrophic extinction model (where sites are either empty or at carrying capacity) and to a metapopulation model with explicit dynamics, where extinction is caused by demographic stochasticity and by chaos. Contrary to the expectation from the standard island model, the usual effect of population subdivision is to decrease the effective size relative to a panmictic population living on the same resource.","lang":"eng"}],"citation":{"chicago":"Whitlock, Michael, and Nicholas H Barton. “The Effective Size of a Subdivided Population.” Genetics. Genetics Society of America, 1997. https://doi.org/10.1093/genetics/146.1.427.","ieee":"M. Whitlock and N. H. Barton, “The effective size of a subdivided population,” Genetics, vol. 146, no. 1. Genetics Society of America, pp. 427–441, 1997.","apa":"Whitlock, M., & Barton, N. H. (1997). The effective size of a subdivided population. Genetics. Genetics Society of America. https://doi.org/10.1093/genetics/146.1.427","ama":"Whitlock M, Barton NH. The effective size of a subdivided population. Genetics. 1997;146(1):427-441. doi:10.1093/genetics/146.1.427","ista":"Whitlock M, Barton NH. 1997. The effective size of a subdivided population. Genetics. 146(1), 427–441.","short":"M. Whitlock, N.H. Barton, Genetics 146 (1997) 427–441.","mla":"Whitlock, Michael, and Nicholas H. Barton. “The Effective Size of a Subdivided Population.” Genetics, vol. 146, no. 1, Genetics Society of America, 1997, pp. 427–41, doi:10.1093/genetics/146.1.427."},"year":"1997","date_updated":"2022-08-19T10:01:10Z","external_id":{"pmid":["9136031 "]},"acknowledgement":"This paper has benefited greatly from the kind efforts oF ARMANDO CABALLERO, PETER KEIGHTLEY, BEATE NÜRNBERCER and SALLY OTTO in reading and discussing the manuscript. We also thank MONTY SLATKIN and three anonymous reviewers for their helpful comments. One of these reviewers in particular greatly improved this paper. The work reported here was supported by a grant from the Science and Engineering Research Council (U.R) and the Darwin Trust of Edinburgh, as well as by the Natural Sciences and Engineering Research Council (Canada).","volume":146,"extern":"1","date_created":"2018-12-11T12:04:20Z","article_processing_charge":"No","publication_status":"published","intvolume":" 146","title":"The effective size of a subdivided population","scopus_import":"1","pmid":1,"_id":"3630","issue":"1","author":[{"full_name":"Whitlock, Michael","first_name":"Michael","last_name":"Whitlock"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H"}],"publisher":"Genetics Society of America","article_type":"original","quality_controlled":"1","page":"427 - 441","publication_identifier":{"issn":["0016-6731"]},"publist_id":"2753","oa":1,"type":"journal_article","date_published":"1997-05-01T00:00:00Z","main_file_link":[{"url":"https://academic.oup.com/genetics/article/146/1/427/6053913","open_access":"1"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","oa_version":"Published Version","month":"05","publication":"Genetics","language":[{"iso":"eng"}]}]