5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 Computer Science.) $\endgroup$ – Raphael Dec 4 '14 at 11:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Franki Dec 4 '14 at 12:30
  • $\begingroup$ @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. $\endgroup$ – Franki Dec 4 '14 at 13:16
  • $\begingroup$ 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.) $\endgroup$ – Raphael Dec 4 '14 at 14:10
  • 4
    $\begingroup$ $\mathrm{DCSL}$ equals $\mathrm{DSPACE}(n)$. This makes most of the closure properties listed a straightforward exercise. $\endgroup$ – Emil Jeřábek Dec 4 '14 at 14:50
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.