Topic · semigroups and automata theory
Most cited papers in semigroups and automata theory
What are the most cited papers in semigroups and automata theory?
The most cited paper in semigroups and automata theory is "Reducibility among Combinatorial Problems" (Richard M. Karp, 1972), with 11,108 citations. Next come "Communication and Concurrency" (6,871) and "The complexity of theorem-proving procedures" (6,257).
Showing 50 of 100 papers. Every paper with more than 641 citations is listed.
| # | Paper | ||
|---|---|---|---|
| 1 | Reducibility among Combinatorial Problems Richard M. Karp | 1972 | 11,108 |
| 2 | Communication and Concurrency Robin Milner | 1989 | 6,871 |
| 3 | The complexity of theorem-proving procedures Stephen A Cook | 1971 | 6,257 |
| 4 | On observing nondeterminism and concurrency Matthew Hennessy, Robin Milner · Lecture notes in computer science | 1980 | 4,501 |
| 5 | Efficient string matching Alfred V. Aho, Margaret J. Corasick · Communications of the ACM | Jun 1975 | 2,969 |
| 6 | On the Complexity of Finite Sequences Abraham Lempel, J. Ziv · IEEE Transactions on Information Theory | 1976 | 2,784 |
| 7 | A critical point for random graphs with a given degree sequence Michael S. O. Molloy, Bruce A. Reed · Random Structures and Algorithms | Mar 1995 | 2,427 |
| 8 | Isabelle/HOL: A Proof Assistant for Higher-Order Logic Tobias Nipkow, Markus Wenzel, Lawrence Charles Paulson · Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) | 2002 | 2,319 |
| 9 | A fast string searching algorithm Robert S. Boyer, J Strother Moore · Communications of the ACM | Oct 1977 | 2,312 |
| 10 | A theory of type polymorphism in programming Robin Milner · Journal of Computer and System Sciences | Dec 1978 | 2,221 |
| 11 | Learning regular sets from queries and counterexamples Dana Angluin · Information and Computation | Nov 1987 | 2,135 |
| 12 | Finite Automata and Their Decision Problems M. O. Rabin, D. Scott · IBM Journal of Research and Development | Apr 1959 | 1,905 |
| 13 | Concurrency and automata on infinite sequences David S. Park · Lecture notes in computer science | 22 Nov 2005 | 1,883 |
| 14 | The theory of hybrid automata Thomas A. Henzinger | 23 Dec 2002 | 1,861 |
| 15 | Queries and Concept Learning Dana Angluin · Machine Learning | Apr 1988 | 1,638 |
| 16 | On certain formal properties of grammars Noam Chomsky · Information and Control | Jun 1959 | 1,598 |
| 17 | Recursively enumerable sets and degrees Robert Irving Soare · Bulletin of the American Mathematical Society | 1978 | 1,573 |
| 18 | Learning Automata: An Introduction Kumpati S. Narendra, Mandayam A. L. Thathachar · CERN Document Server (European Organization for Nuclear Research) | May 1989 | 1,561 |
| 19 | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms Kellogg S. Booth, George S. Lueker · Journal of Computer and System Sciences | Dec 1976 | 1,507 |
| 20 | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs Bruno Courcelle · Information and Computation | Mar 1990 | 1,474 |
| 21 | Generating hard instances of lattice problems (extended abstract) Miklós Ajtai | 1996 | 1,396 |
| 22 | Relationships between nondeterministic and deterministic tape complexities Walter J. Savitch · Journal of Computer and System Sciences | Apr 1970 | 1,378 |
| 23 | Formal Languages and Their Relation to Automata John E. Hopcroft, Jeffrey David Ullman · CERN Document Server (European Organization for Nuclear Research) | 1969 | 1,342 |
| 24 | Transition network grammars for natural language analysis William A. Woods · Communications of the ACM | Oct 1970 | 1,333 |
| 25 | Simple Fast Algorithms for the Editing Distance between Trees and Related Problems Kaizhong Zhang, Dennis E. Shasha · SIAM Journal on Computing | Dec 1989 | 1,326 |
| 26 | Efficient randomized pattern-matching algorithms Richard M. Karp, Michael O. Rabin · IBM Journal of Research and Development | Mar 1987 | 1,301 |
| 27 | On a Decision Method in Restricted Second Order Arithmetic J. Richard Buchi | 1990 | 1,288 |
| 28 | Data Compression Using Adaptive Coding and Partial String Matching John J. Cleary, Ian H. Witten · IEEE Transactions on Communications | 1984 | 1,261 |
| 29 | Principles and methods of testing finite state machines-a survey Diane Youngmi Lee, Mihalis Yannakakis · Proceedings of the IEEE | 1996 | 1,227 |
| 30 | Alternation Ashok Kumar Chandra, Dexter C. Kozen, Larry J. Stockmeyer · Journal of the ACM | 1981 | 1,215 |
| 31 | Tree Automata Techniques and Applications Hubert Comon, Max Dauchet, Rémi Gilleron et al. | 1997 | 1,184 |
| 32 | Three Partition Refinement Algorithms Robert A. Paige, Robert Endre Tarjan · SIAM Journal on Computing | Dec 1987 | 1,172 |
| 33 | Testing equivalences for processes Rocco De Nicola, Matthew Hennessy · Theoretical Computer Science | 1984 | 1,155 |
| 34 | A linear space algorithm for computing maximal common subsequences D. S. Hirschberg · Communications of the ACM | Jun 1975 | 1,116 |
| 35 | Outline for a Logical Theory of Adaptive Systems John H. Holland · Journal of the ACM | Jul 1962 | 1,109 |
| 36 | The structure of the “THE”-multiprogramming system Edsger W. Dijkstra · Communications of the ACM | May 1968 | 1,094 |
| 37 | Fast Algorithms for Finding Nearest Common Ancestors Dov Harel, Robert Endre Tarjan · SIAM Journal on Computing | May 1984 | 1,081 |
| 38 | On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines Lenore Blum, Mike Shub, Steve Smale · Bulletin of the American Mathematical Society | 1989 | 1,070 |
| 39 | The Byzantine generals problem SRI International, Leslie Lamport, Robert E. Shostak et al. | 9 Oct 2019 | 1,058 |
| 40 | Virtual Knot Theory Louis Hirsch Kauffman · European Journal of Combinatorics | Oct 1999 | 1,035 |
| 41 | Random generation of combinatorial structures from a uniform distribution Mark Jerrum, Leslie Gabriel Valiant, Vijay V. Vazirani · Theoretical Computer Science | 1986 | 1,013 |
| 42 | Algorithmic Information Theory Gregory J. Chaitin · IBM Journal of Research and Development | Jul 1977 | 1,011 |
| 43 | “Sometimes” and “not never” revisited E. Allen Emerson, Joseph Yehuda Halpern · Journal of the ACM | 2 Jan 1986 | 1,011 |
| 44 | Coordination languages and their significance David Hillel Gelernter, Nicholas John Carriero · Communications of the ACM | Feb 1992 | 1,010 |
| 45 | Formal Languages and their Relation to Automata James B. Morris · Nuclear Science and Engineering | May 1970 | 1,005 |
| 46 | Matching, Euler tours and the Chinese postman Jack Edmonds, Ellis L. Johnson · Mathematical Programming | Dec 1973 | 996 |
| 47 | Automata on Infinite Objects Wolfgang H Thomas · Elsevier eBooks | 1990 | 965 |
| 48 | Recognition and parsing of context-free languages in time n3 Daniel H. Younger · Information and Control | Feb 1967 | 953 |
| 49 | Derivatives of Regular Expressions Janusz Brzozowski · Journal of the ACM | Oct 1964 | 938 |
| 50 | Finite-state transducers in language and speech processing Mehryar Mohri | Jun 1997 | 920 |
Citations are OpenAlex's own counts, from its 2026-09-23 snapshot, so the ranking can differ from Google Scholar or Web of Science. A paper is listed for a field when OpenAlex files it under one of the field's topics; retracted papers and papers whose citation count cannot be traced to citing works are left out, and a preprint and the article it became are shown once. Release dates are OpenAlex's: where a source gave only a month or a year, that is what is shown. How the lists are chosen.