<h2>Some  results</h2>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>In such a case, the DLBA $A'$ stops in a rejecting state.</p>

<p>Otherwise, the DLBA $A'$ accepts or rejects as $A$ would have.</p>

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

<h2>Complementation of (the language of) a DLBA $A$</h2>

<p>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.</p>

<p><strong>Thus DCSLs are closed under complementation.</strong></p>

<h2>Intersection, union, and difference of (languages of) two DLBA $A$ and $B$.</h2>

<p>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 <em>and</em>
for intersection and <em>or</em> for union.</p>

<p><strong>This gives closure of DCSLs under union, intersection, and set difference</strong>.</p>

<p><strong>Closure of DCSLs under intersection with regular set is just a special case</strong>, as
any DFA is a DLBA.</p>

<h2>Concatenation of (languages of) two DLBA $A$ and $B$.</h2>

<p>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.</p>

<p>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.</p>

<p>Hence <strong>DCSLs are closed under concatenation.</strong></p>

<h2>Kleene star of (the language of) a DLBA A</h2>

<p>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.</p>

<p>Thus <strong>DCSLs are closed under Kleene star</strong></p>

<p>Note: <strong>Closure of DCSLs under reversal</strong> is just obvious</p>

CC BY-SA 3.0
2014-12-04T13:31:39.600Z
2014-12-04T18:39:31.273Z
2014-12-04T18:39:31.273Z
babou
<p>There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages.</p>

<p>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.</p>

<p>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</p>

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

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

<p>Posting only results is acceptable, but providing proofs or counterexamples is definitely preferred.</p>

<p>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.</p>

<p>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.</p>

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

<hr>

<p>This question moved over from Computer Science beta</p>

CC BY-SA 3.0
2014-12-04T11:37:40.550Z
You pose more than 12 questions in one post; that's bad style. Break up your research into manageable bits and include what you know. (Btw, this is obviously ontopic on [cs.SE].)
Raphael
CC BY-SA 3.0
2014-12-04T12:30:01.473Z
If I split up this question into 12 parts, is there a way to ensure that each question is visible from any of the other 11 ones, since they are all closely related?
Franki
CC BY-SA 3.0
2014-12-04T13:16:02.310Z
@Raphael I can't use tags yet to do that. Would using links be alright? I really don't want to lose sight of any of the 12 questions then.
Franki
CC BY-SA 3.0
2014-12-04T14:10:59.687Z
For yourself, you can keep a list of links anywhere. Using some more tags would certainly help, but you'd have to ask regulars/mods of this site to propose a good tagging. (Also, note that some items are redundant.)
Raphael
CC BY-SA 3.0
2014-12-04T14:50:34.507Z
$\mathrm{DCSL}$ equals $\mathrm{DSPACE}(n)$. This makes most of the closure properties listed a straightforward exercise.
Emil Jeřábek
CC BY-SA 3.0
2014-12-04T19:51:19.683Z
@EmilJeřábek Of course. But since I never had to work with complexity
classes, I would not think of making that remark, so I answered for
fun. I just did some of the proofs, which are pretty easy (for
research level :-). I am not sure the rest is as easy, but I am not
the best expert. These constructions would probably be more useful to
users of the CS site.
babou
CC BY-SA 3.0
2014-12-07T22:27:46.757Z
CSL,the class of context-senstive languages, forms an abstract family of languages (AFL).  The question whether CSL=DCSL is a famous open problem. Suppose DCSL is not closed under one of the AFL operations - then finding a proof for this will be challenging, because that would separate the two language classes. (Beware: Maybe it can be easily shown that DCSL is an AFL as well, I haven't tried.)
Hermann Gruber
<cc.complexity-theory><fl.formal-languages><automata-theory><space-bounded>
Closure properties of deterministic context-sensitive languages
Franki
# Closure properties of deterministic context-sensitive languages

(Asked by: username_0 on 2014-12-04)

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

1. union, $L\_1 \cup L\_2 \in \mathbf{DCSL}$
2. intersection, $L\_1 \cap L\_2 \in \mathbf{DCSL}$
3. set difference, $L\_1 \setminus L\_2 \in \mathbf{DCSL}$ (or $L\_1 - L\_2 \in \mathbf{DCSL}$ to remove ambiguities with left quotient)
4. complementation, $L\_1^c \in \mathbf{DCSL}$
5. concatenation, $L\_1 L\_2 \in \mathbf{DCSL}$
6. Kleene star, $L\_1^\* \in \mathbf{DCSL}$
7. intersection with a regular language, $L\_1 \cap L\_R \in \mathbf{DCSL}$ (bonus)
8. left/right quotient with a regular language, $L\_1 / L\_R \in \mathbf{DCSL}$ and $L\_R \backslash L\_1 \in \mathbf{DCSL}$ (bonus)
9. reversal (bonus)
10. homomorphism, maybe $\lambda$-free homomorphism (bonus)
11. inverse homomorphism (bonus)
12. 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

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, space-bounded
> **Comments:**
> **username_1**: You pose more than 12 questions in one post; that's bad style. Break up your research into manageable bits and include what you know. (Btw, this is obviously ontopic on [cs.SE].)  
> **username_0**: If I split up this question into 12 parts, is there a way to ensure that each question is visible from any of the other 11 ones, since they are all closely related?  
> **username_0**: @Raphael I can't use tags yet to do that. Would using links be alright? I really don't want to lose sight of any of the 12 questions then.  
> **username_1**: For yourself, you can keep a list of links anywhere. Using some more tags would certainly help, but you'd have to ask regulars/mods of this site to propose a good tagging. (Also, note that some items are redundant.)  
> **username_2**: $\mathrm{DCSL}$ equals $\mathrm{DSPACE}(n)$. This makes most of the closure properties listed a straightforward exercise.  
> **username_3**: @EmilJeřábek Of course. But since I never had to work with complexity classes, I would not think of making that remark, so I answered for fun. I just did some of the proofs, which are pretty easy (for research level :-). I am not sure the rest is as easy, but I am not the best expert. These constructions would probably be more useful to users of the CS site.  
> **username_4**: CSL,the class of context-senstive languages, forms an abstract family of languages (AFL).  The question whether CSL=DCSL is a famous open problem. Suppose DCSL is not closed under one of the AFL operations - then finding a proof for this will be challenging, because that would separate the two language classes. (Beware: Maybe it can be easily shown that DCSL is an AFL as well, I haven't tried.)  

---

## 1 answers

### Answer by username_3 on 2014-12-04. Score: 4

## 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


---

