Absorption relation on regular sets

S. Yu. Maslov

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VII, Tome 60 (1976), pp. 65-74

Résumé

Let $R$ be a regular expression (constructed in the usual manner from the letters of an alphabet $A$ by using the operations $\cdot$, $\vee$ и $\{\}$), $R$ be the corresponding regular (recognizable by a finite automaton) set of words in $A$. For words $P$ and $Q$ from $R$ there is defined a relation $P\prec_RQ$ ($QR$-absorbs $P$) satisfying the following conditions: 1) $P\prec_RP$, $\Lambda\prec_{\{R\}}P$ ($\Lambda$ is the empty word); 2) if $P\prec_{R_1}Q$, then $P\prec_{R_1\vee R_2}Q$, $P\prec_{R_2\vee R_1}Q$, $P\prec_{\{R_1\}}Q$; 3) if $P_1\prec_{R_1}Q_1$ and $P_1\prec_{R_2}Q_2$, then $P_1P_2\prec_{R_1\cdot R_2}Q_1Q_2$; 4) if $P_1\prec_{\{R\}}Q_1$ and $P_2\prec_{\{R\}}Q_2$, then $P_1P_2\prec_{\{R\}}Q_1Q_2$. THEOREM. For any $R$ and any infinite sequence of words from $R$ there exists an infinite subsequence such that $P_1\prec_RP_2\prec_RP_3\prec_R\dots$ . Results of such kind have proved applicable to the proofs of the solvability of certain canonic calculi arising in the modelling of biological evolution.