One-counter verifiers for decidable languages

DOI10.1007/978-3-642-38536-0_32zbMATH Open1382.68138arXiv1207.3880OpenAlexW2963588035MaRDI QIDQ4928501FDOQ4928501

Authors: Abuzer Yakaryılmaz 

Publication date: 14 June 2013

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

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.

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

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

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)

Cited In (9)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)