NDLI: Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

Please wait, while we are loading the content...

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

Content Provider	Springer Nature Link
Author	Colmerauer, Alain Dao, Thi Bich Hanh
Copyright Year	2003
Abstract	We are interested in the expressiveness of constraints represented by general first order formulae, with equality as unique relation symbol and function symbols taken from an infinite set F. The chosen domain is the set of trees whose nodes, in possibly infinite number, are labelled by elements of F. The operation linked to each element f of F is the mapping (a 1,..., a n ) ↦ b, where b is the tree whose initial node is labelled f and whose sequence of daughters is a 1,..., a n .We first consider tree constraints involving long alternated sequences of quantifiers ∃∀∃∀.... We show how to express winning positions of two-person games with such constraints and apply our results to two examples.We then construct a family of strongly expressive tree constraints, inspired by a constructive proof of a complexity result by Pawel Mielniczuk. This family involves the huge number α(k), obtained by top down evaluating a power tower of 2's, of height k. By a tree constraint of size proportional to k, it is then possible to define a tree having exactly α(k) nodes or to express the multiplication table computed by a Prolog machine executing up to α(k) instructions.By replacing the Prolog machine with a Turing machine we show the quasi-universality of tree constraints, that is to say, the ability to concisely describe trees which the most powerful machine will never have time to compute. We also rediscover the following result of Sergei Vorobyov: the complexity of an algorithm, deciding whether a tree constraint without free variables is true, cannot be bounded above by a function obtained from finite composition of simple functions including exponentiation.Finally, taking advantage of the fact that we have at our disposal an algorithm for solving such constraints in all their generalities, we produce a set of benchmarks for separating feasible examples from purely speculative ones. Among others we notice that it is possible to solve a constraint of 5000 symbols involving 160 alternating quantifiers.
Starting Page	283
Ending Page	302
Page Count	20
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	8
Issue Number	3
e-ISSN	15729354
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	2003-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computing Methodologies Artificial Intelligence (incl. Robotics) Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

Constraints meet concurrency

PhD theses in constraints

PhD theses in constraints 2012–2015

Decision diagrams for optimization

New techniques for discrete optimization

Editor’s note

Grammar constraints

Probabilistic constraint reasoning

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

Similar Documents

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees

Constraints meet concurrency

PhD theses in constraints

PhD theses in constraints 2012–2015

Decision diagrams for optimization

New techniques for discrete optimization

Editor’s note

Grammar constraints

Probabilistic constraint reasoning

Expressiveness of Full First-Order Constraints in the Algebra of Finite or Infinite Trees