Disjunctive languages and compatible orders. (English) Zbl 0674.20040

Let X be an alphabet, \(2\leq | X| <\aleph_ 0\), and let \(L\subseteq X^*\). For \(u\in X^*\) let \(L..u=\{(\alpha,\beta)|\) \(\alpha,\beta \in X^*\), \(\alpha\) \(u\beta\in L\}\) be the set of contexts of u with respect to L. The language L is said to be disjunctive if the principal congruence defined by L is the equality, that is, if \(L..u=L..v\) implies \(u=v\). The authors introduce the following classification of disjunctive languages: L is s-disjunctive if L..u\(\subseteq L..v\) implies \(u=v\); it is m-disjunctive if it is disjunctive, but not s-disjunctive. Several properties of s-disjunctive and m-disjunctive languages are proved.
Reviewer: H.Jürgensen


20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
68Q45 Formal languages and automata
94B60 Other types of codes
Full Text: DOI EuDML


[1] 1. J. BERSTEL and D. PERRIN, Theory of Codes, Academic Press, Orlando, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[2] 2. M. ITO, H. JURGENSEN, H. J. SHYR and G. THIERRIN, Anti-commutative Languages and n-codes (to appear in Applied Discrete Mathematics). Zbl0679.68140 MR1011274 · Zbl 0679.68140
[3] 3. H. JURGENSEN, H. J. SHYR and G. THIERRIN, Codes and compatible partial orders on free monoids, Proceedings of the First International Symposium on OrderedAlgebraic Structures, Marseille 1984, Research and Exposition in Mathematics, Vol. 14, Helolermann Verlag Berlin, 1986. Zbl0611.06012 MR891474 · Zbl 0611.06012
[4] 4. G. LALLEMENT, Semigroups and Combinatorial Applications, John Wiley, NewYork, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[5] 5. M. LOTHAIRE, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
[6] 6. R. C LYNDON and M. P. SCHÜTZENBERGER, The equation aM=bN cP in a free groupe, Mich. J., Vol. 9, 1962, pp. 289-298. Zbl0106.02204 MR162838 · Zbl 0106.02204
[7] 7. C. M. REIS and H. J. SHYR, Some Properties of Disjunctive Languages on a Free Monoid, Information and Control, Vol. 34, 1978, pp. 334-344. Zbl0376.68044 MR497023 · Zbl 0376.68044
[8] 8. H. J. SHYR, Free Monoids and Languages, Lecture Notes, Dept. Math., Soochow Univ., Taiwan, 1979. Zbl0746.20050 MR1090325 · Zbl 0746.20050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.