Language Recognition Power and Succinctness of Affine Automata

DOI10.1007/978-3-319-41312-9_10MaRDI QIDQ2819147zbMATH OpenOpenAlexFDO

Authors Marcos Villagra, Abuzer Yakaryılmaz

Publication date 28 September 2016

Published in Unconventional Computation and Natural Computation (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic automataquantum automatastate complexitybounded-erroraffine automataone-sided errorstochastic language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Recommendations

• Language recognition power and succinctness of affine automata
• EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
• scientific article; zbMATH DE number 1962778
• Languages recognized by a class of finite automata
• Language recognition by two-way deterministic pushdown automata
• scientific article; zbMATH DE number 3870629
• On the computational power of affine automata
• scientific article; zbMATH DE number 3958761
• scientific article; zbMATH DE number 3978426
• scientific article; zbMATH DE number 4001511

Cites work

• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Affine computation and affine automaton
• Characterizations of one-way general quantum finite automata
• Implications of quantum automata for contextuality
• Language Recognition Power and Succinctness of Affine Automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Languages recognized by nondeterministic quantum finite automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Potential of quantum finite automata with exact acceptance
• Probabilistic automata
• Quantum automata and quantum grammars
• Quantum finite automata: a modern introduction
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Word-functions of stochastic and pseudo stochastic automata

Cited in

(14)

• Language Recognition Power and Succinctness of Affine Automata
• On the computational power of affine automata
• Language recognition by two-way deterministic pushdown automata
• Exact affine counter automata
• Exact Affine Counter Automata
• Affine computation and affine automaton
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Language recognition power and succinctness of affine automata
• Computational limitations of affine automata and generalized affine automata
• Space-efficient recognition of sparse self-reducible languages
• Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition
• Improved constructions for succinct affine automata
• Affine automata verifiers

This page was built for publication: Language Recognition Power and Succinctness of Affine Automata

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