Quantum finite automata: advances on Bertoni's ideas

DOI10.1016/J.TCS.2016.01.045zbMATH Open1359.68159OpenAlexW2254370953MaRDI QIDQ517033FDOQ517033

Authors: Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano 

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.01.045

Recommendations

• Quantum automata for some multiperiodic languages
• Quantum finite automata: a modern introduction
• Quantum automata and periodic events
• scientific article; zbMATH DE number 1490003
• Implementation and Application of Automata

zbMATH Keywords

descriptional complexityquantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Two-way finite automata with quantum and classical states.
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Title not available (Why is that?)
• Title not available (Why is that?)
• One-way finite automata with quantum and classical states
• On the power of one-way automata with quantum and classical states
• Quantum finite automata with control language
• Size lower bounds for quantum automata
• Strengths and Weaknesses of Quantum Computing
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the state complexity of semi-quantum finite automata
• Title not available (Why is that?)
• Quantum complexity theory
• Membership problems for regular and context-free trace languages
• The complexity of promise problems with applications to public-key cryptography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum mechanical Hamiltonian models of Turing machines
• Quantum information theory
• Quantum computing.
• The complexity of minimum difference cover
• Descriptional complexity -- an introductory survey
• Title not available (Why is that?)
• Improved constructions of quantum automata
• Quantum automata and quantum grammars
• Algebraic results on quantum automata
• Characterizations of 1-Way Quantum Finite Automata
• Superiority of exact quantum automata for promise problems
• Title not available (Why is that?)
• Quantum automata for some multiperiodic languages
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• Behaviours of unary quantum automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trace monoids with idempotent generators and measure-only quantum automata
• Unary probabilistic and quantum automata on promise problems
• Complexity of promise problems on classical and quantum automata
• State complexity of operations on two-way finite automata over a unary alphabet
• Title not available (Why is that?)
• Regular languages accepted by quantum automata
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Implications of quantum automata for contextuality
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• Semantic alternatives in partial Boolean quantum logic
• Quantum automata and periodic events
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Normal forms for unary probabilistic automata
• Title not available (Why is that?)
• On the decidability of the intersection problem for quantum automata and context-free languages
• Algebraic characterization of the class of languages recognized by measure only quantum automata
• Decidable and Undecidable Problems about Quantum Automata
• Quantum state complexity of formal languages
• Lower bounds on the size of quantum automata accepting unary languages.
• Analogies and differences between quantum and stochastic automata

Cited In (13)

• Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
• Lifting query complexity to time-space complexity for two-way finite automata
• Characterization of tree automata based on quantum logic
• Improved constructions of quantum automata
• Descriptional complexity of iterated uniform finite-state transducers
• Mirrors and memory in quantum automata
• Title not available (Why is that?)
• Relativizations of nonuniform quantum finite automata families
• Title not available (Why is that?)
• On finite automata with quantum and classical states
• The descriptional power of queue automata of constant length
• Title not available (Why is that?)
• Quantum \(\omega\)-automata over infinite words and their relationships

This page was built for publication: Quantum finite automata: advances on Bertoni's ideas

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