Document Open Access Logo

Choiceless Logarithmic Space

Authors Erich Grädel, Svenja Schalthöfer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.31.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Erich Grädel
  • RWTH Aachen University, Germany
Svenja Schalthöfer
  • RWTH Aachen University, Germany

Cite As Get BibTex

Erich Grädel and Svenja Schalthöfer. Choiceless Logarithmic Space. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.31

Abstract

One of the most important open problems in finite model theory is the question whether there is a logic characterising efficient computation. While this question usually concerns Ptime, it can also be applied to other complexity classes, and in particular to Logspace which can be seen as a formalisation of efficient computation for big data. One of the strongest candidates for a logic capturing Ptime is Choiceless Polynomial Time (CPT). It is based on the idea of choiceless algorithms, a general model of symmetric computation over abstract structures (rather than their encodings by finite strings). However, there is currently neither a comparably strong candidate for a logic for Logspace, nor a logic transferring the idea of choiceless computation to Logspace.
We propose here a notion of Choiceless Logarithmic Space which overcomes some of the obstacles posed by Logspace as a less robust complexity class. The resulting logic is contained in both Logspace and CPT, and is strictly more expressive than all logics for Logspace that have been known so far. Further, we address the question whether this logic can define all Logspace-queries, and prove that this is not the case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
Keywords
  • Finite Model Theory
  • Logics for Logspace
  • Choiceless Computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Abu Zaid, E. Grädel, M. Grohe, and W. Pakusa. Choiceless Polynomial Time on structures with small Abelian colour classes. In MFCS 2014, volume 8634 of Lecture Notes in Computer Science, pages 50-62. Springer, 2014. Google Scholar
  2. A. Atserias, A. Bulatov, and A. Dawar. Affine Systems of Equations and Counting Infinitary Logic. Theoretical Computer Science, 410:1666-1683, 2009. Google Scholar
  3. A. Blass, Y. Gurevich, and S. Shelah. Choiceless polynomial time. Annals of Pure and Applied Logic, 100(1-3), 1999. Google Scholar
  4. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992. Google Scholar
  5. A. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1), 1982. Google Scholar
  6. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  7. A. Dawar, M. Grohe, B. Holm, and B. Laubner. Logics with Rank Operators. In Proc. 24th IEEE Symp. on Logic in Computer Science (LICS 09), pages 113-122, 2009. Google Scholar
  8. A. Dawar, D. Richerby, and B. Rossman. Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs. Annals of Pure and Applied Logic, 152:31-50, 2009. Google Scholar
  9. E. Grädel and M. Grohe. Is Polynomial Time Choiceless? In Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, pages 193-209, 2015. Google Scholar
  10. E. Grädel, Ł. Kaiser, W. Pakusa, and S. Schalthöfer. Characterising Choiceless Polynomial Time with First-Order Interpretations. In LICS, 2015. Google Scholar
  11. E. Grädel and M. Otto. Inductive Definability with Counting on Finite Structures. In Computer Science Logic, CSL 92, volume 702 of Lecture Notes in Computer Science, pages 231-247. Springer, 1992. Google Scholar
  12. E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! Journal of Symbolic Logic, To appear, 2019. http://arxiv.org/abs/1503.05423. Google Scholar
  13. E. Grädel and M. Spielmann. Logspace Reducibility via Abstract State Machines. In J. Wing, J. Woodcock, and J. Davies, editors, World Congress on Formal Methods (FM `99), volume 1709 of LNCS. Springer, 1999. URL: http://www.logic.rwth-aachen.de/pub/graedel/GrSp-fm99.ps.
  14. E. Grädel et al. Finite Model Theory and Its Applications. Springer-Verlag, 2007. Google Scholar
  15. M. Grohe. The quest for a logic capturing PTIME. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS'08), pages 267-271, 2008. Google Scholar
  16. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017. Google Scholar
  17. M. Grohe, B. Grußien, A. Hernich, and B. Laubner. L-Recursion and a new Logic for Logarithmic Space. In LIPIcs-Leibniz International Proceedings in Informatics, volume 12. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2011. Google Scholar
  18. B. Grußien. Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion. PhD thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2017. URL: https://doi.org/10.18452/18548.
  19. Y. Gurevich. Logic and the challenge of computer science. In E. Börger, editor, Current Trends in Theoretical Computer Science, pages 1-57. Computer Science Press, 1988. Google Scholar
  20. N. Immerman. Expressibility as a complexity measure: results and directions. In Structure in Complexity Theory, pages 194-202, 1987. Google Scholar
  21. N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16(4):760-778, 1987. Google Scholar
  22. W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen University, 2016. Google Scholar
  23. W. Pakusa, S. Schalthöfer, and E. Selman. Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), pages 19:1-19:17, 2016. Google Scholar
  24. O. Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):17, 2008. Google Scholar
  25. B. Rossman. Choiceless Computation and Symmetry. In A. Blass, N. Dershowitz, and W. Reisig, editors, Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, volume 6300 of LNCS, pages 565-580. Springer, 2010. Google Scholar
  26. S. Schalthöfer. Choiceless Computation and Logic. PhD thesis, RWTH Aachen University, 2018. Google Scholar
  27. M. Spielmann. Abstract state machines: Verification problems and complexity. PhD thesis, RWTH Aachen University, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact