Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
281--316
Opis fizyczny
Bibliogr. 20 poz., rys.
Twórcy
autor
- Computer Laboratory, University of Cambridge, United Kingdom, anuj.dawar@cl.cam.ac.uk
autor
- Twigkit ltd., United Kingdom, bjarki@twigkit.com
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-c699a9f0-a0aa-4568-9335-dcbcc31a61f4