SOLVING LINEAR CONSTRAINTS ON FINITE DOMAINS THROUGH PARSING

• Type: Article in International Scientific Journal
• Date: 1991

Authors

FILGUEIRAS, M (Author) FCUP; TOMAS, AP (Author) FCUP

Journal

Title: Lecture Notes in Computer Science

Vol. 541

Pages: 1-16

ISSN: 0302-9743

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 1 Citation

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-001-R6F

Abstract (EN): In this paper we present results from ongoing research which allows the use of parsing methods to solve a particular kind of constraints, namely linear constraints on finite domains. Solving this kind of constraints is equivalent to solving systems of linear Diophantine equations on a finite subset of the naturals. We associate, to such a system, a definite-clause grammar that can be used to enumerate its solutions, and define a class of grammars, the connected grammars, for which the set of successful derivations covers the set of non-negative solutions of the associated system. This definition is based on a study of cycles in context-free grammars using compiler construction concepts and techniques.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 16