On test sets for checking morphism equivalence on languages with fair distribution of letters (Q1061491): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(84)90089-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2070321272 / rank | |||
Normal rank |
Revision as of 01:59, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On test sets for checking morphism equivalence on languages with fair distribution of letters |
scientific article |
Statements
On test sets for checking morphism equivalence on languages with fair distribution of letters (English)
0 references
1984
0 references
A finite subset F of a language L is called a test set for L if it satisfies the following condition: For each two morphisms g and h, \(g(w)=h(w)\) for all w in L if and only if \(g(w)=h(w)\) for all w in F. A language L over an alphabet \(\Sigma\) has fair distribution of letters if there exists a positive constant c such that, for each subword v of any word in L, if \(| v| >c\) then every letter of \(\Sigma\) occurs in v. The authors prove that (i) every DOL language with fair distribution of letters possesses (effectively) a test set, (ii) every language L with fair distribution of letters possesses a test set relative to morphisms which have bounded balance on L. It has been recently shown that every language possesses a test set. Thus the so-called Ehrenfeucht conjecture has been settled. The reader is referred to Bulletin of the Association for Theoretical Computer Science, no. 27, October 1985.
0 references
morphism equivalence
0 references
test set
0 references
fair distribution of letters
0 references
DOL language
0 references
Ehrenfeucht conjecture
0 references