Pebble Games with Algebraic Rules

• Autorzy: Dawar, A. , Holm, B.
• Języki publikacji: EN

Abstrakty

EN

We define a general framework of partition games for formulating two-player pebble games over finite structures. The framework we introduce includes as special cases the pebble games for finite-variable logics with and without counting. It also includes a matrix-equivalence game, introduced here, which characterises equivalence in the finite-variable fragments of the matrix-rank logic of [Dawar et al. 2009]. We show that one particular such game in our framework, which we call the invertible-map game, yields a family of polynomial-time approximations of graph isomorphism that is strictly stronger than the well-known Weisfeiler-Leman method. We show that the equivalence defined by this game is a refinement of the equivalence defined by each of the games for finite-variable logics.

Słowa kluczowe

EN

pebble game; Weisfeiler-Leman method

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 150, nr 3/4
• Strony: 281--316
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Dawar, A.

• Computer Laboratory, University of Cambridge, United Kingdom,

autor

Holm, B.

• Twigkit ltd., United Kingdom,

Bibliografia

• [1] Gurevich Y. Logic and the Challenge of Computer Science. In: Börger E (ed.), Current Trends in Theoretical Computer Science, pp. 1-57. Computer Science Press, 1988.
• [2] Immerman N. Relational Queries computable in Polynomial Time. Information and Control, 1986; 68: 86-104. doi: 10.1016/s0019-9958(86)80029-8.
• [3] Vardi MY. The Complexity of Relational Query Languages. In: STOC '82: Proc. 14th ACM Symp. on Theory of Computing. ACM Press, 1982 pp. 137-146. doi: 10.1145/800070.802186.
• [4] Cai JY, Fürer M, Immerman N. An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica, 1992; 12 (4): 389-410. doi: 10.1007/bf01305232.
• [5] Dawar A, Grohe M, Holm B, Laubner B. Logics with Rank Operators. In: Proc. 24th IEEE Symp. on Logic in Computer Science. 2009 pp. 113-122. doi: 10.1109/lics.2009.24.
• [6] Grädel E, Pakusa W. Rank Logic is Dead, Long Live Rank Logic! In: 24th EACSL Annual Conférénce on Computer Science Logic, CSL 2015. 2015 pp. 390-404. doi: 10.4230/LIPIcs.CSL.2015.390.
• [7] Immerman N, Lander E. Describing graphs: A first-order approach to graph canonization. Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, 1990. pp. 59-81. doi: 10.1007/978-1-4612-4478-3_5.
• [8] Hella L. Logical hierarchies in PTIME. Information and Computation, 1996; 129: 1-19. doi: 10.1006/inco.1996.0070.
• [9] Chistov A, Ivanyos G, Karpinski M. Polynomial time algorithms for modules over finite dimensional algebras. In: Proc. 1997 International Symposium on symbolic and algebraic computation. ACM. 1997, pp. 68-74. doi: 10.1145/258726.258751.
• [10] Ebbinghaus HD, Flum J. Finite Model Theory. Springer-Verlag, 1999. doi: 10.1007/3-540-28788-4.
• [11] Libkin L. Elements of finite model theory. Springer-Verlag, 2004. doi: 10.1007/978-3-662-07003-l.
• [12] Holm B. Descriptive complexity of linear algebra. Ph.D. thesis, Univ. of Cambridge, 2010.
• [13] Otto M. Bounded Variable Logics and Counting - A Study in Finite Models, volume 9 of Lecture Notes in Logic. Springer-Verlag, 1997. URL http://projecteuclid.org/euclid.lnl/1235416490.
• [14] Laubner B. The Structure of Graphs and New Logics for the Characterization of Polynomial Time Ph.D. thesis, Humboldt-Universität zu Berlin, 2011.
• [15] Fraïssé R. Sur quelques Classifications des Systèmes de Relations. Publications Scientifiques de l’Université d’Algerie, Séries A, 1954; 1: 35-182.
• [16] Ehrenfeucht A. An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae, 1961; 49 (2): 129-141. URL http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv49i2p129bwm.
• [17] Barwise J. On Moschovakis Closure Ordinals. Journal of Symbolic Logic, 1977; 42: 292-296. doi: 10.2307/2272133.
• [18] Poizat B. Deux Ou Trois Choses Que je Sais de Ln. Journal of Symbolic Logic, 1982; 47 (3): 1: 641-658. doi: 10.2307/2273594.
• [19] Dawar A, Holm B. Pebble Games for Logics with Counting and Rank. In: Cégielski P (ed.), Studies in Weak Arithmetics, pp. 99-120. CSLI Publications, 2010.
• [20] Derksen H. The Graph Isomorphism Problem and approximate categories. J. Symb. Comput., 2013; 59: 81-112. doi: 10.1016/j.jsc.2013.06.002.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).

Identyfikatory

DOI

10.3233/FI-2017-1471