Detecting all dependences in systems of geometric constraints using the witness method

Dominique Michelucci; Sebti Foufou

doi:10.1007/978-3-540-77356-6_7

Detecting all dependences in systems of geometric constraints using the witness method

Dominique Michelucci, Sebti Foufou

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences. We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposition.

Original language	English (US)
Title of host publication	Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers
Publisher	Springer Verlag
Pages	98-112
Number of pages	15
ISBN (Print)	354077355X, 9783540773559
DOIs	https://doi.org/10.1007/978-3-540-77356-6_7
State	Published - 2007
Event	6th International Workshop on Automated Deduction in Geometry, ADG 2006 - Pontevedra, Spain Duration: Aug 31 2006 → Sep 2 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4869 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th International Workshop on Automated Deduction in Geometry, ADG 2006
Country/Territory	Spain
City	Pontevedra
Period	8/31/06 → 9/2/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-77356-6_7

Cite this

Michelucci, D., & Foufou, S. (2007). Detecting all dependences in systems of geometric constraints using the witness method. In Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers (pp. 98-112). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4869 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-540-77356-6_7

Detecting all dependences in systems of geometric constraints using the witness method. / Michelucci, Dominique; Foufou, Sebti.
Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers. Springer Verlag, 2007. p. 98-112 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4869 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Michelucci, D & Foufou, S 2007, Detecting all dependences in systems of geometric constraints using the witness method. in Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4869 LNAI, Springer Verlag, pp. 98-112, 6th International Workshop on Automated Deduction in Geometry, ADG 2006, Pontevedra, Spain, 8/31/06. https://doi.org/10.1007/978-3-540-77356-6_7

Michelucci D, Foufou S. Detecting all dependences in systems of geometric constraints using the witness method. In Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers. Springer Verlag. 2007. p. 98-112. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-77356-6_7

Michelucci, Dominique ; Foufou, Sebti. / Detecting all dependences in systems of geometric constraints using the witness method. Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers. Springer Verlag, 2007. pp. 98-112 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e0345c4a24f8405db7eea7edadb35106,

title = "Detecting all dependences in systems of geometric constraints using the witness method",

abstract = "In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences. We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposition.",

author = "Dominique Michelucci and Sebti Foufou",

year = "2007",

doi = "10.1007/978-3-540-77356-6_7",

language = "English (US)",

isbn = "354077355X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "98--112",

booktitle = "Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers",

note = "6th International Workshop on Automated Deduction in Geometry, ADG 2006 ; Conference date: 31-08-2006 Through 02-09-2006",

}

TY - GEN

T1 - Detecting all dependences in systems of geometric constraints using the witness method

AU - Michelucci, Dominique

AU - Foufou, Sebti

PY - 2007

Y1 - 2007

N2 - In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences. We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposition.

AB - In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences. We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposition.

UR - http://www.scopus.com/inward/record.url?scp=38549089466&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38549089466&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-77356-6_7

DO - 10.1007/978-3-540-77356-6_7

M3 - Conference contribution

AN - SCOPUS:38549089466

SN - 354077355X

SN - 9783540773559

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 98

EP - 112

BT - Automated Deduction in Geometry - 6th International Workshop, ADG 2006, Revised Papers

PB - Springer Verlag

T2 - 6th International Workshop on Automated Deduction in Geometry, ADG 2006

Y2 - 31 August 2006 through 2 September 2006

ER -

Detecting all dependences in systems of geometric constraints using the witness method

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this