Algorithmic problems for differential polynomial algebras

DOI10.1016/J.JALGEBRA.2016.02.010MaRDI QIDQ267385zbMATH OpenOpenAlexFDO

Authors Ualbai Umirbaev

Publication date 8 April 2016

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07230

zbMATH Keywords

differential polynomial algebrasGroebner basesMinsky machinesthe ideal membership problemthe subalgebra membership problem

Mathematics Subject Classification ID

Differential algebra (12H05) Decidability and field theory (12L05) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Differential graded algebras and applications (associative algebraic aspects) (16E45) Computational aspects of associative rings (general theory) (16Z05)

Abstract: We prove that the ideal membership problem and the subalgebra membership problem are algorithmically undecidable for differential polynomial algebras with at least two basic derivation operators.

Review text

In this paper it is proved that the membership problem for finitely generated differential ideals of differential algebras with at least two derivation operators is algorithmically undecidable, i.e. the word problem for differential algebras is undecidable. The main instrument of proving this is an interpretation of Minsky machines. The proof uses the fact that every recursive function can be calculated by Minsky machines without cycles [the author, Algebra Logic 32, No. 4, 244--255 (1993); translation from Algebra Logika 32, No. 4, 450--470 (1993; Zbl 0851.16023)] a method of interpreting the ideal membership problem from [the author, ``The occurrence problem in free associative and free Jordan algebras, in: Algorithmic problems in algebra and model theory, 11--15 (1995)], it is also proved that the membership problem for finitely generated differential subalgebras is undecidable.

Recommendations

• Algorithms and methods in differential algebra
• Polynomial algorithms in computer algebra
• Publication:3031846
• scientific article; zbMATH DE number 5154
• Polynomial complexity algorithms for computational problems in the theory of algebraic curves
• Algorithmic polynomials
• Algorithmic Polynomials
• Computational algorithms for algebraic operations on multidimensional polynomials
• Problems of computer algebra involved in the search for polynomial solutions of linear differential and difference equations
• Algorithms yield upper bounds in differential algebra

Cites work

• Algorithmic problems in associative algebras
• ALGORITHMIC PROBLEMS IN VARIETIES
• Associative differential operations
• Die Unterringe der freien Lieschen Ringe
• Gröbner-Shirshov bases and their calculation
• scientific article; zbMATH DE number 4181494 (Why is no real title available?)
• scientific article; zbMATH DE number 3170376 (Why is no real title available?)
• scientific article; zbMATH DE number 4138006 (Why is no real title available?)
• scientific article; zbMATH DE number 4085632 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• scientific article; zbMATH DE number 17848 (Why is no real title available?)
• scientific article; zbMATH DE number 177871 (Why is no real title available?)
• scientific article; zbMATH DE number 3627285 (Why is no real title available?)
• scientific article; zbMATH DE number 1252509 (Why is no real title available?)
• scientific article; zbMATH DE number 503186 (Why is no real title available?)
• scientific article; zbMATH DE number 612877 (Why is no real title available?)
• scientific article; zbMATH DE number 1979252 (Why is no real title available?)
• scientific article; zbMATH DE number 2146477 (Why is no real title available?)
• scientific article; zbMATH DE number 1860838 (Why is no real title available?)
• scientific article; zbMATH DE number 3285229 (Why is no real title available?)
• scientific article; zbMATH DE number 3415973 (Why is no real title available?)
• scientific article; zbMATH DE number 3082632 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Membership problem for differential ideals generated by a composition of polynomials
• Occurrence problem for free solvable groups
• Systems of linear equations and the word problem for the varieties \({\mathfrak N}_2{\mathfrak N}_c\) of Lie algebras
• Systems of linear equations over associative algebras and the occurrence problem for lie algebras
• The occurrence problem for extensions of Abelian groups by nilpotent groups
• The occurrence problem for free metanilpotent Lie algebras
• The occurrence problem for Lie algebras
• The word problem for subvarieties of the variety \({\mathfrak N}_ 2{\mathfrak A}\)
• Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence

Cited in

(13)

• Algorithmic problems in associative algebras
• Membership problem for differential ideals generated by a composition of polynomials
• Algorithm for checking triviality of ``mixed ideals in the ring of differential polynomials
• SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY
• scientific article; zbMATH DE number 177871 (Why is no real title available?)
• Une note sur les algorithmes de décomposition en algèbre différentielle
• scientific article; zbMATH DE number 1567883 (Why is no real title available?)
• Algorithmic problems for free Poisson algebras
• Complete Algorithms for Algebraic Strongest Postconditions and Weakest Preconditions in Polynomial ODE’S
• A new algorithm for computing regular representations for radicals of parametric differential ideals
• scientific article; zbMATH DE number 224226 (Why is no real title available?)
• Differential algebraic dependence and Novikov dependence
• Differential elimination and algebraic invariants of polynomial dynamical systems

This page was built for publication: Algorithmic problems for differential polynomial algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q267385)