Back to Search
Start Over
Typing linear constraints
- Source :
- ACM transactions on programming languages and systems (Online) 32 (2010): 21–42. doi:10.1145/1749608.1749610, info:cnr-pdr/source/autori:Ruggieri S.; Mesnard F./titolo:Typing linear constraints/doi:10.1145%2F1749608.1749610/rivista:ACM transactions on programming languages and systems (Online)/anno:2010/pagina_da:21/pagina_a:42/intervallo_pagine:21–42/volume:32, ACM Transactions on Programming Languages and Systems (TOPLAS), ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2010, 32 (6), pp.en ligne. ⟨10.1145/1749608.1749610⟩
- Publication Year :
- 2010
- Publisher :
- Association for Computing Machinery (ACM), 2010.
-
Abstract
- We present a type system for linear constraints over the reals intended for reasoning about the input-output directionality of variables. Types model the properties of definiteness, range width or approximation, lower and upper bounds of variables in a linear constraint. Several proof procedures are presented for inferring the type of a variable and for checking validity of type assertions. We rely on theory and tools for linear programming problems, linear algebra, parameterized polyhedra and negative constraints. An application of the type system is proposed in the context of the static analysis of constraint logic programs. Type assertions are at the basis of the extension of well-moding from pure logic programming. The proof procedures (both for type assertion validity and for well-moding) are implemented and their computational complexity is discussed. We report experimental results demonstrating the efficiency in practice of the proposed approach.
- Subjects :
- Linear programming
Computer science
Definiteness
Parameterized complexity
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Data type
Constraint logic programming
0202 electrical engineering, electronic engineering, information engineering
[INFO]Computer Science [cs]
[MATH]Mathematics [math]
Polyhedra
ComputingMilieux_MISCELLANEOUS
Linear constraints
Verification
020207 software engineering
Constraint (information theory)
Algebra
Variable (computer science)
Type theory
010201 computation theory & mathematics
Linear algebra
Languages
Well-moding
Algorithm
Software
Subjects
Details
- ISSN :
- 15584593 and 01640925
- Volume :
- 32
- Database :
- OpenAIRE
- Journal :
- ACM Transactions on Programming Languages and Systems
- Accession number :
- edsair.doi.dedup.....af64e7888df506728cd1146f8226bc6c