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