Quantum automata and algebraic groups

DOI10.1016/j.jsc.2004.11.008zbMath1124.81004OpenAlexW2074794353MaRDI QIDQ2456549

Pascal Koiran, Emmanuel Jeandel, H. G. J. Derksen

Publication date: 19 October 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://hal-lara.archives-ouvertes.fr/hal-02101965/file/RR2003-39.pdf

zbMATH Keywords

undecidabilityalgebraic groupsalgebraic geometryprobabilistic automataQuantum automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Linear algebraic groups over arbitrary fields (20G15) Quantum computation (81P68)

Related Items

Deciding universality of quantum gates ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Embedding algorithms and applications to differential equations ⋮ Universality of single-qudit gates ⋮ Analyzing ultimate positivity for solvable systems ⋮ On the computation of the Galois group of linear difference equations ⋮ Zariski density and computing in arithmetic groups ⋮ Computing the binomial part of a polynomial ideal ⋮ Around the numeric-symbolic computation of differential Galois groups ⋮ A fast algorithm for computing multiplicative relations between the roots of a generic polynomial ⋮ Toric varieties from cyclic matrix semigroups ⋮ Some formal tools for analyzing quantum automata. ⋮ Unnamed Item ⋮ Real computational universality: the word problem for a class of groups with infinite presentation ⋮ Linear groups and computation ⋮ Finding Integral Linear Dependencies of Algebraic Numbers and Algebraic Lie Algebras ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ Constructing algebraic groups from their Lie algebras. ⋮ ON THE DECIDABILITY OF THE INTERSECTION PROBLEM FOR QUANTUM AUTOMATA AND CONTEXT-FREE LANGUAGES ⋮ Computing the Lie algebra of the differential Galois group: the reducible case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derivations and radicals of polynomial ideals over fields of arbitrary characteristic
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Deciding finiteness for matrix groups over function fields
• Quantum automata and quantum grammars
• Computational invariant theory
• The calculation of radical ideals in positive characteristic
• On commutative endomorphism rings
• On the combinatorial and algebraic complexity of quantifier elimination
• An effective lower bound for the height of algebraic numbers
• Decidable and Undecidable Problems about Quantum Automata
• Probabilistic automata
• An algorithm for computing the integral closure
• Computing the radical of an ideal in positive characteristic
• Deciding finiteness for matrix semigroups over function fields over finite fields. A note on a paper by Rockmore, Tan, and Beals
• Analogies and differences between quantum and stochastic automata