|
Zapiski Nauchnykh Seminarov LOMI, 1976, Volume 60, Pages 65–74
(Mi znsl2071)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Citation:
S. Yu. Maslov, “Absorption relation on regular sets”, Studies in constructive mathematics and mathematical logic. Part VII, Zap. Nauchn. Sem. LOMI, 60, "Nauka", Leningrad. Otdel., Leningrad, 1976, 65–74; J. Soviet Math., 14:5 (1980), 1468–1475
Linking options:
https://www.mathnet.ru/eng/znsl2071 https://www.mathnet.ru/eng/znsl/v60/p65
|
|