Language Recognition Power and Succinctness of Affine Automata
DOI10.1007/978-3-319-41312-9_10zbMATH Open1476.68139arXiv1602.05432OpenAlexW2275579475MaRDI QIDQ2819147FDOQ2819147
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
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
probabilistic automataquantum automatastate complexitybounded-erroraffine automataone-sided errorstochastic language
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Cites Work
- Succinctness of two-way probabilistic and quantum finite automata
- Unbounded-error quantum computation with small space bounds
- Probabilistic automata
- Title not available (Why is that?)
- Characterizations of one-way general quantum finite automata
- Title not available (Why is that?)
- Quantum automata and quantum grammars
- Languages recognized by nondeterministic quantum finite automata
- Superiority of exact quantum automata for promise problems
- Potential of quantum finite automata with exact acceptance
- Languages Recognized with Unbounded Error by Quantum Finite Automata
- Implications of quantum automata for contextuality
- Title not available (Why is that?)
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Affine computation and affine automaton
- Quantum finite automata: a modern introduction
- Space-Efficient Deterministic Simulation of Probabilistic Automata
- Word-functions of stochastic and pseudo stochastic automata
- Language Recognition Power and Succinctness of Affine Automata
- Looking for Pairs that Hard to Separate: A Quantum Approach
Cited In (14)
- 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
- Language recognition power and succinctness of affine automata
- Looking for Pairs that Hard to Separate: A Quantum Approach
- 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
- Language Recognition Power and Succinctness of Affine Automata
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)
