SpringerLink
Log in

The Complexity of Counting Quantifiers on Equality Languages

  • Conference paper
  • First Online:
Pursuit of the Universal (CiE 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9709))

Included in the following conference series:

  • 692 Accesses

Abstract

An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.

B. Martin and A. Pongrácz were supported by EPSRC grant EP/L005654/1.

A. Pongrácz—Supported also by the Hungarian Scientific Research Fund (OTKA) grant no. K109185.

M. Wrona—Partially supported by NCN grant number 2014/14/A/ST6/00138.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Another typical solution is to give definition to complexity of relationally-infinite \(\varGamma \) along the lines of “easy”, if it is easy for all finite subsets, and “hard”, if it is hard for some finite subset.

References

  1. Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC\(^1\). J. Comput. Syst. Sci. 41(3), 274–306 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782–1802 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bodirsky, M., Chen, H.: Quantified equality constraints. In: Proceedings of LICS 2007, pp. 203–212 (2007)

    Google Scholar 

  4. Bodirsky, M., Chen, H.: Quantified equality constraints. SIAM J. Comput. 39(8), 3682–3699 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bodirsky, M., Chen, H.: Personal communication (2012)

    Google Scholar 

  6. Bodirsky, M., Chen, H., Pinsker, M.: The reducts of equality up to primitive positive interdefinability. J. Symb. Log. 75(4), 1249–1292 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bodirsky, M., Kára, J.: The complexity of equality constraint languages. Theor. Comput. Syst. 43(2), 136–158 (2008). A preliminary version appeared in the proceedings of CSR 2006

    Article  MathSciNet  MATH  Google Scholar 

  8. Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66–120 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Clark, R., Grossman, M.: Number sense and quantifier interpretation. Topoi 26(1), 51–62 (2007)

    Article  Google Scholar 

  11. Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)

    MATH  Google Scholar 

  12. Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP, constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57–104 (1999). A preliminary version appeared in the proceedings of STOC 1993

    Article  MathSciNet  MATH  Google Scholar 

  13. Hell, P., Nešetřil, J.: On the complexity of H-coloring. J. Comb. Theor. Ser. B 48(1), 92–110 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kolaitis, P.G., Vardi, M.Y.: A logical Approach to Constraint Satisfaction. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2005)

    Google Scholar 

  15. Martin, B., Madelaine, F.R., Stacho, J.: Constraint satisfaction with counting quantifiers. SIAM J. Discrete Math. 29(2), 1065–1113 (2015). Extended abstracts appeared at CSR 2012 and CSR 2014

    Article  MathSciNet  MATH  Google Scholar 

  16. Otto, M.: Bounded Variable Logics and Counting - A Study in Finite Models, vol. 9. Springer, Heidelberg (1997). IX+183pp

    Book  MATH  Google Scholar 

  17. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC 1978, pp. 216–226 (1978)

    Google Scholar 

  18. Schmidt, J., Wrona, M.: The complexity of abduction for equality constraint languages. In: Computer Science Logic (CSL 2013), pp. 615–633 (2013)

    Google Scholar 

  19. Szymanik, J.: Quantifiers and Cognition: Logical and Computational Perspectives. Studies in Linguistics and Philosophy. Springer, Cham (2016)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Science and Technology, Middlesex University, The Burroughs, Hendon, London, NW4 4BT, UK

    Barnaby Martin

  2. Debreceni Egyetem TTK, Algebra és Számelmélet Tanszék, Debrecen, PF. 18, 4010, Hungary

    András Pongrácz

  3. Faculty of Mathematics and Computer Science, Theoretical Computer Science Department, Jagiellonian University, Kraków, Poland

    Michał Wrona

Authors
  1. Barnaby Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. András Pongrácz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michał Wrona
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Barnaby Martin .

Editor information

Editors and Affiliations

  1. Swansea University, Swansea, United Kingdom

    Arnold Beckmann

  2. Université Paris-Diderot - Paris 7, Paris, France

    Laurent Bienvenu

  3. University of South Florida, Tampa, Florida, USA

    Nataša Jonoska

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Martin, B., Pongrácz, A., Wrona, M. (2016). The Complexity of Counting Quantifiers on Equality Languages. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds) Pursuit of the Universal. CiE 2016. Lecture Notes in Computer Science(), vol 9709. Springer, Cham. https://doi.org/10.1007/978-3-319-40189-8_34

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-40189-8_34

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-40188-1

  • Online ISBN: 978-3-319-40189-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation