Expressiveness and Complexity of Full First-Order Constraints in the Algebra of Trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

Expressiveness and Complexity of Full First-Order Constraints in the Algebra of Trees

  • Conference paper
  • First Online:
Artificial Intelligence, Automated Reasoning, and Symbolic Computation (AISC 2002, Calculemus 2002)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2385))

  • 351 Accesses

Abstract

What can be expressed by constraints, in the algebra of trees, if quantifiers and all the logical connectors are allowed? What is the complexity of algorithms for solving such general first-order constraints? This talk answers these two questions.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique Fondamentale de Marseille, Université Aix-Marseille II, France

    Alain Colmerauer

Authors
  1. Alain Colmerauer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Karlsruhe (TH), Am Fasanengarten 5, Postfach 6980, D-76128, Karlsruhe, Germany

    Jacques Calmet

  2. CMI, Université de Provence, 39 rue F. Juliot-Curie, 13453, Marseille Cedex 13, France

    Belaid Benhamou

  3. Research Institute for Symbolic Computation (RISC-Linz), Johannes Kepler University, A-4040, Linz, Austria

    Olga Caprotti

  4. ESIL, Université de la Méditerannée, 163 Avenue de Luminy, Marseille Cedex 09, France

    Laurent Henocque

  5. School of Computer Science, University of Birmingham, Birmingham, B15 2TT, UK

    Volker Sorge

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Colmerauer, A. (2002). Expressiveness and Complexity of Full First-Order Constraints in the Algebra of Trees. In: Calmet, J., Benhamou, B., Caprotti, O., Henocque, L., Sorge, V. (eds) Artificial Intelligence, Automated Reasoning, and Symbolic Computation. AISC Calculemus 2002 2002. Lecture Notes in Computer Science(), vol 2385. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45470-5_2

Download citation

  • DOI: https://doi.org/10.1007/3-540-45470-5_2

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43865-6

  • Online ISBN: 978-3-540-45470-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation