Improved constructions for succinct affine automata

DOI10.1007/978-3-030-93489-7_16MaRDI QIDQ2096598zbMATH OpenOpenAlexFDO

Authors Abuzer Yakaryılmaz

Publication date 9 November 2022

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

zbMATH Keywords

affine automatabounded errorlinear systemsone-sided errorprobabilistic automataquantum automatastate complexitysuccinctnesszero error

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Affine automata verifiers
• Affine computation and affine automaton
• Automata and quantum computing
• Characterizations of one-way general quantum finite automata
• Computational limitations of affine automata
• Error-free affine, unitary, and probabilistic OBDDs
• Exact affine counter automata
• Finite state verifiers with constant randomness
• Generalized Automata and Stochastic Languages
• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Interference as a computational resource: a tutorial
• Language Recognition Power and Succinctness of Affine Automata
• Languages recognized by nondeterministic quantum finite automata
• On a conjecture by Christian Choffrut
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the computational power of affine automata
• Probabilistic automata
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• The complexity of probabilistic versus deterministic finite automata
• Unbounded-error quantum computation with small space bounds

Cited in

(1)

• Real-valued affine automata compute beyond Turing machines

This page was built for publication: Improved constructions for succinct affine automata

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