Mostrar el registro sencillo del ítem
dc.contributor.author | Lucas Alba, Salvador | es_ES |
dc.date.accessioned | 2015-06-05T11:15:36Z | |
dc.date.available | 2015-06-05T11:15:36Z | |
dc.date.issued | 2014-12 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://hdl.handle.net/10251/51307 | |
dc.description.abstract | Proving polynomials non-negative when variables range on a subset of numbers (e.g., [0, +∞)) is often required in many applications (e.g., in the analysis of program termination). Several representations for univariate polynomials P that are non-negative on [0, +∞) have been investigated. They can often be used to characterize the property, thus providing a method for checking it by trying a match of P against the representation. We introduce a new characterization based on viewing polynomials P as vectors, and find the appropriate polynomial basis B in which the non-negativeness of the coordinates [P]B representing P in B witnesses that P is non-negative on [0, +∞). Matching a polynomial against a representation provides a way to transform universal sentences ∀x ∈ [0, +∞) P(x) ≥ 0 into a constraint solving problem which can be solved by using efficient methods. We consider different approaches to solve both kind of problems and provide a quantitative evaluation of performance that points to an early result by P´olya and Szeg¨o’s as an appropriate basis for implementations in most cases. | es_ES |
dc.language | Inglés | es_ES |
dc.publisher | Springer Verlag (Germany) | es_ES |
dc.relation.ispartof | Artificial Intelligence and Symbolic Computation: 12th International Conference, AISC 2014, Seville, Spain, December 11-13, 2014. Proceedings | es_ES |
dc.relation.ispartofseries | Lecture Notes in Computer Science;8884 | |
dc.rights | Reserva de todos los derechos | es_ES |
dc.subject | Polynomial inequalities | es_ES |
dc.subject | Representation theorems | es_ES |
dc.subject | Positive polynomials | es_ES |
dc.subject.classification | LENGUAJES Y SISTEMAS INFORMATICOS | es_ES |
dc.title | Using Representation Theorems for Proving Polynomials Non-negative | es_ES |
dc.type | Capítulo de libro | es_ES |
dc.identifier.doi | 10.1007/978-3-319-13770-4_4 | |
dc.rights.accessRights | Abierto | es_ES |
dc.contributor.affiliation | Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació | es_ES |
dc.description.bibliographicCitation | Lucas Alba, S. (2014). Using Representation Theorems for Proving Polynomials Non-negative. En Artificial Intelligence and Symbolic Computation: 12th International Conference, AISC 2014, Seville, Spain, December 11-13, 2014. Proceedings. Springer Verlag (Germany). 21-33. doi:10.1007/978-3-319-13770-4_4 | es_ES |
dc.description.accrualMethod | S | es_ES |
dc.relation.publisherversion | http://link.springer.com/chapter/10.1007/978-3-319-13770-4_4 | es_ES |
dc.description.upvformatpinicio | 21 | es_ES |
dc.description.upvformatpfin | 33 | es_ES |
dc.type.version | info:eu-repo/semantics/publishedVersion | es_ES |
dc.relation.senia | 279094 | |
dc.description.references | Alarcón, B., Gutiérrez, R., Lucas, S., Navarro-Marset, R.: Proving Termination Properties with mu-term. In: Johnson, M., Pavlovic, D. (eds.) AMAST 2010. LNCS, vol. 6486, pp. 201–208. Springer, Heidelberg (2011) | es_ES |
dc.description.references | Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, Berlin (2006) | es_ES |
dc.description.references | Bernstein, S.: Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités. Communic. Soc. Math. de Kharkow 13(2), 1–2 (1912) | es_ES |
dc.description.references | Bernstein, S.: Sur la répresentation des polynômes positifs. Communic. Soc. Math. de Kharkow 14(2), 227–228 (1915) | es_ES |
dc.description.references | Borralleras, C., Lucas, S., Oliveras, A., Rodríguez, E., Rubio, A.: SAT Modulo Linear Arithmetic for Solving Polynomial Constraints. Journal of Automated Reasoning 48, 107–131 (2012) | es_ES |
dc.description.references | Boudaoud, F., Caruso, F., Roy, M.-F.: Certificates of Positivity in the Bernstein Basis. Discrete Computational Geometry 39, 639–655 (2008) | es_ES |
dc.description.references | Choi, M.D., Lam, T.Y., Reznick, B.: Sums of squares of real polynomials. In: Proc. of the Symposium on Pure Mathematics, vol. 4, pp. 103–126. American Mathematical Society (1995) | es_ES |
dc.description.references | Contejean, E., Marché, C., Tomás, A.-P., Urbain, X.: Mechanically proving termination using polynomial interpretations. Journal of Automated Reasoning 32(4), 315–355 (2006) | es_ES |
dc.description.references | Hilbert, D.: Über die Darstellung definiter Formen als Summe von Formenquadraten. Mathematische Annalen 32, 342–350 (1888) | es_ES |
dc.description.references | Hong, H., Jakuš, D.: Testing Positiveness of Polynomials. Journal of Automated Reasoning 21, 23–38 (1998) | es_ES |
dc.description.references | Karlin, S., Studden, W.J.: Tchebycheff systems: with applications in analysis and statistics. Interscience, New York (1966) | es_ES |
dc.description.references | Lucas, S.: Polynomials over the reals in proofs of termination: from theory to practice. RAIRO Theoretical Informatics and Applications 39(3), 547–586 (2005) | es_ES |
dc.description.references | Polya, G., Szegö, G.: Problems and Theorems in Analysis II. Springer (1976) | es_ES |
dc.description.references | Powers, V., Reznick, B.: Polynomials that are positive on an interval. Transactions of the AMS 352(10), 4677–4692 (2000) | es_ES |
dc.description.references | Powers, V., Wörmann, T.: An algorithm for sums of squares of real polynomials. Journal of Pure and Applied Algebra 127, 99–104 (1998) | es_ES |