[Solved]: Is the universe problem for one-counter automata with restricted alphabet size undecidable?

Problem Detail: 

Consider the following universe problem.

The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.

In [1], it is stated and proved that the universe problem is undecidable for a particular class of one-counter automata. This result then follows for the class of all non-deterministic one-counter automata. I'm wondering if it is known whether this problem is still undecidable when we restrict the size of the input alphabet of the automaton.

I think that with alphabet size 1 the problem becomes decidable, but what about size 2? And if that turns out to be decidable what is the smallest value of $n \in \mathbb{N}$ such that the problem is undecidable.

I think it's probable that the answer to this question is known but I'm having trouble finding an answer. If it is already known then I would appreciate a reference.

---

[1] Ibarra, O. H. (1979). Restricted one-counter machines with undecidable universe problems. Mathematical systems theory, 13(1), 181-186

Asked By : Sam Jones

Answered By : Hendrik Jan

It must be undecidable for an alphabet with two symbols. It is possible to code any alphabet into two letters, e.g., map 16 symbols to the length 4 binary strings $aaaa, aaab, \dots, bbbb$. Then equality to $\Sigma^*$ is equivalent to equality to all possible codes for strings. In the 16 letter example this means equality to all strings of a multiple of four letters. Clearly that is not universality. That is obtained by adding those binary strings that are not coding. That is a regular set and can be generated by a one counter automaton.

The same explanation, with $\LaTeX$ for those who appreciate it. Assume universality is undecidable for $\Sigma$. Let $h: \Sigma^* \to \{0,1\}^*$ be an injective morphism. Now $L = \Sigma^*$ iff $h(L) = h(\Sigma^*)$. This in turn is equivalent to $h(L) \cup R = \{0,1\}^*$ where $R$ is the (fixed) regular language $\{0,1\}^* - h(\Sigma^*)$. Hence we cannot decide whether the binary one counter language $h(L) \cup R$ is universal. Note that language is one counter as the family is closed under morphisms and union (with regular languages).

As you state "I think that" I can also confirm the question is decidable for a one letter alphabet. It is decidable for push-down automata (hence context-free languages) as one letter CFL are (effectively) equivalent to regular languages.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12233

 Ask a Question

 Download Related Notes/Documents