Disjunctive splittability of languages
type: Item
instance of: scholarly article
title: Disjunctive splittability of languages
zbMATH Open document ID: 0648.20063
DOI: 10.1007/BF02573133
author: Masashi Katsura
published in: Semigroup Forum
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/134924
review text: Let X be a finite alphabet with more than one element. A language A is any subset of the free monoid \(X^*\) on X. The language A is said to be dense if \(A\cap X^*uX^*\neq \emptyset\) for any \(u\in X^*\). A is discrete if \(| A\cap X^ n| \leq 1\) for any \(n\geq 1\). A is locally finite of rank r if \(| A\cap uv^+w| \leq r\) for any \(u,v,w\in X^*\), where \(B^+\) denotes the subsemigroup generated by B. A is a prefix code if u,ux\(\in A\) implies \(x=1\). For a language A, \(P_ A=A\setminus AX^+\). Consider a class T of languages containing at least one dense language and closed under taking dense subsets (e.g., the class P of all prefix codes). A language is said to be DT-splittable if it is a disjoint union of dense discrete languages in T which are locally finite of rank 1. In case \(A\setminus F\) is DT-splittable for some finite language F, A is said to be semi-DT-splittable. Starting from an extension of a result of \textit{H. J. Shyr} [Inf. Control 46, 257-269 (1980; Zbl 0453.68046)], the author investigates these notions extensively. Among other results, the following are proved in the paper. 1) A language is DT-splittable if and only if it is a union of dense languages in T. 2) A language A is DP-splittable if and only if there exist \(B,C\subseteq P_ A\) such that \(A\cap BX^*\) and \(A\cap CX^*\) contain dense prefix codes. 3) For any dense languages A, B and C, ABC is semi-DP-splittable. 4) If A is a dense language with \(1\not\in A\), then \(A^ n\) is DP-splittable for some \(n\geq 1\).
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 4057814
zbMATH Keywords: finite alphabet
zbMATH Keywords: free monoid
zbMATH Keywords: dense language
zbMATH Keywords: prefix codes
zbMATH Keywords: discrete languages
zbMATH Keywords: finite language
zbMATH Keywords: semi-DP-splittable
reviewed by: Jorge Almeida
MaRDI profile type: Publication
cites work: Q3787510
cites work: The equation \(a_ M=b^ Nc^ P\) in a free group
cites work: Some properties of disjunctive languages on a free monoid
cites work: Q3886879
cites work: Q4001349
cites work: Ordered catenation and regular free disjunctive languages
cites work: A characterization of dense languages
OpenAlex ID: W2071609840
Recommended article: A characterization of dense languages
Recommended article: Q4819886
Recommended article: Classifications of dense languages
Recommended article: Q3746903
Recommended article: Disjunctive decomposition of languages
Recommended article: A characterization of s-languages
Recommended article: Q3431302
Recommended article: Free submonoids in the monoid of languages
Recommended article: Q3361897
Recommended article: Fast stabbing of boxes in high dimensions
description: scientific article; zbMATH DE number 4057814