RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1976 Volume 60, Pages 65–74 (Mi znsl2071)

This article is cited in 1 paper

Absorption relation on regular sets

S. Yu. Maslov


Abstract: 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.

UDC: 51.01:164


 English version:
Journal of Soviet Mathematics, 1980, 14:5, 1468–1475

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024