1
$\begingroup$

Wikipedia says:

A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language.

A full trio, also called a cone, is a trio closed under arbitrary homomorphism.

A (full) semi-AFL is a (full) trio closed under union.

A (full) AFL is a (full) semi-AFL closed under concatenation and the Kleene plus.

  • I am wondering if the four concepts are required to be closed under intersection with regular language, not intersection with languages in the same family?

  • why are intersection with regular languages required, not intersection?

  • I wonder what the concepts are if changing closure under intersection with regular language, to closure under intersection with languages in the same family?

I asked these because I saw that the recursively enumerable languages, recursive languages, context-sensitive languages, regular languages are closed under intersection with languages in the same families, while context-free languages are not.

$\endgroup$
6
  • 2
    $\begingroup$ I think you pretty much answered your question already: AFLs are not necessarily closed against intersection, so you get a different family (of language classes). So what are you asking for? $\endgroup$
    – Raphael
    Commented Jun 2, 2014 at 21:04
  • $\begingroup$ (1) why are intersection with regular languages required, not intersection? (2) Are there already concepts, if changing closure under intersection with regular language, to closure under intersection with languages in the same family? $\endgroup$
    – Tim
    Commented Jun 2, 2014 at 21:05
  • 1
    $\begingroup$ ad 1) "why is a definition like this?" is almost always tough to answer; somebody needed a name for classes with these properties, period. ad 2) What do you mean by "are there already concepts"? "Can I define it?" vs "Does the concept have a name?" vs "Are there any such classes?" vs... $\endgroup$
    – Raphael
    Commented Jun 2, 2014 at 21:09
  • $\begingroup$ (1) Closure under intersection is more perfect mathematically than closure under intersection with regular languages only. Formal theory choose to study the latter, which seems odd if without knowing the reason. (2) Does the concept have a name? (3) My questions are not just for tros, but for al the four concepts. $\endgroup$
    – Tim
    Commented Jun 2, 2014 at 21:11
  • 2
    $\begingroup$ Why is one more perfect than the other? Names are given to concepts that are found to be more useful. Of course that may sometimes change with time. There are many more families of languages than appear in textbooks, that people will study for one reason or other. Closure under intersection with regular sets is nearly always the case (I do not recall an example where it is not). I guess closure under intersection within the family is not so frequent for families that have been considered interesting. You may also wonder whether it enables the proof of interesting other results. $\endgroup$
    – babou
    Commented Jun 2, 2014 at 21:29

4 Answers 4

4
$\begingroup$

Because it is a very natural set of operations: the full trio operations (morphism, inverse morphism, intersection with regular languages) exactly corresponds to closure under finite state transductions.

We can formulate results for such nice families. Requiring too many properties would exclude some families of languages. Who wants to miss the context-free languages?

Likewise the Boolean operations (intersection, union, complement) form a nice set, but we do not always require them.

The notion "intersection closed full AFL" is well studied.

$\endgroup$
2
$\begingroup$
  1. It is intersection with regular languages, as Wikipedia says (not intersection with other languages in the same family).

  2. Because. Because that's what the definition says. Changing the definition would give a different concept. For instance, context-free languages are closed under intersection with regular languages, but not under intersection with other context-free languages, as you point out. This is what the standard definition says, and it is a useful concept. Beyond that, I'm not sure what you expect from a "why" question; it's a definition, and it is what it is.

  3. I don't know if there is any standard name for such a concept.

$\endgroup$
2
$\begingroup$

Definitions are chosen, and associated with names, according to their utility in the development of the mathematical theory at hand. Sometimes they are defined very locally for a specific proof, but remain uninteresting outside that proof. Other are given a wider scope because they can be more widely useful.

There may be some aesthetics in the choice of definition, when it does reflect some deep structure of the problems, and that will contribute to usefulness. But a symmetry that is seldom encountered is probably not that useful, or indicative of deep mathematical structure.

I can only talk of my very limited experience. Closure under intersection with regular sets is almost ubiquitous for families of languges. No counter-example comes to my mind. Of course, it is always possible to contrive one, but not so easily (I guess) to contrive one that corresponds to a useful family of languages.

When you choose a definition, thus focussing you interest and your work on it, you have to ask yourself two questions:

  • How often will it apply to problems you may be interested in, and how inportant these problems are likely to be (though that may be hard to estimate)

  • How convenient is this definition is to derive general results that can be applied to whatever will fit the definition.

Trios and AFLs where defined as they have been by people who found that many families of languages met the corresponding definitions. Furthermore, from the definitions, there were able to prove a variety of results abstractedly for trios and AFLs, that can be applied without further effort to all these families.

