Journal of the Association for Computing Machinery Short Title: J. Assoc. Comput. Mach. Publisher: Association for Computing Machinery (ACM), New York, NY ISSN: 0004-5411 Online: http://dl.acm.org/citation.cfm?id=J401 Successor: Journal of the ACM Comments: Journal; No longer indexed Documents Indexed: 1,779 Publications (1955–1995) References Indexed: 15 Publications with 169 References. all top 5 Latest Issues 42, No. 6 (1995) 42, No. 5 (1995) 42, No. 4 (1995) 42, No. 3 (1995) 42, No. 2 (1995) 42, No. 1 (1995) 41, No. 6 (1994) 41, No. 5 (1994) 41, No. 4 (1994) 41, No. 3 (1994) 41, No. 2 (1994) 41, No. 1 (1994) 40, No. 5 (1993) 40, No. 4 (1993) 40, No. 3 (1993) 40, No. 2 (1993) 40, No. 1 (1993) 39, No. 4 (1992) 39, No. 3 (1992) 39, No. 2 (1992) 39, No. 1 (1992) 38, No. 4 (1991) 38, No. 3 (1991) 38, No. 2 (1991) 38, No. 1 (1991) 37, No. 4 (1990) 37, No. 3 (1990) 37, No. 2 (1990) 37, No. 1 (1990) 36, No. 4 (1989) 36, No. 3 (1989) 36, No. 2 (1989) 36, No. 1 (1989) 35, No. 4 (1988) 35, No. 3 (1988) 35, No. 2 (1988) 35, No. 1 (1988) 34 (1987) 33 (1986) 32 (1985) 31 (1984) 30 (1983) 29 (1982) 28 (1981) 27 (1980) 26 (1979) 25 (1978) 24 (1977) 23 (1976) 22 (1975) 21 (1974) 20 (1973) 19 (1972) 18 (1971) 17 (1970) 16 (1969) 15 (1968) 14 (1967) 13 (1966) 12 (1965) 11 (1964) 10 (1963) 9 (1962) 8 (1961) 7 (1960) 6 (1959) 5 (1958) 2 (1955) all top 5 Authors 21 Ginsburg, Seymour 18 Tarjan, Robert Endre 15 Papadimitriou, Christos Harilaos 15 Ullman, Jeffrey David 12 Coffman, Edward Grady jun. 12 Halpern, Joseph Yehuda 12 Lynch, Nancy Ann 12 Yannakakis, Mihalis 11 Galil, Zvi 11 Rosenberg, Arnold Leonard 11 Sahni, Sartaj K. 10 Fagin, Ronald 10 Slagle, James R. 9 Dolev, Danny 9 Harrison, Michael A. 9 Ibarra, Oscar H. 9 Kung, H. T. 9 Winograd, Shmuel 9 Yao, Andrew Chi-Chih 8 Fischer, Michael J. 8 Sagiv, Yehoshua 8 Traub, Joseph Frederick 7 Adiri, Igal 7 Aho, Alfred Vaino 7 Greibach, Sheila A. 7 Hopcroft, John Edward H. 7 Hunt, Harry Bowen III 7 Karp, Richard Manning 7 Konheim, Alan G. 7 Megiddo, Nimrod 7 Salton, Gerard 7 Stockmeyer, Larry J. 7 Towsley, Donald Fred 7 Valiant, Leslie Gabriel 7 Wong, Chak-Kuen 7 Yu, Clement T. 6 Attiya, Hagit 6 Curtis, H. Allen 6 Garey, Michael Randolph 6 Lipton, Richard Jay 6 Meyer, Albert Ronald 6 Mitra, Debasis 6 Sethi, Ravi 5 Brent, Richard Peirce 5 Bruno, John L. 5 Chaitin, Gregory John 5 Dwork, Cynthia 5 Even, Shimon 5 Frederickson, Greg N. 5 Gelenbe, Sami Erol 5 Gonzalez, Teofilo F. 5 Hartmanis, Juris 5 Iglehart, Donald Lee 5 Johnson, Donald B. 5 Kleinrock, Leonard 5 Lamport, Leslie 5 Loveland, Donald W. 5 Manna, Zohar 5 Muntz, Richard R. 5 Pease, Marshall C. III 5 Peleg, David 5 Pippenger, Nicholas J. 5 Preparata, Franco P. 5 Reif, John H. 5 Reischuk, Rüdiger 5 Shostak, Robert E. 5 Upfal, Eli 5 Vardi, Moshe Ya’akov 5 Wagner, Robert A. 5 Wigderson, Avi 4 Baccelli, François Louis 4 Baker, Brenda S. 4 Beeri, Catriel 4 Blum, Manuel 4 Book, Ronald Vernon 4 Brzozowski, Janusz Antoni 4 Chandy, Kanianthra Mani 4 Chazelle, Bernard 4 Ehrenfeucht, Andrzej 4 Fischer, Patrick Carl 4 Fredman, Michael L. 4 Gabow, Harold N. 4 Gill, Arthur 4 Gottlob, Georg 4 Gurari, Eitan M. 4 Hennessy, Matthew C. B. 4 Henschen, Lawrence J. 4 Hirschberg, Daniel S. 4 Hofri, Micha 4 Horowitz, Ellis 4 Ja’Ja’, Joseph F. 4 Johnson, David Stifler 4 Kannan, Ravindran 4 Kosaraju, S. Rao 4 Ladner, Richard E. 4 Lavenberg, Stephen S. 4 Maier, David 4 Mansour, Yishay 4 Mehlhorn, Kurt 4 Merritt, Michael J. ...and 1,683 more Authors all top 5 Fields 1,088 Computer science (68-XX) 154 Numerical analysis (65-XX) 122 Mathematical logic and foundations (03-XX) 119 Operations research, mathematical programming (90-XX) 92 Information and communication theory, circuits (94-XX) 82 Combinatorics (05-XX) 58 Probability theory and stochastic processes (60-XX) 20 Linear and multilinear algebra; matrix theory (15-XX) 19 Number theory (11-XX) 11 Group theory and generalizations (20-XX) 10 Field theory and polynomials (12-XX) 9 Statistics (62-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Convex and discrete geometry (52-XX) 6 Systems theory; control (93-XX) 5 General algebraic systems (08-XX) 5 Approximations and expansions (41-XX) 4 Biology and other natural sciences (92-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Real functions (26-XX) 3 Harmonic analysis on Euclidean spaces (42-XX) 3 Integral equations (45-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 2 History and biography (01-XX) 2 Associative rings and algebras (16-XX) 2 Functions of a complex variable (30-XX) 2 Ordinary differential equations (34-XX) 2 Partial differential equations (35-XX) 2 Operator theory (47-XX) 1 Commutative algebra (13-XX) 1 Nonassociative rings and algebras (17-XX) 1 Integral transforms, operational calculus (44-XX) 1 Geometry (51-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Geophysics (86-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 1,556 Publications have been cited 47,521 times in 34,847 Documents Cited by ▼ Year ▼ Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088 Goemans, Michel X.; Williamson, David P. 780 1995 A machine-oriented logic based on the resolution principle. Zbl 0139.12303 Robinson, J. A. 634 1965 Impossibility of distributed consensus with one faulty process. Zbl 0629.68027 Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. 574 1985 Alternation. Zbl 0473.68043 Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. 565 1981 A computing procedure for quantification theory. Zbl 0212.34203 Davis, M.; Putnam, H. 445 1960 Fast probabilistic algorithms for verification of polynomial identities. Zbl 0452.68050 Schwartz, J. T. 437 1980 Theoretical improvements in algorithmic efficiency for network flow problems. Zbl 0318.90024 Edmonds, Jack; Karp, Richard M. 419 1972 Fibonacci heaps and their uses in improved network optimization algorithms. Zbl 1412.68048 Fredman, Michael L.; Tarjan, Robert Endre 388 1987 Integer programming formulation of traveling salesman problems. Zbl 0100.15101 Miller, C. E.; Tucker, A. W.; Zemlin, R. A. 376 1960 Optimal order of one-point and multipoint iteration. Zbl 0289.65023 Kung, H. T.; Traub, J. F. 371 1974 Confluent reductions: Abstract properties and applications to term rewriting systems. Zbl 0458.68007 Huet, Gerard 370 1980 Reaching agreement in the presence of faults. Zbl 0434.68031 Pease, M.; Shostak, R.; Lamport, L. 367 1980 Algebraic laws for nondeterminism and concurrency. Zbl 0629.68021 Hennessy, Matthew; Milner, Robin 363 1985 Scheduling algorithms for multiprogramming in a hard-real-time environment. Zbl 0265.68013 Liu, C. L.; Layland, James W. 362 1973 Color-coding. Zbl 0885.68116 Alon, Noga; Yuster, Raphael; Zwick, Uri 358 1995 Efficient planarity testing. Zbl 0307.68025 Hopcroft, John; Tarjan, Robert 343 1974 P-complete approximation problems. Zbl 0348.90152 Sahni, Sartaj; Gonzalez, Teofilo 339 1976 Learnability and the Vapnik-Chervonenkis dimension. Zbl 0697.68079 Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 330 1989 A new approach to the maximum-flow problem. Zbl 0661.90031 Goldberg, Andrew V.; Tarjan, Robert E. 311 1988 ’Direct search’ solution of numerical and statistical problems. Zbl 0111.12501 Hooke, R.; Jeeves, T. A. 289 1961 On context-free languages. Zbl 0154.25801 Parikh, R. J. 288 1966 The string-to-string correction problem. Zbl 0278.68032 Wagner, Robert A.; Fischer, Michael J. 283 1974 The well-founded semantics for general logic programs. Zbl 0799.68045 Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S. 282 1991 Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067 Baker, Brenda S. 279 1994 Fast approximation algorithms for the knapsack and sum of subset problems. Zbl 0345.90049 Ibarra, Oscar H.; Kim, Chul E. 277 1975 The semantics of predicate logic as a programming language. Zbl 0339.68004 van Emden, M. H.; Kowalski, R. A. 265 1976 A theory of communicating sequential processes. Zbl 0628.68025 Brookes, S. D.; Hoare, C. A. R.; Roscoe, A. W. 262 1984 Open, closed, and mixed networks of queues with different classes of customers. Zbl 0313.68055 Baskett, Forest; Chandy, K. Mani; Muntz, Richard R.; Palacios, Fernando G. 258 1975 A machine-independent theory of the complexity of recursive functions. Zbl 0155.01503 Blum, Manuel 256 1967 A framework for defining logics. Zbl 0778.03004 Harper, Robert; Honsell, Furio; Plotkin, Gordon 254 1993 Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Zbl 0799.68101 Goldreich, Oded; Micali, Silvio; Wigderson, Avi 248 1991 The complexity of propositional linear temporal logics. Zbl 0632.68034 Sistla, A. P.; Clarke, E. M. 246 1985 A technique for the numerical solution of certain integral equations of the first kind. Zbl 0108.29902 Phillips, D. L. 245 1962 Efficiency of a good but not linear set union algorithm. Zbl 0307.68029 Tarjan, Robert Endre 245 1975 Institutions: Abstract model theory for specification and programming. Zbl 0799.68134 Goguen, Joseph A.; Burstall, Rod M. 241 1992 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035 Garey, M. R.; Johnson, D. S. 239 1978 Initial algebra semantics and continuous algebras. Zbl 0359.68018 Goguen, J. A.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B. 230 1977 Open shop scheduling to minimize finish time. Zbl 0343.68031 Gonzalez, Teofilo; Sahni, Sartaj 224 1976 Derivatives of regular expressions. Zbl 0225.94044 Brzozowski, Janusz A. 223 1964 A theorem on Boolean matrices. Zbl 0118.33104 Warshall, S. 221 1962 Applying parallel computation algorithms in the design of serial algorithms. Zbl 0627.68034 Megiddo, Nimrod 218 1983 “Sometimes” and “not never” revisited: On branching versus linear time temporal logic. Zbl 0629.68020 Emerson, E. Allen; Halpern, Joseph Y. 217 1986 Iterative procedures for nonlinear integral equations. Zbl 0149.11503 Anderson, D. G. 215 1965 A space-economical suffix tree construction algorithm. Zbl 0329.68042 McCreight, Edward M. 213 1976 Approximation schemes for covering and packing problems in image processing and VLSI. Zbl 0633.68027 Hochbaum, Dorit S.; Maass, Wolfgang 210 1985 On the hardness of approximating minimization problems. Zbl 0814.68064 Lund, Carsten; Yannakakis, Mihalis 209 1994 A theory of program size formally identical to information theory. Zbl 0309.68045 Chaitin, Gregory J. 209 1975 On the structure of polynomial time reducibility. Zbl 0322.68028 Ladner, Richard E. 208 1975 On the desirability of acyclic database schemes. Zbl 0624.68087 Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis 205 1983 Reversal-bounded multicounter machines and their decision problems. Zbl 0365.68059 Ibarra, Oscar H. 189 1978 Storing a sparse table with O(1) worst case access time. Zbl 0629.68068 Fredman, Michael L.; Komlós, János; Szemerédi, Endre 188 1984 Self-adjusting binary search trees. Zbl 0631.68060 Sleator, Daniel Dominic; Tarjan, Robert Endre 184 1985 Algorithms for scheduling independent tasks. Zbl 0326.68024 Sahni, Sartaj K. 183 1976 Knowledge and common knowledge in a distributed environment. Zbl 0699.68115 Halpern, Joseph Y.; Moses, Yoram 181 1990 Algebraic methods for interactive proof systems. Zbl 0799.68097 Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam 177 1992 A fast direct solution of Poisson’s equation using Fourier analysis. Zbl 0139.10902 Hockney, R. W. 172 1965 A random polynomial-time algorithm for approximating the volume of convex bodies. Zbl 0799.68107 Dyer, Martin; Frieze, Alan; Kannan, Ravi 165 1991 Complexity of network synchronization. Zbl 0628.68045 Awerbuch, Baruch 163 1985 Linear programming in linear time when the dimension is fixed. Zbl 0637.90064 Megiddo, Nimrod 163 1984 A transformation system for developing recursive programs. Zbl 0343.68014 Burstall, R. M.; Darlington, John 162 1977 On communicating finite-state machines. Zbl 0512.68039 Brand, Daniel; Zafiropulo, Pitro 161 1983 Parallel prefix computation. Zbl 0445.68066 Ladner, Richard E.; Fischer, Michael J. 160 1980 Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006 Linial, Nathan; Mansour, Yishay; Nisan, Noam 158 1993 The parallel evaluation of general arithmetic expressions. Zbl 0276.68010 Brent, Richard P. 158 1974 Bisimulation can’t be traced. Zbl 0886.68027 Bloom, Bard; Istrail, Sorin; Meyer, Albert R. 155 1995 On the length of programs for computing finite binary sequences. Zbl 0158.25301 Chaitin, Gregory J. 151 1966 Indexed grammars - an extension of context-free grammars. Zbl 0175.27801 Aho, A. V. 148 1968 Dynamic programming treatment of the travelling salesman problem. Zbl 0106.14102 Bellman, Richard 146 1962 \(\mathrm{IP}=\mathrm{PSPACE}\). Zbl 0799.68096 Shamir, Adi 142 1992 Complete sets of reductions for some equational theories. Zbl 0479.68092 Peterson, Gerald E.; Stickel, Mark E. 136 1981 Atomic snapshots of shared memory. Zbl 0783.68029 Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir 136 1993 Hard examples for resolution. Zbl 0639.68093 Urquhart, Alasdair 133 1987 Efficient algorithms for shortest paths in sparse networks. Zbl 0343.68028 Johnson, Donald B. 131 1977 Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0222.02035 Cook, Stephen A. 130 1971 The complexity of probabilistic verification. Zbl 0885.68109 Courcoubetis, Costas; Yannakakis, Mihalis 129 1995 The complexity of searching a graph. Zbl 0637.68081 Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 128 1988 The complexity of some problems on subsequences and supersequences. Zbl 0371.68018 Maier, David 128 1978 Computing partitions with applications to the knapsack problem. Zbl 0329.90046 Horowitz, Ellis; Sahni, Sartaj 125 1974 A simple on-line bin-packing algorithm. Zbl 0629.68045 Lee, C. C.; Lee, D. T. 123 1985 Slowing down sorting networks to obtain faster sorting algorithms. Zbl 1378.68037 Cole, Richard 122 1987 A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078 Callahan, Paul B.; Kosaraju, S. Rao 119 1995 Asynchronous iterative methods for multiprocessors. Zbl 0372.68015 Baudet, Gerard M. 118 1978 Tree-manipulating systems and Church-Rosser theorems. Zbl 0267.68013 Rosen, Barry K. 118 1973 Degrees of acyclicity for hypergraphs and relational database schemes. Zbl 0624.68088 Fagin, Ronald 118 1983 Error analysis of direct methods of matrix inversion. Zbl 0109.09005 Wilkinson, J. H. 117 1961 Exact and approximate algorithms for scheduling nonidentical processors. Zbl 0329.68041 Horowitz, Ellis; Sahni, Sartaj 115 1976 A really temporal logic. Zbl 0807.68065 Alur, Rajeev; Henzinger, Thomas A. 115 1994 Many hard examples for resolution. Zbl 0712.03008 Chvátal, Vašek; Szemerédi, Endre 113 1988 Computational limitations on learning from examples. Zbl 0662.68086 Pitt, Leonard; Valiant, Leslie G. 113 1988 Inference of reversible languages. Zbl 0485.68066 Angluin, Dana 110 1982 On finding the maxima of a set of vectors. Zbl 0316.68030 Kung, H. T.; Luccio, F.; Preparata, F. P. 109 1975 Numerical inversion of Laplace transforms using a Fourier series approximation. Zbl 0315.65074 Crump, Kenny S. 109 1976 Reasoning about knowledge and probability. Zbl 0806.68098 Fagin, Ronald; Halpern, Joseph Y. 107 1994 Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. Zbl 0165.51403 Dubner, H.; Abate, J. 106 1968 A propositional modal logic of time intervals. Zbl 0799.68175 Halpern, Joseph Y.; Shoham, Yoav 105 1991 On the complexity of integer programming. Zbl 0468.68050 Papadimitriou, Christos H. 105 1981 Renaming in an asynchronous environment. Zbl 0699.68034 Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny; Peleg, David; Reischuk, Rüdiger 104 1990 A trade-off between space and efficiency for routing tables. Zbl 0900.68262 Peleg, David; Upfal, Eli 104 1989 A sufficient condition for backtrack-free search. Zbl 0477.68063 Freuder, Eugene C. 103 1982 Fast decision procedures based on congruence closure. Zbl 0441.68111 Nelson, Greg; Oppen, Derek C. 102 1980 Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088 Goemans, Michel X.; Williamson, David P. 780 1995 Color-coding. Zbl 0885.68116 Alon, Noga; Yuster, Raphael; Zwick, Uri 358 1995 Bisimulation can’t be traced. Zbl 0886.68027 Bloom, Bard; Istrail, Sorin; Meyer, Albert R. 155 1995 The complexity of probabilistic verification. Zbl 0885.68109 Courcoubetis, Costas; Yannakakis, Mihalis 129 1995 A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078 Callahan, Paul B.; Kosaraju, S. Rao 119 1995 Designing programs that check their work. Zbl 0886.68046 Blum, Manuel; Kannan, Sampath 82 1995 Sharing memory robustly in message-passing systems. Zbl 0886.68018 Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny 81 1995 Three logics for branching bisimulation. Zbl 0886.68064 de Nicola, Rocco; Vaandrager, Frits 76 1995 On the \(k\)-server conjecture. Zbl 0885.68075 Koutsoupias, Elias; Papadimitriou, Christos H. 74 1995 Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Zbl 0886.68077 Nebel, Bernhard; Bürckert, Hans-Jürgen 72 1995 The complexity of logic-based abduction. Zbl 0886.68121 Eiter, Thomas; Gottlob, Georg 68 1995 A randomized linear-time algorithm to find minimum spanning trees. Zbl 0886.68079 Karger, David R.; Klein, Philip N.; Tarjan, Robert E. 58 1995 Las Vegas algorithms for linear and integer programming when the dimension is small. Zbl 0885.65063 Clarkson, Kenneth L. 46 1995 Logical foundations of object-oriented and frame-based languages. Zbl 0885.68054 Kifer, Michael; Lausen, Georg; Wu, James 36 1995 Parametricity and local variables. Zbl 0885.68039 O’Hearn, P. W.; Tennent, R. D. 34 1995 Termination for direct sums of left-linear complete term rewriting systems. Zbl 0885.68093 Toyama, Y.; Klop, J. W.; Barendregt, H. P. 28 1995 Eigenvalues and expansion of regular graphs. Zbl 0885.68117 Kahale, Nabil 27 1995 On the minimality and global consistency of row-convex constraint networks. Zbl 0885.68087 van Beek, Peter; Dechter, Rina 25 1995 The isomorphism conjecture fails relative to a random oracle. Zbl 0886.68068 Kurtz, Stuart A.; Mahaney, Stephen R.; Royer, James S. 23 1995 On the existence of equilibria in noncooperative optimal flow control. Zbl 0885.68015 Korilis, Yannis A.; Lazar, Aurel A. 23 1995 Dynamic fault-tolerant clock synchronization. Zbl 0886.68008 Dolev, Danny; Halpern, Joseph Y.; Simons, Barbara; Strong, Ray 18 1995 Online tracking of mobile users. Zbl 0885.68017 Awerbuch, Baruch; Peleg, David 18 1995 NP trees and Carnap’s modal logic. Zbl 0886.68069 Gottlob, Georg 17 1995 On the impact of forgetting on learning machines. Zbl 0891.68088 Freivalds, Rūsiņš; Kinber, Efim; Smith, Carl H. 16 1995 Translating default logic into standard autoepistemic logic. Zbl 0884.03025 Gottlob, Georg 14 1995 A class of logic problems solvable by linear programming. Zbl 0900.03025 Conforti, Michele; Cornuéjols, Gérard 14 1995 Computing with faulty shared objects. Zbl 0890.68019 Afek, Yehuda; Greenberg, David S.; Merritt, Michael; Taubenfeld, Gadi 14 1995 Equational specifications, complete term rewriting systems, and computable and semicomputable algebras. Zbl 0885.68092 Bergstra, J. A.; Tucker, J. V. 13 1995 Constructing 1-writer multireader multivalued atomic variables from regular variables. Zbl 0886.68019 Haldar, S.; Vidyasankar, K. 6 1995 Provably correct theories of action. Zbl 0886.68122 Lin, Fangzhen; Shoham, Yoav 6 1995 Subquadratic zero-knowledge. Zbl 0890.68054 Boyar, Joan; Brassard, Gilles; Peralta, René 6 1995 Nearly optimal algorithms and bounds for multilayer channel routing. Zbl 0886.68021 Berger, Bonnie; Brady, Martin; Brown, Donna; Leighton, Tom 4 1995 Deterministic on-line routing on area-universal networks. Zbl 0885.68029 Bay, Paul; Bilardi, Gianfranco 4 1995 An optimal service policy for buffer systems. Zbl 0885.68016 Birman, Alexander; Gail, H. Richard; Hantler, Sidney L.; Rosberg, Zvi; Sidi, Moshe 4 1995 Calculating normalization constants of closed queuing networks by numerically inverting their generating functions. Zbl 0885.68026 Choudhury, Gagan L.; Leung, Kin K.; Whitt, Ward 4 1995 Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Zbl 0886.68017 Chien, Andrew A.; Kim, Jae H. 3 1995 Expected deadlock time in a multiprocessing system. Zbl 0885.68040 Compton, Kevin J.; Ravishankar, Chinya 3 1995 On the average communication complexity of asynchronous distributed algorithms. Zbl 0886.68070 Tsitsiklis, John N.; Stamoulis, George D. 2 1995 A constant-time optimal parallel string-matching algorithm. Zbl 0885.68082 Galil, Zvi 2 1995 Bounds on the speedup and efficiency of partial synchronization in parallel processing systems. Zbl 0886.68020 Chang, C. S.; Nelson, R. 1 1995 A theory of using history for equational systems with applications. Zbl 0885.68128 Verma, Rakesh M. 1 1995 Recoverable sequence transmission protocols. Zbl 0885.68018 Tempero, Ewan D.; Ladner, Richard E. 1 1995 Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067 Baker, Brenda S. 279 1994 On the hardness of approximating minimization problems. Zbl 0814.68064 Lund, Carsten; Yannakakis, Mihalis 209 1994 A really temporal logic. Zbl 0807.68065 Alur, Rajeev; Henzinger, Thomas A. 115 1994 Reasoning about knowledge and probability. Zbl 0806.68098 Fagin, Ronald; Halpern, Joseph Y. 107 1994 Cryptographic limitations on learning Boolean formulae and finite automata. Zbl 0807.68073 Kearns, Michael; Valiant, Leslie 79 1994 Biconnectivity approximations and graph carvings. Zbl 0822.68082 Khuller, Samir; Vishkin, Uzi 62 1994 On binary constraint problems. Zbl 0813.03045 Ladkin, Peter B.; Maddux, Roger D. 41 1994 Linear approximation of shortest superstrings. Zbl 0812.68075 Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis 40 1994 Counting networks. Zbl 0813.68050 Aspnes, James; Herlihy, Maurice; Shavit, Nir 34 1994 Are wait-free algorithms fast? Zbl 0812.68077 Attiya, Hagit; Lynch, Nancy; Shavit, Nir 30 1994 New approximation algorithms for graph coloring. Zbl 0821.68092 Blum, Avrim 28 1994 On the power of bounded concurrency. I: Finite automata. Zbl 0813.68138 Drusinsky, Doron; Harel, David 23 1994 Bounds on the time to reach agreement in the presence of timing uncertainty. Zbl 0807.68042 Attiya, Hagit; Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry 21 1994 Equational inference, canonical proofs, and proof orderings. Zbl 0806.68095 Bachmair, Leo; Dershowitz, Nachum 20 1994 Learning Boolean formulas. Zbl 0830.68108 Kearns, Michael; Li, Ming; Valiant, Leslie 19 1994 Instance complexity. Zbl 0807.68035 Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu 18 1994 Shortest paths in the plane with polygonal obstacles. Zbl 0814.68129 Storer, James A.; Reif, John H. 16 1994 Modular stratification and magic sets for datalog programs with negation. Zbl 0830.68028 Ross, Kenneth A. 16 1994 Probabilistic recurrence relations. Zbl 0830.68046 Karp, Richard M. 15 1994 Motion planning in the presence of moving obstacles. Zbl 0812.68115 Reif, John; Sharir, Micha 14 1994 Mixed integer programming methods for computing nonmonotonic deductive databases. Zbl 0830.68039 Bell, Colin; Nerode, Anil; Ng, Raymond T.; Subrahmanian, V. S. 13 1994 The elusive atomic register. Zbl 0806.68025 Singh, Ambuj K.; Anderson, James H.; Gouda, Mohamed G. 11 1994 Faster tree pattern matching. Zbl 0806.68055 Dubiner, Moshe; Galil, Zvi; Magen, Edith 10 1994 An analysis of ML typability. Zbl 0806.68016 Kfoury, A. J.; Tiuryn, J.; Urzyczyn, P. 10 1994 Average-case analysis of algorithms for matchings and related problems. Zbl 0829.68070 Motwani, Rajeev 10 1994 On solving equations and disequations. Zbl 0812.68064 Buntine, Wray L.; Bürckert, Hans-Jürgen 8 1994 Channel routing of multiterminal nets. Zbl 0812.68083 Gao, Shaodi; Kaufmann, Michael 8 1994 On the power of bounded concurrency. II: Pushdown automata. Zbl 0822.68067 Hirst, Tirza; Harel, David 6 1994 Diversity-based inference of finite automata. Zbl 0821.68085 Rivest, Ronald L.; Schapire, Robert E. 6 1994 Fishspear: A priority queue algorithm. Zbl 0807.68020 Fischer, Michael J.; Paterson, Michael S. 6 1994 Computing bounds on steady state availability of repairable computer systems. Zbl 0812.68059 Lui, John C. S.; Muntz, Richard R. 6 1994 Monte Carlo summation and integration applied to multiclass queuing networks. Zbl 0829.68010 Ross, Keith W.; Tsang, Danny H. K.; Wang, Jie 4 1994 The relationship between greedy parsing and symbolwise text compression. Zbl 0812.68071 Bell, Timothy C.; Witten, Ian H. 3 1994 Tight lower bounds for probabilistic solitude verification on anonymous rings. Zbl 0806.68038 Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David 2 1994 Efficient computation of Fourier inversion for finite groups. Zbl 0832.20027 Rockmore, Daniel N. 2 1994 Circumscription with homomorphisms: Solving the equality and counterexample problems. Zbl 0815.68089 Rathmann, Peter K.; Winslett, Marianne; Manasse, Mark 2 1994 Parallel linear programming in fixed dimension almost surely in constant time. Zbl 0807.90080 Alon, Noga; Megiddo, Nimrod 2 1994 Parallel algorithms for evaluating sequences of set-manipulation operations. Zbl 0830.68056 Atallah, Mikhail J.; Goodrich, Michael T.; Kosaraju, S. Rao 2 1994 Efficient decomposition methods for the analysis of multi-facility blocking models. Zbl 0812.68060 Conway, Adrian E.; Pinsky, Eugene; Tridandapani, Srinivasan 1 1994 A single-exponential upper bound for finding shortest paths in three dimensions. Zbl 0814.68079 Reif, John H.; Storer, James A. 1 1994 Optimal algorithms for parallel Givens factorization on a coarse-grained PRAM. Zbl 0802.65024 Cosnard, Michel; Daoudi, El Mostafa 1 1994 A framework for defining logics. Zbl 0778.03004 Harper, Robert; Honsell, Furio; Plotkin, Gordon 254 1993 Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006 Linial, Nathan; Mansour, Yishay; Nisan, Noam 158 1993 Atomic snapshots of shared memory. Zbl 0783.68029 Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir 136 1993 Recontamination does not help to search a graph. Zbl 0768.68048 Lapaugh, Andrea S. 101 1993 Perfectly secure message transmission. Zbl 0774.68017 Dolev, Danny; Dwork, Cynthia; Waarts, Orli; Yung, Moti 78 1993 Learning read-once formulas with queries. Zbl 0764.68139 Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek 54 1993 Complexity and algorithms for reasoning about time: A graph-theoretic approach. Zbl 0795.68095 Golumbic, Martin Charles; Shamir, Ron 48 1993 Decidability of bisimulation equivalence for processes generating context-free languages. Zbl 0801.68102 Baeten, J. C. M.; Bergstra, J. A.; Klop, J. W. 46 1993 An algebraic theory of graph reduction. Zbl 0795.68156 Arnborg, Stefan; Courcelle, Bruno; Proskurowski, Andrzej; Seese, Detlef 44 1993 Random walks on weighted graphs and applications to on-line algorithms. Zbl 0785.68071 Coppersmith, Don; Doyle, Peter; Raghavan, Prabhakar; Snir, Marc 34 1993 The minimum consistent DFA problem cannot be approximated within any polynomial. Zbl 0774.68084 Pitt, Leonard; Warmuth, Manfred K. 30 1993 Knowledge, probability, and adversaries. Zbl 0783.68120 Halpern, Joseph Y.; Tuttle, Mark R. 30 1993 Automatic recognition of tractability in inference relations. Zbl 0770.68106 McAllester, David A. 28 1993 Undecidable optimization problems for database logic programs. Zbl 0785.68021 Gaifman, Haim; Mairson, Harry; Sagiv, Yehoshua; Vardi, Moshe Y. 28 1993 Randomized parallel algorithms for backtrack search and branch-and-bound computation. Zbl 0789.68066 Karp, Richard M.; Zhang, Yanjun 22 1993 An algorithm for finding canonical sets of ground rewrite rules in polynomial time. Zbl 0779.68050 Gallier, Jean; Narendran, Paliath; Plaisted, David; Raatz, Stan; Snyder, Wayne 16 1993 Modal nonmonotonic logics: Ranges, characterization, computation. Zbl 0783.68121 Marek, V. Wiktor; Schwarz, Grigori F.; Truszczyński, Mirosław 13 1993 ...and 1456 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 34,268 Authors 120 Ibarra, Oscar H. 98 Kutrib, Martin 82 Jain, Sanjay 80 Raynal, Michel 79 Epstein, Leah 76 Saurabh, Saket 72 Rajsbaum, Sergio 70 Otto, Friedrich 69 Fomin, Fedor V. 63 Guerraoui, Rachid 58 Aceto, Luca 58 Vardi, Moshe Ya’akov 56 Cordero, Alicia 56 Stephan, Frank 56 Torregrosa Sanchez, Juan Ramón 55 Malcher, Andreas 54 Tarjan, Robert Endre 53 Sharir, Micha 53 Woeginger, Gerhard 51 Ingólfsdóttir, Anna 50 Golovach, Petr A. 50 Peleg, David 49 Schneider, Carsten 47 Halpern, Joseph Yehuda 46 Bodlaender, Hans L. 46 Inenaga, Shunsuke 46 Zehavi, Meirav 44 Wood, Derick 43 Argyros, Ioannis Konstantinos 43 Levin, Asaf 42 Book, Ronald Vernon 42 Case, John 42 Holzer, Markus 42 Meseguer Guaita, José 42 Okhotin, Alexander 42 Pan, Victor Yakovlevich 41 Eiter, Thomas 41 Evans, David John 41 Goldreich, Oded 41 Gottlob, Georg 40 Attiya, Hagit 40 Bergstra, Jan A. 40 Fernau, Henning 40 Iliopoulos, Costas S. 40 Pelc, Andrzej 40 Strusevich, Vitaly A. 39 Ibaraki, Toshihide 39 Lohrey, Markus 39 Lokshtanov, Daniel 39 Montanari, Angelo 39 Subramani, Krishnan 39 Taubenfeld, Gadi 38 Chen, Danny Ziyi 37 Amir, Amihood 37 Engelfriet, Joost 37 Lynch, Nancy Ann 37 Wang, Haitao 36 Chen, Jian-er 36 Thilikos, Dimitrios M. 35 Diaconescu, Răzvan 35 Herlihy, Maurice P. 35 Jansen, Klaus 34 Alon, Noga 34 Calude, Cristian S. 34 Chan, Timothy Moon-Yew 34 Chatterjee, Krishnendu 34 Fraigniaud, Pierre 34 Moses, Yoram 34 Reichel, Lothar 34 Smid, Michiel H. M. 34 Soleymani, Fazlollah 34 Spirakis, Paul G. 34 Takeda, Masayuki 33 Agarwal, Pankaj Kumar 33 Behl, Ramandeep 33 Eppstein, David Arthur 33 Ésik, Zoltán 33 Galil, Zvi 33 Inoue, Katsushi 33 Laporte, Gilbert 33 van Glabbeek, Robert Jan 32 Bannai, Hideo 32 Bille, Philip 32 Bozzelli, Laura 32 Crochemore, Maxime 32 Demaine, Erik D. 32 Maheshwari, Anil 32 McQuillan, Ian 32 Mehlhorn, Kurt 32 Narendran, Paliath 32 Navarro, Gonzalo 32 Papadimitriou, Christos Harilaos 32 Rozenberg, Grzegorz 32 Rytter, Wojciech 32 Salomaa, Kai T. 32 Yang, Boting 31 Allender, Eric W. 31 Bose, Prosenjit K. 31 Censor-Hillel, Keren 31 Greibach, Sheila A. ...and 34,168 more Authors all top 5 Cited in 977 Journals 3,334 Theoretical Computer Science 1,333 Information Processing Letters 1,056 Journal of Computer and System Sciences 968 Discrete Applied Mathematics 783 European Journal of Operational Research 752 Information and Computation 716 Algorithmica 580 Artificial Intelligence 419 Computers & Operations Research 360 Acta Informatica 349 Information Sciences 297 Distributed Computing 288 International Journal of Foundations of Computer Science 285 International Journal of Computer Mathematics 280 Journal of Computational and Applied Mathematics 280 Operations Research Letters 277 Mathematical Programming. Series A. Series B 274 Journal of Symbolic Computation 271 Applied Mathematics and Computation 257 Theory of Computing Systems 255 Computers & Mathematics with Applications 254 Discrete Mathematics 246 Journal of Automated Reasoning 240 Linear Algebra and its Applications 239 Annals of Operations Research 222 Mathematical Systems Theory 222 Computational Geometry 220 Computing 214 Annals of Mathematics and Artificial Intelligence 214 Journal of Combinatorial Optimization 196 SIAM Journal on Computing 195 Networks 176 Journal of Discrete Algorithms 172 Mathematics of Computation 170 Journal of Computational Physics 163 Numerische Mathematik 155 Discrete & Computational Geometry 150 BIT 138 Real-Time Systems 135 Logical Methods in Computer Science 132 Queueing Systems 126 Computational Complexity 125 Annals of Pure and Applied Logic 123 Journal of Scheduling 117 Mathematical Structures in Computer Science 116 Formal Aspects of Computing 116 Numerical Algorithms 112 Discrete Optimization 110 The Journal of Symbolic Logic 108 Pattern Recognition 102 Theory and Practice of Logic Programming 100 Journal of Complexity 96 Fuzzy Sets and Systems 96 Journal of Logical and Algebraic Methods in Programming 95 Journal of Global Optimization 93 BIT. Nordisk Tidskrift for Informationsbehandling 91 International Journal of Computational Geometry & Applications 89 International Journal of Approximate Reasoning 88 Calcolo 86 Formal Methods in System Design 82 Journal of Optimization Theory and Applications 82 Combinatorica 80 International Journal of Computer & Information Sciences 80 Journal of Combinatorial Theory. Series B 80 Mathematical and Computer Modelling 78 Computer Physics Communications 77 The Journal of Logic and Algebraic Programming 74 RAIRO. Informatique Théorique et Applications 73 Random Structures & Algorithms 72 SIAM Journal on Discrete Mathematics 71 Journal of Cryptology 70 Journal of Soviet Mathematics 69 Computational Optimization and Applications 67 Automatica 65 Applied Numerical Mathematics 65 Machine Learning 64 Mathematical Programming 64 Naval Research Logistics 64 Journal of Applied Non-Classical Logics 64 Optimization Letters 63 Journal of Mathematical Analysis and Applications 62 Studia Logica 62 Journal of Computer Science and Technology 61 RAIRO, Informatique Théorique 60 Computer Methods in Applied Mechanics and Engineering 60 Applied Mathematical Modelling 60 Journal of Applied Logic 58 Mathematics and Computers in Simulation 58 SIAM Journal on Scientific Computing 57 Cybernetics 57 INFORMS Journal on Computing 56 International Journal for Numerical Methods in Engineering 56 European Journal of Combinatorics 56 Cybernetics and Systems Analysis 56 International Transactions in Operational Research 55 Kybernetika 55 Journal of Functional Programming 53 International Journal of Production Research 53 Journal of Parallel and Distributed Computing 53 ACM Transactions on Computational Logic ...and 877 more Journals all top 5 Cited in 62 Fields 22,847 Computer science (68-XX) 6,582 Operations research, mathematical programming (90-XX) 4,263 Combinatorics (05-XX) 3,714 Numerical analysis (65-XX) 3,648 Mathematical logic and foundations (03-XX) 1,557 Information and communication theory, circuits (94-XX) 962 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 926 Probability theory and stochastic processes (60-XX) 531 Linear and multilinear algebra; matrix theory (15-XX) 531 Statistics (62-XX) 499 Number theory (11-XX) 439 Biology and other natural sciences (92-XX) 430 Convex and discrete geometry (52-XX) 421 Systems theory; control (93-XX) 368 Group theory and generalizations (20-XX) 310 Order, lattices, ordered algebraic structures (06-XX) 290 Quantum theory (81-XX) 281 Partial differential equations (35-XX) 244 Ordinary differential equations (34-XX) 241 Field theory and polynomials (12-XX) 236 Approximations and expansions (41-XX) 222 Fluid mechanics (76-XX) 205 Category theory; homological algebra (18-XX) 203 Mechanics of deformable solids (74-XX) 185 Commutative algebra (13-XX) 167 Calculus of variations and optimal control; optimization (49-XX) 165 General algebraic systems (08-XX) 150 Algebraic geometry (14-XX) 136 Statistical mechanics, structure of matter (82-XX) 132 Dynamical systems and ergodic theory (37-XX) 125 Integral equations (45-XX) 116 Operator theory (47-XX) 113 Special functions (33-XX) 96 Integral transforms, operational calculus (44-XX) 93 Real functions (26-XX) 92 Functions of a complex variable (30-XX) 91 History and biography (01-XX) 81 Geometry (51-XX) 78 Harmonic analysis on Euclidean spaces (42-XX) 71 Associative rings and algebras (16-XX) 70 General topology (54-XX) 55 General and overarching topics; collections (00-XX) 50 Manifolds and cell complexes (57-XX) 50 Mechanics of particles and systems (70-XX) 47 Difference and functional equations (39-XX) 45 Functional analysis (46-XX) 45 Optics, electromagnetic theory (78-XX) 43 Algebraic topology (55-XX) 39 Classical thermodynamics, heat transfer (80-XX) 37 Geophysics (86-XX) 27 Measure and integration (28-XX) 23 Nonassociative rings and algebras (17-XX) 22 Differential geometry (53-XX) 15 Global analysis, analysis on manifolds (58-XX) 12 Topological groups, Lie groups (22-XX) 10 Sequences, series, summability (40-XX) 10 Relativity and gravitational theory (83-XX) 7 Potential theory (31-XX) 7 Several complex variables and analytic spaces (32-XX) 7 Mathematics education (97-XX) 5 Abstract harmonic analysis (43-XX) 1 Astronomy and astrophysics (85-XX) Citations by Year