Cover Image

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yamakami, Tomoyuki
Format:	Preprint
Published:	2019
Subjects:	Formal Languages and Automata Theory Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
by: Yamakami, Tomoyuki
Published: (2020)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
by: Yamakami, Tomoyuki
Published: (2021)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Complexity of Unary Exclusive Nondeterministic Finite Automata
by: Kutrib, Martin, et al.
Published: (2024)

On the Simulation Cost of Quantum Finite Automata
by: Chen, Zeyu, et al.
Published: (2026)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
by: Haneef, Farah
Published: (2024)

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

Finite Automata Encoding Piecewise Polynomials
by: Berdinsky, Dmitry, et al.
Published: (2021)

Maximal Length Cellular Automata : A Survey
by: Adak, Sumit, et al.
Published: (2024)

A Representative Framework for Implementing Quantum Finite Automata on Real Devices
by: Khadieva, Aliya, et al.
Published: (2024)

Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications
by: Moreira, Nelma, et al.
Published: (2025)

Unconditional proofs of quantumness between small-space machines
by: Say, A. C. Cem, et al.
Published: (2024)

QIP $ \subseteq $ AM(2QCFA)
by: Yakaryılmaz, Abuzer
Published: (2025)

Classical and quantum Merlin-Arthur automata
by: Yakaryılmaz, Abuzer
Published: (2022)

Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024)
by: Manea, Florin, et al.
Published: (2024)

Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata
by: Ziiatdinov, Mansur, et al.
Published: (2024)

Landauer Principle and Thermodynamics of Computation
by: Chattopadhyay, Pritam, et al.
Published: (2025)

Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
by: Vinarskii, Evgenii, et al.
Published: (2025)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
by: Gezer, M. Utkan, et al.
Published: (2020)

Quantum Büchi Automata
by: Wang, Qisheng, et al.
Published: (2018)

An Invitation to Universality in Physics, Computer Science, and Beyond
by: Gonda, Tomáš, et al.
Published: (2024)

Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
by: Mazowiecki, Filip, et al.
Published: (2025)

Query Learning of Advice and Nominal Automata
by: Zhou, Kevin
Published: (2024)

Measure Many Quantum Finite Automata on Infinite Words
by: Midya, Abhisek, et al.
Published: (2026)

SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
by: Marzouk, Reda, et al.
Published: (2025)

Implementing a Quantum Finite Automaton in IBMQ using Custom Control Pulses
by: Lussi, Eduardo Willwock, et al.
Published: (2024)

Characterizing the Polynomial-Time Minimizable $ω$-Automata
by: Radi, Bader Abu, et al.
Published: (2025)

On the complexity of computing Strahler numbers
by: Ganardi, Moses, et al.
Published: (2025)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
by: Podolskii, Vladimir, et al.
Published: (2024)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
by: Uezato, Yuya
Published: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
by: Arvind, V., et al.
Published: (2024)

Entropy of pebble automata and space complexity
by: Montoya, J. Andres
Published: (2026)

Complexity of Fungal Automaton Prediction
by: Formenti, Enrico, et al.
Published: (2026)

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
by: Bozga, Marius, et al.
Published: (2026)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
by: Chen, Zeyu, et al.
Published: (2025)