Improved constructions for succinct affine automata

DOI10.1007/978-3-030-93489-7_16OpenAlexW4206015765MaRDI QIDQ2096598

Abuzer Yakaryılmaz

Publication date: 9 November 2022

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

zbMATH Keywords

linear systemsstate complexityquantum automataprobabilistic automatasuccinctnessbounded errorzero erroraffine automataone-sided error

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Characterizations of one-way general quantum finite automata
• Error-free affine, unitary, and probabilistic OBDDs
• Affine automata verifiers
• Automata and quantum computing
• Computational limitations of affine automata
• Language Recognition Power and Succinctness of Affine Automata
• Finite state verifiers with constant randomness
• On quantum and probabilistic communication
• On a Conjecture by Christian Choffrut
• Probabilistic automata
• Generalized Automata and Stochastic Languages
• On the Computational Power of Affine Automata
• Affine Computation and Affine Automaton
• Interference as a computational resource: a tutorial

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