Deciding whether a unary context-sensitive language is regular

Question

It is a well-known result that the question

Does a context-free grammar generate a regular language?

is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case, the classes of context-free and regular languages coincide.

My question is to know what happens for unary context-sensitive languages.

Is it decidable to know whether a given context-sensitive grammar on a unary alphabet generates a regular language.

If the answer is positive, an estimation of the complexity would be welcome.

Answer 1

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate that there is a unary CSL $X$ which isn't regular (in contrast to the positive result for unary CFLs), and then reduces from the halting problem for Turing machines by, given a TM $M$, constructing a CSG $G$ which simulates $M$ on a length of tape shorter than the parse string $w$, recognising $X$ if $M$ halts without overstepping its bounds and failing to parse otherwise, so that $G$ successfully parses all $w \in X$ that are sufficiently long iff $M$ halts (so that $L(G)$ differs from $X$ on only finitely many strings and therefore cannot be regular), otherwise $G$ recognizes the empty language (which is clearly regular).

Key to this approach is the observation that CSGs are not merely concerned with grammatical matters such as phrase structure -- indeed, CSG derivation sequences can carry out arbitrary nondeterministic space-bounded computation (indeed there are $\mathbf{PSPACE}$-complete CSLs) before ever getting to the business of aligning with the parse string. This is most easily observed via standard conversions between CSGs and monotonic grammars (which continues to work when restricted to unary alphabets), and the use of simple monotonic productions to simulate Turing machine transitions on derivation strings which represent stages in a computation history. Throughout this answer I'm going to assume the reader can intuit most of the details when a CSG is required to simulate a given computation. (I assume the asker is comfortable with all of this, but I'm going over it for completeness. Nevertheless, feel free to request clarification in the comments.)

---

Firstly, we need our non-regular unary CSG. (EDIT: so, this was overkill -- non-regular unary CSLs can easily be exhibited e.g. via the pumping lemma on any language which exhibits the most basic of non-regularity. See the comments for examples. In hindsight, using a diagonal argument was like bringing a nuclear warhead to a knife fight. Peruse this construction if you're curious, otherwise skip to the reduction.)

Let $D_1, D_2, ... $ be an enumeration of DFAs over alphabet $\{1\}$, such that the number of states in $D_i$ increases in $i$. We describe a CSG $G_X$ in terms of its behaviour whilst parsing string $1^n \in \{1\}^*$:

1. Nondeterministically generate a string of $n$ "blank" non-terminals, which we think of as the "tape". One of the blank non-terminals should be a separate "blank + read-write head + start state" non-terminal. If the parse string isn't $1^n$ then this derivation will end up failing. We describe the rest of the process in terms of the deterministic computation simulated by the only possible derivation.
2. Print on the tape an encoding of $D_i$ followed by the number $i$ in binary, where $i = n - c$ and $c$ is chosen so that we always have enough space on our tape to do what we need to. (This is possible since the space required to encode both $D_i$ and $i$ grows logarithmically in $i$.)
3. Evaluate $D_i$ on input $1^i$. This doesn't require a representing $D_i$'s tape -- you can just store a single state, which you change according to the transitions of $D_i$ as you decrement $i$.
4. If $D_i$ rejects $1^i$, overwrite the entire tape with non-terminals which produce $1$. Otherwise fail.

We take $X = L(G_X)$. Clearly $X \ne L(D_i)$ for any $i$, since $1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$.

---

The next step is to design a reduction from the halting problem to the asker's problem. (If you skipped the above section, let $X$ be an arbitrary non-regular unary CSL generated by CSG $G_X$.)

Let $M$ be an arbitrary TM. We convert $M$ into a CSG $G$ which behaves as follows on parse string $1^n$:

1. Generate $n-2$ blank non-terminals, the leftmost one being the separate blank + read-write head non-terminal, and also generate a "boundary" non-terminal on each side. Again, if we generate the wrong number of non-terminals then we fail.
2. Simulate $M$ in the space between the boundary non-terminals. If $M$ ever shifts onto one of the boundary states, we terminate the simulation and assume that $M$ never halts.
3. If $M$ halts, behave like $G_X$. If we had to terminate the simulation, then fail.

Note that if $M$ manages to run forever within the boundaries then $G$ can never generate a parse string and so will fail. If $M$ halts, then there is some amount of space $n$ which suffices to contain $M$'s entire computation, hence $G$ parses $1^m$ whenever $m \ge n+2$ and $1^m \in X$, and hence $X$ is the union of $L(G)$ and a finite language, whence $L(G)$ is not regular. On the other hand, if $M$ never halts, then $L(G) = \varnothing$ is clearly regular.

An algorithm for deciding whether $L(G)$ is regular or not would determine whether or not $M$ halts on a blank tape, which is undecidable. It follows that the asker's problem is undecidable.

Answer 2

This is essentially the same answer as above, but since a "more expedient" answer is sought, I'm mentioning this: (Also, this is my first post here, so forgive me if I'm posting a triviality!)

Observe that emptiness is undecidable for unary context-sensitive languages. Fix a context-sensitive, but non-regular language $N\subseteq a^*$. Given an LBA for $L\subseteq a^*$, one can easily construct an LBA for $L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$. Then clearly $L'$ is regular if and only if $L$ is empty.

Update: Of course, the same argument shows that undecidability already holds for deterministic logarithmic space.