One-counter verifiers for decidable languages

DOI10.1007/978-3-642-38536-0_32MaRDI QIDQ4928501zbMATH OpenOpenAlexFDO

Authors Abuzer Yakaryılmaz

Publication date 14 June 2013

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS's for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca's). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be space efficient. As a further result, if the 2qcca can use a quantum counter instead of a classical one, then the protocol can even be public, also known as Arthur-Merlin games. We also investigate the computational power of 2pca's and 2qcca's as language recognizers. We show that bounded-error 2pca's can be more powerful than their deterministic counterparts by giving a bounded-error simulation of their nondeterministic counterparts. Then, we present a new programming technique for bounded-error 2qcca's and show that they can recognize a language which seems not to be recognized by any bounded-error 2pca. We also obtain some interesting results for bounded-error 1-pebble quantum finite automata based on this new technique. Lastly, we prove a conjecture posed by Ravikumar (FSTTCS 1992) regarding 1-pebble probabilistic finite automata, i.e. they can recognize some nonstochastic languages with bounded error.

Recommendations

• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• One-way probabilistic reversible and quantum one-counter automata.
• scientific article; zbMATH DE number 1696659
• Quantum versus deterministic counter automata

Cited in

(9)

• scientific article; zbMATH DE number 7104930 (Why is no real title available?)
• One-way permutations and self-witnessing languages
• Decidability of bisimilarity for one-counter processes.
• Regular Realizability Problems and Context-Free Languages
• On regular realizability problems for context-free languages
• New results on the minimum amount of useful space
• scientific article; zbMATH DE number 1670834 (Why is no real title available?)
• One-counter automata for parsing and language approximation
• MTL and TPTL for One-Counter Machines

This page was built for publication: One-counter verifiers for decidable languages

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