More Web Proxy on the site http://driver.im/

research-article

The nature and power of fixed-point logic with counting

Author:

Anuj DawarAuthors Info & Claims

ACM SIGLOG News, Volume 2, Issue 1

Pages 8 - 21

https://doi.org/10.1145/2728816.2728820

Published: 28 January 2015 Publication History

Abstract

In 1982, Neil Immerman proposed an extension of fixed-point logic by means of counting quantifiers (which we denote FPC) as a logic that might express all polynomial-time properties of unordered graphs. It was eventually proved (by Cai, Fürer and Immerman) that there are polynomial-time graph properties that are not expressible in FPC. Nonetheless, FPC is a powerful and natural fragment of the complexity class PTime. In this article, I justify this claim by reviewing three recent positive results that demonstrate the expressive power and robustness of this logic.

References

[1]

M. Anderson and A. Dawar. 2014. On Symmetric Circuits and Fixed-Point Logics. In 31st Intl. Symp. Theoretical Aspects of Computer Science (STACS 2014). 41--52.

[2]

M. Anderson, A. Dawar, and B. Holm. 2013. Maximum Matching and Linear Programming in Fixed-Point Logic with Counting. In 28th Annual ACM/IEEE Symp. Logic in Computer Science. 173--182.

Digital Library

[3]

A. Atserias, A. Bulatov, and A. Dawar. 2009. Affine Systems of Equations and Counting Infinitary Logic. Theoretical Computer Science 410, 18 (2009), 1666--1683.

Digital Library

[4]

A. Blass, Y. Gurevich, and S. Shelah. 1999. Choiceless Polynomial Time. Annals of Pure and Applied Logic 100 (1999), 141--187.

[5]

J-Y. Cai, M. Fürer, and N. Immerman. 1992. An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica 12, 4 (1992), 389--410.

[6]

E. Dahlhaus. 1984. Reduction to NP--Complete Problems by Interpretation. In LNCS 171. Springer-Verlag, 357--365.

Digital Library

[7]

A. Dawar. 1998. A Restricted Second Order Logic for Finite Structures. Information and Computation 143 (1998), 154--174.

Digital Library

[8]

A. Dawar. 2007. Finite Model Theory on Tame Classes of Structures. In MFCS (Lecture Notes in Computer Science), Vol. 4708. Springer, 2--12.

Digital Library

[9]

A. Dawar and E. Grädel. 2010. Properties of Almost All Graphs and Generalized Quantifiers. Fundam. Inform. 98, 4 (2010), 351--372.

Digital Library

[10]

A. Dawar, M. Grohe, B. Holm, and B. Laubner. 2009. Logics with Rank Operators. In Proc. 24th IEEE Symp. on Logic in Computer Science. 113--122.

Digital Library

[11]

L. Denenberg, Y. Gurevich, and S. Shelah. 1986. Definability by Constant-depth Polynomial-size Circuits. Information and Control 70 (1986), 216--240.

Digital Library

[12]

H-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (2nd ed.). Springer.

[13]

J. Edmonds. 1965. Maximum Matching and a Polyhedron with 0, 1 Vertices. J. Research National Bureau of Standards 69 B (1965), 125--130.

[14]

F. Gire and H. Hoang. 1998. An Extension of Fixpoint Logic with a Symmetry-Based Choice Construct. Information and Computation 144 (1998), 40--65.

Digital Library

[15]

M. Grohe. 1998. Fixed-Point Logics on Planar Graphs. In Proc. 13th IEEE Annual Symp. Logic in Computer Science. 6--15.

Digital Library

[16]

M. Grohe. 2012. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM 59, 5 (2012), 27:1--27:64.

Digital Library

[17]

M. Grohe. 2014. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. (2014). http://www.automata.rwth-aachen.de/~grohe/cap/index.en Draft of Monograph.

[18]

M. Grohe, K. Kersting, M. Mladenov, and E. Selman. 2014. Dimension Reduction via Colour Refinement. In Algorithms - ESA 2014 - 22nd Annual European Symposium. 505--516.

[19]

M. Grohe and J. Mariño. 1999. Definability and Descriptive Complexity on Databases of Bounded Tree-Width. In Proc. 7th International Conference on Database Theory (LNCS), Vol. 1540. Springer, 70--82.

Digital Library

[20]

L. Hella. 1992. Logical hierarchies in PTIME. In Proc. 7th IEEE Symp. on Logic in Computer Science. 360--368.

[21]

B. Holm. 2010. Descriptive Complexity of Linear Algebra. Ph.D. Dissertation. University of Cambridge.

[22]

N. Immerman. 1982. Relational Queries Computable in Polynomial Time (Extended Abstract). In Proc. 14th Annual ACM Symp. Theory of Computing. 147--152.

Digital Library

[23]

N. Immerman. 1986. Relational Queries computable in Polynomial Time. Information and Control 68 (1986), 86--104.

Digital Library

[24]

N. Immerman. 1999. Descriptive Complexity. Springer.

[25]

N. Immerman and E. S. Lander. 1990. Describing Graphs: A First-order Approach to Graph Canonization. In Complexity Theory Retrospective, A. Selman (Ed.). Springer-Verlag.

[26]

L. G. Khachiyan. 1980. Polynomial Algorithms in Linear Programming. U. S. S. R. Comput. Math. and Math. Phys. 20, 1 (1980), 53--72.

