A context-free language which is not acceptable by a probabilistic automaton

DOI10.1016/S0019-9958(71)90373-1zbMath0218.68012MaRDI QIDQ5623234

Namio Honda, Masakazu Nasu

Publication date: 1971

Published in: Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Quantum alternation ⋮ Probabilistic automata ⋮ Stochastic grammars and languages ⋮ Propriétés booléennes des langages stochastiques ⋮ Lower space bounds for randomized computation ⋮ QUANTUM COUNTER AUTOMATA ⋮ Quantum computation with write-only memory ⋮ Unbounded-error quantum computation with small space bounds ⋮ The notion of a probabilistic cellular acceptor ⋮ Classes of formal grammars ⋮ THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA ⋮ Languages Recognized with Unbounded Error by Quantum Finite Automata ⋮ Theory of one-tape linear-time Turing machines