TR-IT-0267

TR-IT-0267 :July 1998

Yves Lepage

On Some Properties of Languages of Analogical Strings

Abstract:We show how to define some formal languages using analogy between strings of characters. We prove that any language of analogical strings has the bounded growth property, a property relevant to the modelling of natural languages. In addition, {

a^{n} / n \geq 1

}, {

a^{n} b^{n} / n \geq 1

}, and {

a^{n} b^{n} c^{n} / n \geq 1

} are shown to be languages of analogical strings, each capable of being analyzed with a similar asymptotic behavior. Moreover, the crucial formal language {

a^{n} b^{m} c^{n} d^{m} / n \geq 1 \land m \geq 1

} is shown to be a simple language of analogical strings.
Keywords:Analogy, languages, bounded growth, formal languages hierarchy.