Search results for " Formal languages"
showing 10 items of 79 documents
Alternating, private alternating, and quantum alternating realtime automata
2014
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we present two equivalent definitions of realtime private alternating finite automata (PAFAs). We show that the emptiness problem is undecidable for PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages, including the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. Regarding quantum finite automata (QFAs), we show that the emptiness problem is undecidable both for universal QFAs o…
Probabilistic verification of all languages
2018
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any language, there is a constant-space weak-IPS (the non-members may not be rejected with high probability); and, (iii) for any language, there is a constant-space IPS with two provers where the verifier reads the input once. Additionally, we show that uncountably many binary (unary) languages can be verified in constant space and in linear (quadratic) expected time.
Inkdots as advice for finite automata
2015
We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of advised finite automata. The existence of an infinite hierarchy of classes of languages that can be recognized with the help of increasing numbers of inkdots as advice is shown. The effects of different forms of advice on the succinctness of the advised machines are examined. We also study randomly placed inkdots as advice to probabilistic finite automata, and demonstrate the superiority of this model over its deterministic version. Even very slowly growing amounts of space can become a resource of meaningful use i…
Uncountable realtime probabilistic classes
2017
We investigate the minimum cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.
Zero-Error Affine, Unitary, and Probabilistic OBDDs
2017
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.
Nondeterministic unitary OBDDs
2016
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically cheap functions that are expensive for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
Debates with small transparent quantum verifiers
2014
We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most $\mathsf{NP}$ to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least $\mathsf{E}$. We also show that the quantum model outperforms its classical counterpart when restricted to run in p…
Log-space counter is useful for unary languages by help of a constant-size quantum register
2013
The minimum amount of resources to recognize a nonregular language is a fundamental research topic in theoretical computer science which has been examined for different kinds of resources and many different models. In this note, we focus on unary languages and space complexity on counters. Our model is two-way one-counter automaton with quantum and classical states (2QCCA), which is a two-way finite automaton with one-counter (2DCA) augmented with a fixed size quantum register or a two-way finite automaton with quantum and classical states (2QCFA) augmented with a classical counter. It is known that any 2DCA using a sublinear space on its counter can recognize only regular languages \cite{D…
Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
2023
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.
One-counter verifiers for decidable languages
2012
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 spac…