Source author record

Hamoon Mousavi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory math.CO Discrete Mathematics Computational Complexity quant-ph

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the complexity of zero gap MIP*

The class $\mathsf{MIP}^*$ is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that $\mathsf{MIP}^*$ is equal to $\mathsf{RE}$ , the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game $G$ is exactly $1$ . This problem corresponds to a complexity class that we call zero gap $\mathsf{MIP}^*$ , denoted by $\mathsf{MIP}^*_0$ , where there is no promise gap between the verifier's acceptance probabilities in the YES and NO cases. We prove that $\mathsf{MIP}^*_0$ extends beyond the first level of the arithmetical hierarchy (which includes $\mathsf{RE}$ and its complement $\mathsf{coRE}$ ), and in fact is equal to $Π_2^0$ , the class of languages that can be decided by quantified formulas of the form $\forall y \, \exists z \, R(x,y,z)$ . Combined with the previously known result that $\mathsf{MIP}^{co}_0$ (the commuting operator variant of $\mathsf{MIP}^*_0$ ) is equal to $\mathsf{coRE}$ , our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.

preprint2014arXiv

Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Fibonacci-automatic". This class includes, for example, the famous Fibonacci word f = 01001010..., the fixed point of the morphism 0 -> 01 and 1 -> 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth. As an application of our method we prove a new result: there exists an aperiodic infinite binary word avoiding the pattern x x x^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.

preprint2014arXiv

Mechanical Proofs of Properties of the Tribonacci Word

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Tribonacci-automatic". This class includes, for example, the famous Tribonacci word T = 0102010010202 ..., the fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 0. We use it to reprove some old results about the Tribonacci word from the literature, such as assertions about the occurrences in T of squares, cubes, palindromes, and so forth. We also obtain some new results.

preprint2013arXiv

Repetition Avoidance in Circular Factors

We consider the following novel variation on a classical avoidance problem from combinatorics on words: instead of avoiding repetitions in all factors of a word, we avoid repetitions in all factors where each individual factor is considered as a "circular word", i.e., the end of the word wraps around to the beginning. We determine the best possible avoidance exponent for alphabet size 2 and 3, and provide a lower bound for larger alphabets.

preprint2013arXiv

Shortest Repetition-Free Words Accepted by Automata

We consider the following problem: given that a finite automaton $M$ of $N$ states accepts at least one $k$ -power-free (resp., overlap-free) word, what is the length of the shortest such word accepted? We give upper and lower bounds which, unfortunately, are widely separated.

preprint2012arXiv

Filtrations of Formal Languages by Arithmetic Progressions

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that the operation diag, which extracts the diagonal of words of square length arranged in a square array, preserves regularity but does not preserve context-freeness.

preprint2012arXiv

On the Number of Unbordered Factors

We illustrate a general technique for enumerating factors of k-automatic sequences by proving a conjecture on the number f(n) of unbordered factors of the Thue-Morse sequence. We show that f(n) <= n for n >= 4 and that f(n) = n infinitely often. We also give examples of automatic sequences having exactly 2 unbordered factors of every length.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.