Code properties and homomorphisms of DOL systems (Q1058858)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Code properties and homomorphisms of DOL systems |
scientific article |
Statements
Code properties and homomorphisms of DOL systems (English)
0 references
1985
0 references
The starting point of the paper is that each infinite polynomially bounded DOL language is either a prefix code or a suffix code. The authors consider also two special classes of biprefix codes called infix and outfix codes and investigate in detail the connection between code properties and structural properties of polynomially bounded DOL languages. Some of the central results are: the code properties of the languages denoted by the derivative D' of a DOL system (introduced here) must hold for the language generated by D; if L is the language generated by a linearly bounded DOL system D, then either L has extremely strong code properties or L has extremely restricted structural properties; every DOL language is the union of a commutative equivalent of a, possibly empty, prefix code. The article is closed with a discussion of several unanswered decidability question concerning code properties of DOL languages.
0 references
prefix code
0 references
suffix code
0 references
biprefix codes
0 references
polynomially bounded DOL languages
0 references
DOL system
0 references