They apparently had no incentive to do it for arbitrary intersection within the family. Hence no definition and no name, that I know of.

A further remark is that all these families include regular sets. Hence they are more likely to be closed under intersection with regular sets than under arbitrary intersection within the family (which does imply closure under intersection with regular sets). Hence the definition as chosen is more likely to be applicable, hence more generally useful. And it turn out to be already very useful by itself as remarked by Jan Hendrik.

The following is pure speculation on my part. It may also be that operations considered for closure correspond to interesting structural properties of languages. For example closure under union seems naturally associated with non-determinism (recall that deterministic context-free languages are not closed under union). It may be that there is no simple such property associated with intersection. But as I said, this is not based on hard understanding.

$\endgroup$
1
$\begingroup$

Closure under intersection with regular sets is natural in the sense that most machine models for language classes are finite-state based with some additional control mechanism, and by some standard constructions a finite automaton describing some other regular language could be coded into this finite-state mechanism to get closure under intersection. This is how most of the proofs that show this closure property work. I will give a more detailed and formal answer under some very specific framework below. But before some remarks on the boolean operations.

1) Note the curious fact that for a trio, closure under intersection is the same as closure under shuffle. The shuffle of two words is the language of all possible interleavings of two words, i.e., if $u,v \in X^*$ for some alphabet $X$, then $$ u \diamond v := \{ u_1 v_1 u_2 v_2 \cdots u_k v_k \mid k \ge 1, u_i, v_i \in X \cup \{\varepsilon\}\}. $$ For languages $U, V \subseteq X^*$ we set $U \diamond V = \bigcup_{u \in U, v \in V} u\diamond v$. We can write the shuffle with intersection and the trio operations. Let $\overline X = \{ \overline x : x \in X \}$ be some disjoint copy of $X$ and $h : (X \cup \overline X)^* \to X^*$ the homomorphism given by $h(x) = h(\overline x) = x$ and $h_1, h_2 : (X \cup \overline X)^* \to X$ two homomorphisms given by $h_1(x) = h_2(\overline x) = \varepsilon$, $h_1(\overline x) = x$ and $h_2(x) = x$. Then $$ U \diamond V = h(h_1^{-1}(U) \cap h_2^{-1}(V)). $$ This formula also gives that we always have closure under shuffle with regular languages in any trio. Conversely if a trio is closed under shuffle then $$ U \cap V = h((U \diamond \overline V) \cap (X\overline X)^*) $$ where $\overline U = \{ \overline u : u \in U \}$ is the image of U under the homomorphism given by $x \mapsto \overline x$.

2) If we allow complementation as already mentioned many interesting and natural language classes are excluded. But this could be stated more formal as was done in Georg Zetzsche's dissertation Monoids as Storage Mechanisms.

If a trio containing only recursively enumerable languages is closed under complementation, then it is precisely the class of all regular languages.

So, if we also want some meaningful way to talk about computability, there is not trio closed under complementation except the regular languages.

3) Let me make my intuitive remarks why closure under intersection with regular languages is a natural operation more precise, or represents a structural property as noted in @babou answer. As said it has to do with the fact that most machine models are finite state based with some additional control (a stack, an infinite tape, a linear bounded tape etc).

One way to make this more precise and unify these models is the notion of valence automata, which is also a central topic in the above mentioned dissertation. A valence automaton is essentially a finite automaton enriched with some ''counting mechanism/or storage mechanism'' in form of a monoid. Imagine you have some additional register that can save an element from some monoid, and you can alter it by multiplication with other monoid elements. The following monoids correspond to the following language classes.

Monoid      |  Language class
-------------------------------
B           |  Context-Free     
F_2         |  Context-Free
B x B       |  Recursively Enumerable
1           |  Regular
Z^n         |  Blind counter languages
N^n         |  Partially blind counter languages

where B denotes the bicyclic monoid, F_2 the free group of rank $2$, 1 the trivial monoid, Z the integers, and N the natural numbers, see the mentioned dissertation for more details.

By a slight modification of the product automaton construction we can show that if $U$ and $V$ are accepted by some valence automata over monoids $M$ and $N$, then $U \cap V$ is accepted by some valence automaton over $M \times N$. But if $V$ is regular, we can choose $N = 1$, the trivial monoid. Hence in this case $M \times N \cong M$, so that we have not left our language class, or said differently every language described by valence automata is closed under intersection with regular languages (and in fact they are semi AFL's).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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