{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:30:02Z","timestamp":1775097002358,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1992,12,1]],"date-time":"1992-12-01T00:00:00Z","timestamp":723168000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1992,12]]},"DOI":"10.1007\/bf01305232","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T10:20:39Z","timestamp":1111746039000},"page":"389-410","source":"Crossref","is-referenced-by-count":290,"title":["An optimal lower bound on the number of variables for graph identification"],"prefix":"10.1007","volume":"12","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Martin","family":"F\ufffdrer","sequence":"additional","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"A. V. Aho, J. E. Hopcroft andJ. D. Ullman:The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai: Recursive Construction for 3-Regular Expanders,28th IEEE Symp. on Foundations of Computer Science (1987), 295?304.","DOI":"10.1109\/SFCS.1987.50"},{"key":"CR3","unstructured":"L. Babai: Monte Carlo Algorithms in Graph Isomorphism Testing, Tech. Rep. DMS 79-10, Universit\u00e9 de Montr\u00e9al, 1979."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/0209018","volume":"9","author":"L. Babai","year":"1980","unstructured":"L. Babai: On the Complexity of Canonical Labeling of Strongly Regular Graphs,SIAM J. Computing 9 (1980), 212?216.","journal-title":"SIAM J. Computing"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"L. Babai: Moderately Exponential Bound for Graph Isomorphism,Proc. Conf. on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Springer, 1981, 34?50.","DOI":"10.1007\/3-540-10854-8_4"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"553","DOI":"10.2307\/2006997","volume":"113","author":"L. Babai","year":"1981","unstructured":"L. Babai: On the Order of Uniprimitive Permutation Groups,Annals of Math. 113 (1981), 553?568.","journal-title":"Annals of Math."},{"key":"CR7","unstructured":"L. Babai:Permutation Groups, Coherent Configurations, and Graph Isomorphism, D. Sc. Thesis, Hungarian Acad. Sci., 1984 (in Hungarian)."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L. Babai","year":"1980","unstructured":"L. Babai, P. Erd?s, andS. M. Selkow: Random Graph Isomorphism,SIAM J. on Comput. 9 (1980), 628?635.","journal-title":"SIAM J. on Comput."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"L. Babai, W. M. Kantor, andE. M. Luks: Computational Complexity and the Classification of Finite Simple Groups,24th IEEE Symp. on Foundations of Computer Science (1983), 162?171.","DOI":"10.1109\/SFCS.1983.10"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"L. Babai andL. Ku?era: Canonical Labelling of Graphs in Linear Average Time,20th IEEE Symp. on Foundations of Computer Science (1979), 39?46.","DOI":"10.1109\/SFCS.1979.8"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"L. Babai andE. M. Luks: Canonical Labeling of Graphs,15th ACM Symposium on Theory of Computing (1983), 171?183.","DOI":"10.1145\/800061.808746"},{"issue":"No. 3","key":"CR12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. M. Barrington","year":"1990","unstructured":"D. M. Barrington, N. Immerman, andH. Straubing: On Uniformity Within NC1,J. Comput. System Sci. 41, No. 3 (1990), 274?306.","journal-title":"J. Comput. System Sci."},{"key":"CR13","unstructured":"L. Babai andR. Mathon: Talk at the South-East Conference on Combinatorics and Graph Theory, 1980."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0095-8956(80)90063-5","volume":"28","author":"P. J. Cameron","year":"1980","unstructured":"P. J. Cameron: 6-Transitive Graphs,J. Combinat. Theory B 28, (1980), 168?179.","journal-title":"J. Combinat. Theory B"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra andD. Harel: Structure and Complexity of Relational Queries,J. Comput. System Sci. 25 (1982), 99?128.","journal-title":"J. Comput. System Sci."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht: An Application of Games to the Completeness Problem for Formalized Theories,Fund. Math. 49 (1961), 129?141.","journal-title":"Fund. Math."},{"key":"CR17","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9: Sur quelques classifications des syst\u00e8ms de relations,Publ. Sci. Univ. Alger 1 (1954), 35?182.","journal-title":"Publ. Sci. Univ. Alger"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer, W. Schnyder, andE. Specker: Normal Forms for Trivalent Graphs and Graphs of Bounded Valence,15th ACM Symposium on Theory of Computing (1983), 161?170.","DOI":"10.1145\/800061.808745"},{"key":"CR19","first-page":"76","volume-title":"Algorithmic Research in Combinatorics","author":"Ya. Yu. Gol'fand","year":"1978","unstructured":"Ya. Yu. Gol'fand andM. H. Klin: Onk-Regular Graphs, in:Algorithmic Research in Combinatorics, Nauka Publ., Moscow, 1978, 76?85."},{"key":"CR20","unstructured":"Yu. Gurevich: Logic and the Challenge of Computer Science, in:Current Trends in Theoretical Computer Science, ed. Egon B\u00f6rger, Computer Science Press, 1988, 1?57."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00147398","volume":"4","author":"D. G. Higman","year":"1975","unstructured":"D. G. Higman: Coherent Configurations I.: Ordinary Representation Theory,Geometriae Dedicata 4 (1975), 1?32.","journal-title":"Geometriae Dedicata"},{"issue":"No. 3","key":"CR22","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"N. Immerman: Number of Quantifiers is Better than Number of Tape Cells,J. Comput. System Sci. 22, No. 3 (1981), 384?406.","journal-title":"J. Comput. System Sci."},{"issue":"No. 1","key":"CR23","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman: Upper and Lower Bounds for First Order Expressibility,J. Comput. System Sci. 25, No. 1 (1982), 76?98.","journal-title":"J. Comput. System Sci."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman: Relational Queries Computable in Polynomial Time,Information and Control 68 (1986), 86?104.","journal-title":"Information and Control"},{"issue":"No. 4","key":"CR25","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman: Languages That Capture Complexity Classes,SIAM J. Computing 16, No. 4 (1987), 760?778.","journal-title":"SIAM J. Computing"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0890-5401(89)90055-2","volume":"83","author":"N. Immerman","year":"1989","unstructured":"N. Immerman andD. Kozen: Definability with Bounded Number of Bound Variables,Information and Computation 83 (1989), 121?139.","journal-title":"Information and Computation"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"N. Immerman andE. S. Lander: Describing Graphs: A First-Order Approach to Graph Canonization, in:Complexity Theory Retrospective, Alan Selman, ed., Springer-Verlag, 1990, 59?81.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"N. Immerman, S. Patnaik, andD. Stemple: The Expressiveness of a Family of Finite Set Languages,Tenth ACM Symposium on Principles of Database Systems (1991), 37?52.","DOI":"10.1145\/113413.113417"},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"L. Ku?era: Canonical Labeling of Regular Graphs in Linear Average Time,28th IEEE Symp. on Foundations of Computer Science (1987), 271?279.","DOI":"10.1109\/SFCS.1987.11"},{"key":"CR30","unstructured":"M. H. Klin, M. E. Muzichuk, andI. A. Farad?ev: Cellular Rings and Groups of Automorphism of Graphs, Introductory Article to a Book to be Published by D. Reidel Publ. Co."},{"key":"CR31","volume-title":"Angewandte Algebra","author":"M. Ch. Klin","year":"1988","unstructured":"M. Ch. Klin, R. P\u00f6schel, andK. Rosenbaum: Angewandte Algebra, Vieweg & Sohn Publ., Braunschweig 1988."},{"key":"CR32","unstructured":"R. Lipton: The Beacon Set Approach to Graph Isomorphism, Yale Dept. Comp. Sci. preprint No. 135, 1978."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E. M. Luks","year":"1982","unstructured":"E. M. Luks: Isomorphism of Graphs of Bounded Valence Can be Tested in Polynomial Time,J. Comput. System Sci. 25 (1982), 42?65.","journal-title":"J. Comput. System Sci."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R. Mathon","year":"1979","unstructured":"R. Mathon: A Note On the Graph Isomorphism Counting Problem,Inform. Proc. Let. 8 (1979), 131?132.","journal-title":"Inform. Proc. Let."},{"key":"CR35","series-title":"Tech. Rep. TR-CS-87-03","volume-title":"Nauty User's Guide (Version 1.2)","author":"B. D. McKay","year":"1987","unstructured":"B. D. McKay: Nauty User's Guide (Version 1.2), Tech. Rep. TR-CS-87-03, Dept. Computer Science, Austral. National Univ., Melbourne, 1987."},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"G. L. Miller: On then logn Isomorphism Technique,10th ACM Symposium on Theory of Computing (1978), 51?58.","DOI":"10.1145\/800133.804331"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1002\/jgt.3190010410","volume":"1","author":"R. C. Read","year":"1977","unstructured":"R. C. Read andD. G. Corneil: The Graph Isomorphism Disease,J. Graph Theory 1 (1977), 339?363.","journal-title":"J. Graph Theory"},{"key":"CR38","doi-asserted-by":"crossref","unstructured":"M. Vardi: Complexity of Relational Query Languages,14th ACM Symposium on Theory of Computing (1982), 137?146.","DOI":"10.1145\/800070.802186"},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"B. Weisfeiler, ed.:On Construction and Identification of Graphs, Lecture Notes in Mathematics 558, Springer, 1976.","DOI":"10.1007\/BFb0089374"},{"key":"CR40","first-page":"12","volume":"9","author":"B. Weisfeiler","year":"1968","unstructured":"B. Weisfeiler andA. A. Lehman: A Reduction of a Graph to a Canonical Form and an Algebra Arising during this Reduction, (in Russian),Nauchno-Technicheskaya Informatsia, Seriya 2,9 (1968), 12?16.","journal-title":"Nauchno-Technicheskaya Informatsia, Seriya 2"},{"key":"CR41","unstructured":"V. N. Zemlyachenko, N. Kornienko, andR. I. Tyshkevich:Graph Isomorphism Problem, (in Russian), The Theory fo Computation I, Notes Sci. Sem. LOMI 118, 1982."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01305232.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01305232\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01305232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T21:22:50Z","timestamp":1735420970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01305232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["BF01305232"],"URL":"https:\/\/doi.org\/10.1007\/bf01305232","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}