[27]

K. Kuratowski. 1930. Sur le Probléme des Courbes Gauches en Topologie. Fundamenta Mathematicae 15 (1930), 271283.

[28]

L. Lovász and P. Gács. 1977. Some Remarks on Generalized Spectra. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 23 (1977), 27--144.

[29]

E. M. Luks. 1982. Isomorphism of Graphs of Bounded Valence Can be Tested in Polynomial Time. J. Comput. System Sci. 25 (1982), 42--65.

[30]

M. Otto. 1996. The Logic of Explicitly Presentation-Invariant Circuits. In Computer Science Logic, 10th International Workshop, CSL '96, Annual Conference of the EACSL. 369--384.

Digital Library

[31]

M. Otto. 1997. Bounded Variable Logics and Counting --- A Study in Finite Models. Lecture Notes in Logic, Vol. 9. Springer-Verlag.

[32]

A. A. Razborov. 1985. Lower Bounds on the Monotone Complexity of some Boolean Functions. Dokl. Akad. Nauk. SSSR 281 (1985), 798--801.

[33]

N. Robertson and P. D. Seymour. 1995. Graph Minors. XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B 63 (1995), 65--110.

Digital Library

[34]

N. Robertson and P. D. Seymour. 2003. Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89 (2003), 43--76.

Digital Library

[35]

N. Robertson and P. D. Seymour. 2004. Graph Minors. XX. Wagner's conjecture. J. Comb. Theory, Ser. B 92 (2004), 325--357.

Digital Library

[36]

T. Rothvoß. 2014. The Matching Polytope has Exponential Extension Complexity. In Symp. Theory of Computing, STOC 2014. 263--272.

Digital Library

[37]

M. Y. Vardi. 1982. The Complexity of Relational Query Languages. In Proc. of the 14th ACM Symp. on the Theory of Computing. 137--146.

Digital Library

[38]

K. Wagner. 1937. Uber eine Eigenschaft der Ebenen Komplexe. Math. Ann. 114 (1937), 570--590.

Cited By

Dawar APago B(2024)A Logic for P: Are we Nearly There Yet?ACM SIGLOG News10.1145/3665453.366545911:2(35-60)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1145/3665453.3665459
Bodirsky MRydval J(2022)On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/356605170:1(1-58)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3566051
Dawar AFerreira Santos F(2022)Separating LREC from LFPProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533368(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533368
Show More Cited By

Recommendations

Sahlqvist theorem for modal fixed point logic

We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula @f there exists an LFP-formula @g(@f), with no free first-order variable or predicate symbol, such that a ...
An Infinitary System for the Least Fixed-Point Logic restricted to Finite Models

The notion of the least fixed-point of an operator is widely applied in computer science as, for instance, in the context of query languages for relational databases. Some extensions of first-order classical logic (FOL) with fixed-point operators, as ...
The expressive power of two-variable least fixed-point logics
MFCS'05: Proceedings of the 30th international conference on Mathematical Foundations of Computer Science

The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are:

The two-variable fragment of monadic least fixed-point logic with parameters is as expressive as full monadic least fixed-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGLOG News

ACM SIGLOG News Volume 2, Issue 1

January 2015

42 pages

EISSN:2372-3491

DOI:10.1145/2728816

Editor:
Andrzej Murawski
University of Warwick

Issue’s Table of Contents

Copyright © 2015 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 January 2015

Published in SIGLOG Volume 2, Issue 1

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
204
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dawar APago B(2024)A Logic for P: Are we Nearly There Yet?ACM SIGLOG News10.1145/3665453.366545911:2(35-60)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1145/3665453.3665459
Bodirsky MRydval J(2022)On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/356605170:1(1-58)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3566051
Dawar AFerreira Santos F(2022)Separating LREC from LFPProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533368(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533368
Arvind VFuhlbrück FKöbler JVerbitsky O(2022)On the Weisfeiler-Leman dimension of fractional packingInformation and Computation10.1016/j.ic.2021.104803288:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.ic.2021.104803
Dawar AWilsenach G(2021)Symmetric Circuits for Rank LogicACM Transactions on Computational Logic10.1145/347622723:1(1-35)Online publication date: 22-Nov-2021
https://dl.acm.org/doi/10.1145/3476227
Atserias ADawar AOchremiak J(2021)On the Power of Symmetric Linear ProgramsJournal of the ACM10.1145/345629768:4(1-35)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3456297
Tucker-Foltz JGorla D(2021)Inapproximability of unique games in fixed-point logic with countingProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470706(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470706
Bodirsky MPakusa WRydval JHermanns HZhang LKobayashi NMiller D(2020)Temporal Constraint Satisfaction Problems in Fixed-Point LogicProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3373718.3394750(237-251)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3373718.3394750
Arvind VFuhlbrück FKöbler JVerbitsky O(2020)On Weisfeiler-Leman invariance: Subgraph counts and related graph propertiesJournal of Computer and System Sciences10.1016/j.jcss.2020.04.003113(42-59)Online publication date: Dec-2020
https://doi.org/10.1016/j.jcss.2020.04.003
Arvind VFuhlbrück FKöbler JVerbitsky O(2020)On the Weisfeiler-Leman Dimension of Fractional PackingLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_25(357-368)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_25
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents