Code properties and homomorphisms of DOL systems (Q1058858): Difference between revisions

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.