Closure properties of deterministic context-sensitive languages There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages.

However, the literature is almost mute on the subject of the closure properties of deterministic context-sensitive languages. In fact, I have spend days looking for it on the internet and in the standard reference books about formal languages and theoretical computer science and didn't find anything complete or related enough to bother using and I wasn't able to find results let alone proofs for most properties myself either.

So, let $\mathbf{DCSL}$ denote the class of deterministic context-sensitive languages, then given two arbitrary languages $L_1, L_2 \in \mathbf{DCSL}$ and a regular language $L_R$, what are its closure properties under


union, $L_1 \cup L_2 \in \mathbf{DCSL}$
intersection, $L_1 \cap L_2 \in \mathbf{DCSL}$
set difference, $L_1 \setminus L_2 \in \mathbf{DCSL}$ (or $L_1 - L_2 \in \mathbf{DCSL}$ to remove ambiguities with left quotient)
complementation, $L_1^c \in \mathbf{DCSL}$
concatenation, $L_1 L_2 \in \mathbf{DCSL}$
Kleene star, $L_1^* \in \mathbf{DCSL}$
intersection with a regular language, $L_1 \cap L_R \in \mathbf{DCSL}$ (bonus)
left/right quotient with a regular language, $L_1 / L_R \in \mathbf{DCSL}$ and $L_R \backslash L_1 \in \mathbf{DCSL}$ (bonus)
reversal (bonus)
homomorphism, maybe $\lambda$-free homomorphism (bonus)
inverse homomorphism (bonus)
substitution, maybe $\lambda$-free substitution (bonus)


These are probably not all interesting closure properties of languages, but for now, I think they are enough.

Posting only results is acceptable, but providing proofs or counterexamples is definitely preferred.

To clarify the notion of deterministic context-free language: a language $L$ is deterministically context-sensitive, if there exist a formal grammar $G$ such that $L_G = L$ and all production rules of $G$ are unambiguous and consist of either growing[1] or strictly growing[2] context-sensitive substitution patterns.

Note: There are two slightly different kinds of unambiguous context-sensitive grammar classes and probably two slightly different kinds of deterministic context-sensitive language classes as well (unless they coincide, which I highly doubt since their nondeterministic counterparts don't), namely [1] and [2]. For the questions posed above, both are relevant and may yield different answers.

Note: AFAIK A (strictly) growing grammar/language is also called a (strictly) monotonic grammar/language by some authors



This question moved over from Computer Science beta
Some  results

Unless I am very mistaken, some of these questions are not hard. But I did not yet look at all of them.

I assume that a deterministic context-sensitive language (DCSL) is
defined as one recognized by a deterministic linear bounded automaton
(DLBA). We note $n$ the size of the input string $w$. We restrict the
problem, w.l.o.g, to DLBAs that use a tape that has the size of the
input string, plus the two end markers. We also assume that acceptance
is by terminating (no transition) accepting state, and rejection is by
terminating non-accepting state or non-termination.

The constructions below will use multi-track finite tapes. That is
only a presentation of a single tape that is the cross-product of
several tapes, i.e. where each cell can contain a tuple of symbols,
one component of the tuple for each track.

Since the tape contain initially just the input string, a first
deterministic pass of any DLBA we build will consiste in
transforming the input tape into a multitrack tape, that will have the
initial string in one or several of its tracks.

For every DLBA $A$, there is a DLBA $A'$ that always halt and accepts the same language.

The problem here is to detect looping computation. That is done with
the pigeon-hole principle, using the fact that computation is deterministic.

A first point is to note that a DLBA has $O(nk^n)$ configuration,
where $k$ is the number of tape symbols of the DLBA, the factor $n$ is
for the head position, and the constant number of states is just a
constant factor.  Hence, using a constant $h$ large enough (usually
$k+1$, but it may not be enough for small values of $n$, though that
is just a finite number of cases), a tape track of size $n$ with an
alphabet of size $h$ is enough to count beyong the number of
configurations of $A$ for the given input.

Hence we can build a DLBA $A'$ that has three tracks, two to simulate
the original DLBA $A$, and the other to simulate the counter. The
roles of the two simulation track are to hold the tape configuration
for the first, and to memorize the head position and the associated
state for the second.

The finite control, simulates steps of the automaton $A$ one at a
time, and  increment the counter by one for each simulated transition.
If the counter overflow the tape, then the number of steps simulated
exceeds the number of possible configurations of $A$, which indicates
that $A$ went at least twice through the same configuration, hence
that it is looping for ever since computation is deterministic.

In such a case, the DLBA $A'$ stops in a rejecting state.

Otherwise, the DLBA $A'$ accepts or rejects as $A$ would have.

*So, W.l.o.g., we can now consider only DLBA that always terminate.

Complementation of (the language of) a DLBA $A$

Given a terminating DLBA accepting a language $L$, we can construct a
DLBA accepting its complement $\bar L$ by exchanging accepting and
non-accepting states.

Thus DCSLs are closed under complementation.

Intersection, union, and difference of (languages of) two DLBA $A$ and $B$.

We assume wlog that both DLBA always terminate. Hence it is easy to
build a DLBA $C$ with two track, each containing initially a copy of
the input (after the initialization pass, as indicated above). The
DLBA $C$ will first simulate $A$ until it terminates, then simulate
$B$ until it terminates. Then it can examine the terminating states of
both, and mimic any bolean function on the results, particularly and
for intersection and or for union.

This gives closure of DCSLs under union, intersection, and set difference.

Closure of DCSLs under intersection with regular set is just a special case, as
any DFA is a DLBA.

Concatenation of (languages of) two DLBA $A$ and $B$.

It is easy to check whether a string $w$ is accepted as the
concatenation of two strings $u\in\mathcal L(A)$ and $v\in\mathcal
L(B)$. Knowing where the boundary between $u$ and $v$ is placed, a
DLBA $C$ can simulate $A$ on $u$, then $B$ on $v$ and decides on
acceptance iff both simulations accept.

The remaining difficulty is that given a string $w$, we do not know
how it should be decomposed as $w=uv$ such that $u\in\mathcal L(A)$
and $v\in\mathcal L(B)$. The solution is to try successively all
possible decompositions, until one succeeds, which is followed by an
acceptance. If none succeed, the input string $w$ is rejected.

Hence DCSLs are closed under concatenation.

Kleene star of (the language of) a DLBA A

This problem is nearly the same as concatenation. But instead of
trying all decompositions of the input string $w$ into two strings, we
have to try all possible decomposition into the concatenation of an
arbitrary number of  non-empty substrings. To do this, the simplest
way is to use a track to keep a clean copy of the input string, a
track to have a working copy on which we test a decomposition in
substring, and a third track with a $\{0,1\}$ alphabet that defines
the decomposition into substrings. To list all the possible
decompositions, we only have to use the third track as a counter from
$0$ to $2^{n-1}-1$, incrementing it by one after every unsuccesful
try, until one succeeds thus accepting the input string, or until the
counter reaches the value $2^{n-1}$ in which case the input string is
not accepted.

Thus DCSLs are closed under Kleene star

Note: Closure of DCSLs under reversal is just obvious