Combinatorial Expressions and Lower Bounds

Authors Thomas Colcombet, Amaldev Manuel



PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.249.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Thomas Colcombet
Amaldev Manuel

Cite AsGet BibTex

Thomas Colcombet and Amaldev Manuel. Combinatorial Expressions and Lower Bounds. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.249

Abstract

A new paradigm, called combinatorial expressions, for computing functions expressing properties over infinite domains is introduced. The main result is a generic technique, for showing indefinability of certain functions by the expressions, which uses a result, namely Hales-Jewett theorem, from Ramsey theory. An application of the technique for proving inexpressibility results for logics on metafinite structures is given. Some extensions and normal forms are also presented.
Keywords
  • expressions
  • lower bound
  • indefinability

Metrics

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

References

  1. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1998. Google Scholar
  2. Erich Grädel and Yuri Gurevich. Metafinite model theory. Information and Computation, 140(1):26 - 81, 1998. Google Scholar
  3. R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory. A Wiley-Interscience publication. Wiley, 1990. Google Scholar
  4. T. Jech. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer Monographs in Mathematics. Springer, 2003. Google Scholar
  5. Pascal Koiran. A weak version of the blum, shub, and smale model. Journal of Computer and System Sciences, 54(1):177 - 189, 1997. Google Scholar
  6. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1994. Google Scholar
  7. Pascal Tesson. Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD thesis, School of Computer Science, McGill University, Montreal, 2003. Google Scholar
  8. Pascal Tesson. An application of the hales-jewett theorem to multiparty communication complexity. Extract from the PhD Thesis, 2004. Google Scholar
  9. L. G. Valiant. Completeness classes in algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 249-261, New York, NY, USA, 1979. ACM. 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