nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

20.03.2022 | Original Paper

Decision problem for a class of univariate Pfaffian functions

verfasst von: María Laura Barbagallo, Gabriela Jeronimo, Juan Sabia

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We address the decision problem for sentences involving univariate functions constructed from a fixed Pfaffian function of order 1. We present a new symbolic procedure solving this problem with a computable complexity based on the computation of suitable Sturm sequences. For a general Pfaffian function, we assume the existence of an oracle to determine the sign that a function of the class takes at a real algebraic number. As a by-product, we obtain a new oracle-free effective algorithm solving the same problem for univariate E-polynomials based on techniques that are simpler than the previous ones, and we apply it to solve a similar decision problem in the multivariate setting. Finally, we introduce a notion of Thom encoding for zeros of an E-polynomial and describe an algorithm for their computation.

Vorheriger Artikel Symbol-pair distance of some repeated-root constacyclic codes of length over the Galois ring

Nächster Artikel Multidimensional Byzantine agreement in a synchronous setting

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Khovanskii, A.: On a class of systems of transcendental equations. Soviet Math. Dokl. 22, 762–765 (1980)

Khovanskii, A.: Fewnomials. Translations of Mathematical Monographs, 88. American Mathematical Society, Providence, RI, (1991)

Gabrielov, A., Vorobjov, N.: Complexity of computations with Pfaffian and Noetherian functions. In Normal Forms, Bifurcations and Finiteness Problems in Differential Equations, Kluwer (2004)

Tarski, A.: A decision method for elementary algebra and geometry, 2nd edn. Universtiy of California Press, Berkeley, Los Angeles (1951)CrossRef

van den Dries, L.: Remarks on Tarski’s problem concerning \(({\mathbf{R}},+,\cdot ,\text{exp})\). Logic Colloquium ’82 (Florence, 1982), 97–121, Stud. Logic Found. Math., 112, North-Holland, Amsterdam (1984)

Macintyre, A., Wilkie, A.J.: On the decidability of the real exponential field. Kreiseliana, 441–467, A K Peters, Wellesley, MA (1996)

Richardson, D.: Towards computing non algebraic cylindrical decompositions. In: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC '91), pp. 247–255. Association for Computing Machinery, New York, NY, USA (1991)CrossRef

Vorobjov, N.: The complexity of deciding consistency of systems of polynomials in exponent inequalities. J. Symbolic Comput. 13(2), 139–173 (1992)MathSciNetCrossRef

Maignan, A.: Solving one and two-dimensional exponential polynomial systems. In: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC '98), pp. 215–221. Association for Computing Machinery, New York, NY, USA (1998)CrossRef

10.

Anai, H., Weispfenning, V.: Deciding linear-trigonometric problems. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (ISSAC '00), pp. 14–22. Association for Computing Machinery, New York, NY, USA (2000)CrossRef

11.

Weispfenning, V.: Deciding linear-transcendental problems. In: Computer Algebra in Scientific Computing, pp. 423–437. Springer, Berlin (2000)CrossRef

12.

Achatz, M., McCallum, S., Weispfenning, V.: Deciding polynomial-exponential problems. In: Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation (ISSAC '08), pp. 215–222. Association for Computing Machinery, New York, NY, USA (2008)

13.

Roy, M.-F., Vorobjov, N.: Finding irreducible components of some real transcendental varieties. Comput. Complexity 4, 107–132 (1994)MathSciNetCrossRef

14.

McCallum, S., Weispfenning, V.: Deciding polynomial-transcendental problems. J. Symbol. Comput. 47, 16–31 (2013)MathSciNetCrossRef

15.

Xu, M., Li, Z.-B., Yang, L.: Quantifier elimination for a class of exponential polynomial formulas. J. Symbolic Comput. 68, 146–168 (2015)MathSciNetCrossRef

16.

Barbagallo, M.L., Jeronimo, G., Sabia, J.: Zero counting for a class of univariate Pfaffian functions. J. Algebra 452, 549–573 (2016)MathSciNetCrossRef

17.

van der Hoeven, J., Shackell, J.R.: Complexity bounds for zero-test algorithms. J. Symbolic Comput. 41, 1004–1020 (2006)MathSciNetCrossRef

18.

Waldschmidt, M.: Transcendence measures for exponentials and logarithms. J. Austral. Math. Soc. Ser. A 25(4), 445–465 (1978)MathSciNetCrossRef

19.

von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)

20.

Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry. Second edition. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin, (2006). Online version available at http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html

21.

Perrucci, D.: Linear solving for sign determination. Theoret. Comput. Sci. 412(35), 4715–4720 (2011)MathSciNetCrossRef

22.

Heindel, L.E.: Integer arithmetic algorithms for polynomial real zero determination. J. Assoc. Comput. Mach. 18, 533–548 (1971)MathSciNetCrossRef

23.

Canny, J.: Improved algorithms for sign determination and existencial quantifier elimination. Computer Science Division, University of California, Berkeley 94720 USA. Comput. J. Vol. 36, No 5, (1993)

Titel: Decision problem for a class of univariate Pfaffian functions
verfasst von: María Laura Barbagallo
Gabriela Jeronimo
Juan Sabia
Publikationsdatum: 20.03.2022
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2024
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-022-00545-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2024

On Kostant’s weight q-multiplicity formula for

Univariate polynomial factorization over finite fields with large extension degree

Multidimensional Byzantine agreement in a synchronous setting

In memoriam Kai-Uwe Schmidt

Distance-regular graphs and new block designs obtained from the Mathieu groups

Symbol-pair distance of some repeated-root constacyclic codes of length over the Galois ring

Premium Partner