Metric properties of functions defined by partial automata
We characterize natural categories in which morphisms are defined by partial automata of the following three types: asynchronous automata, window automata, and automata synchronous over finite alphabets. We distinguish subcategories whose morphisms are defined by finite automata.
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , , , , |
| Format: | Article |
| Language: | Russian English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2010
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/2974 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508981229780992 |
|---|---|
| author | Nekrashevich, V. V. Oliinyk, A. S. Sushchanskii, V. I. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. |
| author_facet | Nekrashevich, V. V. Oliinyk, A. S. Sushchanskii, V. I. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. |
| author_sort | Nekrashevich, V. V. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:41:38Z |
| description | We characterize natural categories in which morphisms are defined by partial automata of the following three types: asynchronous automata, window automata, and automata synchronous over finite alphabets. We distinguish subcategories whose morphisms are defined by finite automata. |
| first_indexed | 2026-03-24T02:33:50Z |
| format | Article |
| fulltext |
UDK 512.58, 515.124
V. V. Nekraßevyç (Texas. A&M un-t, SÍA),
A. S. Olyjn¥k (Kyev. nac. un-t ym. T. Íevçenko),
V. Y. Suwanskyj (Sylez. texn. un-t, Pol\ßa)
METRYÇESKYE SVOJSTVA FUNKCYJ,
OPREDELQEMÁX ÇASTYÇNÁMY AVTOMATAMY
We characterize natural categories in which morphisms are defined by partial automata of the following
three types: the asynchronous automata, the window automata, and the automata synchronous over finite
alphabets. We distinguish subcategories whose morphisms are defined by finite automata.
Oxarakteryzovano pryrodni katehori], morfizmy v qkyx vyznaçagt\sq çastkovymy avtomatamy
tr\ox typiv: asynxronnymy, vikonnymy i synxronnymy nad skinçennymy alfavitamy. Vydileno
pidkatehori], morfizmy qkyx vyznaçeni skinçennymy avtomatamy.
1. Vvedenye. Avtomat¥-preobrazovately razlyçn¥x typov okazalys\ udobn¥m
sredstvom dlq zadanyq otobraΩenyj ul\trametryçeskyx prostranstv, homeo-
morfn¥x kantorovskomu dyskontynuumu. UΩe sravnytel\no nebol\ßye po
çyslu sostoqnyj avtomat¥ mohut opredelqt\ otobraΩenyq s ynteresn¥my
svojstvamy, çto udobno pry postroenyy razlyçn¥x prymerov [1]. Takye avtoma-
t¥ moΩno yspol\zovat\ dlq postroenyq y analyza dynamyçeskyx system, opre-
delenn¥x na vpolne nesvqzn¥x kompaktax (sm., naprymer, [2, 3]), y dynamyçe-
skyx system s dyskretn¥m vremenem [4]. Krome toho, avtomatn¥e
preobrazovanyq (sluçaj, kohda vxodnoj y v¥xodnoj alfavyt¥ sovpadagt)
otnosytel\no operacyy superpozycyy obrazugt poluhruppu, kotoraq soderΩyt
mnoho hrupp y poluhrupp s razlyçn¥my πkstremal\n¥my svojstvamy,
prymenqgwyxsq v razlyçn¥x razdelax sovremennoj alhebr¥, symvol\noj
dynamyky, teoryy C∗ -alhebr (sm. [5, 6]).
Analyz katehoryj otobraΩenyj, opredelenn¥x osnovn¥my typamy avtoma-
tov-preobrazovatelej, do nastoqweho vremeny ne provodylsq, xotq yz obzora [5]
y rabot¥ [7] sleduet, çto voznykagwye zdes\ katehoryy tesno svqzan¥ s kateho-
ryej, obæektamy kotoroj qvlqgtsq ul\trametryçeskye prostranstva, a mor-
fyzmamy — yx neprer¥vn¥e otobraΩenyq. V nastoqwej rabote m¥ pop¥taemsq
vospolnyt\ ukazann¥j probel. Budem rassmatryvat\ try typa avtomatov-preob-
razovatelej: asynxronn¥e, okonn¥e y synxronn¥e, kotor¥m sootvetstvugt try
typa otobraΩenyj ul\trametryçeskyx prostranstv — neprer¥vn¥e, lypßyce-
v¥e y neuvelyçyvagwye rasstoqnye.
KaΩd¥j çastyçn¥j asynxronn¥j avtomat (t.=e. avtomat, funkcyy perexodov
y v¥xodov kotoroho mohut b¥t\ ne vezde opredelen¥) ymeet vpolne zadann¥e ob-
last\ opredelenyq y oblast\ znaçenyj, kotor¥e qvlqgtsq zamknut¥my podmno-
Ωestvamy v prostranstvax beskoneçn¥x slov, preobrazov¥vaem¥x πtym avto-
matom. Poπtomu katehoryq, opredelqemaq avtomatamy, stroytsq sledugwym
obrazom: ee obæektamy qvlqgtsq zamknut¥e podmnoΩestva beskoneçn¥x slov
nad razlyçn¥my koneçn¥my alfavytamy, a morfyzmamy — opredelqem¥e avto-
matamy otobraΩenyq. Xarakteryzacyq πtoj katehoryy y ee podkatehoryj, soot-
vetstvugwyx okonn¥m y synxronn¥m avtomatam, y qvlqetsq osnovnoj cel\g
dannoj rabot¥. Opyßem kratko ee stroenye.
V p. 2 pryveden¥ svedenyq, neobxodym¥e dlq rabot¥ s avtomatn¥my preobra-
zovanyqmy: metryçeskoe prostranstvo ω-slov, asynxronn¥e, okonn¥e y syn-
xronn¥e avtomat¥, avtomatn¥e otobraΩenyq, ravnosyl\n¥e avtomat¥, operacyq
superpozycyy avtomatov y otobraΩenyj, ymy opredelqem¥x. V p. 3 sformuly-
rovan¥ osnovn¥e utverΩdenyq o svojstvax avtomatn¥x otobraΩenyj (teore-
m¥=1, 2), koneçnoavtomatn¥x otobraΩenyj (teorem¥ 4, 5), a takΩe predstavlena
© V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ, 2010
1500 ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
METRYÇESKYE SVOJSTVA FUNKCYJ, OPREDELQEMÁX … 1501
xarakteryzacyq katehoryj avtomatn¥x otobraΩenyj v topolohyçeskyx termy-
nax (teorema 3). V p. 4 pryveden¥ dokazatel\stva ukazann¥x teorem y obsuΩ-
dagtsq hranyc¥ yx prymenymosty.
Vse oboznaçenyq v rabote obweprynqt¥e. Opredelenyq neopredelqem¥x v
stat\e ponqtyj teoryy avtomatov sm. v [8].
2. Prostranstvo ωωωω-slov. Dejstvye avtomatov na ωωωω-slovax. 2.1. Pust\
X — koneçn¥j alfavyt, X = n, X∗ — mnoΩestvo slov nad alfavytom X
(vklgçaq pustoe slovo ∅). Dlynu slova u ∈ ∗X (çyslo sostavlqgwyx slovo
bukv) budem oboznaçat\ symvolom u . Kak ob¥çno, konkatenacyej slov u =
= x x1 2 … xk , v = y y yk1 2 … ∈ X∗ naz¥vaetsq slovo uv = x x1 2 … x y yk 1 2 …
… yl . Slovo u naz¥vaetsq podslovom slova v, esly suwestvugt slova w1 ,
w2 takye, çto v = w uw1 2 . Esly pry πtom w1 = ∅, to slovo u naz¥vaetsq pre-
fyksom yly naçalom slova v, a esly w2 = ∅, to hovorym, çto u — okonçanye
slova v . Symvolom Xm
budem oboznaçat\ mnoΩestvo vsex slov dlyn¥ m (v
çastnosty, X0 = ∅{ } ). Takym obrazom,
X X∗
=
∞
= m
m 0
∪ .
Beskoneçn¥my (vpravo) slovamy yly, kratko, ω-slovamy nad alfavytom X
budem naz¥vat\ beskoneçn¥e posledovatel\nosty symvolov alfavyta X; ω-slo-
va moΩno stroyt\ v vyde konkatenacyy beskoneçnoho çysla koneçn¥x slov.
Konkatenacyq
w w w wi
i=
∞
∏ = …
1
1 2 3
budet beskoneçn¥m slovom v tom y tol\ko v tom sluçae, kohda çyslo nepust¥x
mnoΩytelej wi , i ∈N , beskoneçno. MnoΩestvo vsex ω-slov nad alfavytom X
oboznaçym çerez Xω . Dlq ω-slov opredelqgtsq takΩe ponqtyq prefyksa y
okonçanyq. A ymenno, slovo u ∈ ∗X budet prefyksom ω-slova v, esly su-
westvuet takoe ω-slovo w, çto ymeet mesto ravenstvo v = u w; ω-slovo w v
πtom sluçae naz¥vaetsq okonçanyem slova v.
PoloΩym X∞ = X X∗ ∪ ω
. Dlq lgb¥x u, v ∈ ∞X symvolom κ( , )u v obo-
znaçym dlynu obweho naçala u, v. Opredelym funkcyg
d X X: ∞ ∞ +× → { }R ∪ 0 ,
poloΩyv dlq lgboj par¥ ( , )u v ∈ X X∞ ∞×
d u( , )v =
0
2
, ,
, .( , )
esly
esly
u
uu
=
≠
−
v
vvκ
Neposredstvenno proverqetsq, çto d qvlqetsq ul\trametrykoj na mnoΩest-
ve= X∞ .
Dlq lgb¥x podmnoΩestv K ⊂ ∗X , L ⊂ Xω symvolom K L oboznaçym mno-
Ωestvo u uv{ ∈ K, v ∈ }L . KaΩd¥j ßar v prostranstve Xω ymeet vyd Du =
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
1502 V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ
= u{ }Xω dlq nekotoroho slova u ∈ ∗X . Otsgda neposredstvenno sleduet ta-
kaq lemma.
Lemma 1. Lgboe otkr¥toe podmnoΩestvo v prostranstve Xω sovpada-
et s mnoΩestvom vyda LXω pry nekotorom L ⊂ Xω .
Zam¥kanyq podmnoΩestv yz Xω mohut b¥t\ oxarakteryzovan¥ sledugwym
obrazom.
Lemma 2. Pust\ A ⊂ Xω — nekotoroe podmnoΩestvo. ω-Slovo w ⊂ Xω
prynadleΩyt zam¥kanyg A mnoΩestva A v tom y tol\ko v tom sluçae,
kohda kaΩd¥j prefyks ω -slova w qvlqetsq prefyksom nekotoroho slova
yz==A .
Dokaz¥vaetsq lemma neposredstvennoj proverkoj.
Otsgda dlq podprostranstva Xω poluçaem takug lemmu.
Lemma 3. Podprostranstvo Xω metryçeskoho prostranstva ( , )X∞ d
qvlqetsq odnorodn¥m vpolne nesvqzn¥m poln¥m kompaktom dyametra 1.
2.2. Budem rassmatryvat\ funkcyy, opredelqem¥e çastyçn¥my avtomatamy
odnoho yz trex typov:
1) asynxronn¥my;
2) okonn¥my (ynaçe, odnomern¥my kletoçn¥my);
3) synxronn¥my (ynaçe, avtomatamy Myly).
KaΩd¥j avtomat typa 1 – 3 zadaetsq pqterkoj dann¥x vyda
A = X Y, , , ,Q ϕ ψ ,
hde X — vxodnoj, a Y — v¥xodnoj alfavyt¥ avtomata A, X , Y < ∞; Q —
mnoΩestvo vnutrennyx sostoqnyj A; ϕ — voobwe hovorq, çastyçno opredelen-
naq funkcyq yz Q × X v Q, naz¥vaemaq funkcyej perexodov A.
Funkcyq ψ, kotoraq naz¥vaetsq funkcyej v¥xodov, v kaΩdom yz sluça-
em=1=– 3 opredelqetsq po-raznomu. A ymenno, ψ qvlqetsq, voobwe hovorq, ças-
tyçnoj funkcyej
i) yz mnoΩestva Q × X v mnoΩestvo Y∗ slov nad v¥xodn¥m alfavytom Y
v sluçae, kohda A — asynxronn¥j avtomat;
ii) yz mnoΩestva Q × Xn
( n ∈N fyksyrovano y zavysyt tol\ko ot avtomata
A) v Y dlq okonn¥x avtomatov;
iii) yz mnoΩestva Q × X v mnoΩestvo Y dlq synxronn¥x avtomatov.
Udobn¥m sposobom opysanyq (asynxronn¥x avtomatov) qvlqgtsq specyal\-
noho vyda hraf¥, naz¥vaem¥e dyahrammamy Mura. MnoΩestvo verßyn dyah-
ramm¥ Mura avtomata A sovpadaet s mnoΩestvom eho sostoqnyj. Verßyn¥ q1 ,
q2 soedynen¥ strelkoj v napravlenyy ot q1 k q2 , esly suwestvuet bukva
x ∈X takaq, çto ϕ( , )q x1 = q2 . Dannaq strelka snabΩaetsq metkoj x( ,
ψ( , )q x1 ) .
Dalee, symvolom Dom f budem oboznaçat\ oblast\ opredelenyq funkcyy f,
a symvolom Im f — ee oblast\ znaçenyj. Esly A — okonn¥j avtomat y
Dom ψ � Q × Xn
, to çyslo n naz¥vaetsq ßyrynoj okna avtomata A. Avtomat
A = X Y, , , ,Q ϕ ψ naz¥vaetsq vsgdu opredelenn¥m, esly funkcyy ϕ, ψ vez-
de opredelen¥; v protyvnom sluçae hovorqt, çto A — çastyçn¥j avtomat. Av-
tomat A naz¥vaetsq koneçn¥m, esly koneçn¥m qvlqetsq mnoΩestvo eho vnut-
rennyx sostoqnyj; v protyvnom sluçae hovorqt, çto A — beskoneçn¥j avtomat.
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
METRYÇESKYE SVOJSTVA FUNKCYJ, OPREDELQEMÁX … 1503
KaΩd¥j yz avtomatov typa 1 – 3 pererabat¥vaet cepoçky vxodn¥x symvolov
(nad alfavytom X) v cepoçky v¥xodn¥x symvolov (nad alfavytom Y), naçynaq
rabotu v nekotorom sostoqnyy q0 . Za odyn takt rabot¥ on obrabat¥vaet odyn
vxodnoj symvol (avtomat¥ typov 1 y 3) yly vxodnoe slovo dlyn¥ n (avtomat¥
typa 2), yzmenqet vnutrennee sostoqnye y v¥daet na v¥xode lybo odyn symvol
(avtomat¥ typov 2 y 3), lybo nekotoroe, vozmoΩno pustoe, slovo (avtomat¥ typa
1). V processe rabot¥ asynxronn¥j avtomat pererabat¥vaet vxodnoe slovo yly
ω-slovo pobukvenno, v kaΩdom takte v¥davaq na v¥xode nekotoroe slovo v
v¥xodnom alfavyte; pry πtom vsemu vxodnomu slovu yly ω-slovu sopostavlq-
etsq konkatenacyq tak poluçenn¥x v¥xodn¥x slov. Poskol\ku v¥xodnoe slovo,
postroennoe za odyn takt rabot¥ asynxronnoho avtomata, moΩet b¥t\ pust¥m,
ω-slova mohut pererabat¥vat\sq asynxronn¥my avtomatamy v slova koneçnoj
dlyn¥. Synxronn¥j avtomat pererabat¥vaet slova, sopostavlqq kaΩdomu
vxodnomu symvolu odyn v¥xodnoj. Poπtomu takye avtomat¥ pererabat¥vagt
slova, ne yzmenqq yx dlyn¥, a obrazamy ω-slov vsehda budut ω-slova. Okon-
n¥j avtomat, naxodqs\ v nekotorom vnutrennem sostoqnyy, prosmatryvaet srazu
n-bukvennoe slovo na vxode y sopostavlqet emu nekotor¥j symvol v¥xodnoho
alfavyta; potom on sdvyhaetsq na odyn symvol vpravo, prosmatryvaet nov¥e n
symvolov y t.=d. V rezul\tate vxodnoe slovo dlyn¥ m ≥ n on pererabat¥vaet v
v¥xodnoe slovo dlyn¥ m – n, a vxodnoe ω-slovo — v v¥xodnoe ω-slovo.
2.3. Formal\noe opredelenye dejstvyq avtomatov na slova y ω-slova sle-
dugwee. Snaçala funkcyq perexodov y funkcyq v¥xodov avtomata A ras-
prostranqgtsq na mnoΩestvo Q × ∗X . Dlq synxronn¥x y asynxronn¥x avtoma-
tov πto osuwestvlqetsq s pomow\g sledugwyx rekurrentn¥x sootnoßenyj:
ϕ( , )q q∅ = , ϕ q ux,( ) = ϕ ϕ( , ),q u x( ) , (1)
ψ( , )q ∅ = ∅ , ψ q ux,( ) = ψ ϕ( , ),q u x( ) , (2)
hde u ∈ ∗X , x ∈X . Pry πtom esly znaçenye funkcyj ϕ y ψ na kakom-to na-
çale slova ne opredeleno, to ono ne opredeleno y dlq vseho slova. V rezul\tate
poluçaem funkcyy, opredelenn¥e na nekotor¥x podmnoΩestvax mnoΩestva
Q × ∗X . Dlq okonn¥x avtomatov funkcyq perexodov ϕ rasprostranqetsq na
nekotoroe podmnoΩestvo mnoΩestva Q × ∗X sohlasno sootnoßenyqm (1), a
znaçenyq funkcyy v¥xodov ψ opredelqgtsq, v zavysymosty ot ßyryn¥ n okna
avtomata, ravenstvamy
ψ( , )q u = ∅ , esly u n< ; ϕ q uu, 1( ) = ψ ϕ( , ),q u u1( ) , (3)
hde u, u1 ∈ ∗X y u1 = n. Teper\ obraz slova yly ω-slova u = x x x1 2 3 … nad
alfavytom X pry dejstvyy na neho avtomatom A, naxodqwymsq v sostoqnyy
q0 , opredelqetsq kak slovo yly ω-slovo ′u = y y y1 2 3 … nad alfavytom Y
takoe, çto dlq kaΩdoho natural\noho i
y q x x xi i= …( )ψ 0 1 2, (4)
v sluçae synxronnoho yly asynxronnoho avtomata y
y q x x xi i n= …( )+ −ψ 0 1 2 1, (5)
v sluçae okonnoho avtomata s ßyrynoj okna n. Obraz slova u ne opredelen,
esly xotq b¥ odna yz funkcyj ϕ, ψ ne opredelena na odnom yz prefyksov slo-
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
1504 V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ
va u. Tem sam¥m kaΩd¥j çastyçn¥j avtomat A odnoho yz opysann¥x typov,
naxodqs\ v naçal\nom sostoqnyy q0 , opredelqet dve funkcyy f qA, 0
y f qA, 0
�
takye, çto Dom Af q, 0
� Xω , Im Af q, 0
� Yω y Dom Af q, 0
� � X∗ , Im Af q, 0
� �
� Y∗ .
Opredelenye 1. Çastyçnug funkcyg f qA, 0
(sootvetstvenno f qA, 0
�
) bu-
dem naz¥vat\ funkcyej, zadavaemoj avtomatom A v sostoqnyy q0 na mno-
Ωestve ω-slov Xω (sootvetstvenno na mnoΩestve slov X∗ ).
∏to opredelenye pozvolqet vvesty v rassmotrenye klass avtomatn¥x funk-
cyj nad dann¥m alfavytom.
Opredelenye 2. Funkcyg f : D → Yω , D � Xω , yly f̂ : D̂ → Y∗ , D̂ �
� X∗ , budem naz¥vat\ (asynxronno, okonno, synxronno) avtomatnoj funk-
cyej nad alfavytamy X y Y , esly suwestvugt çastyçn¥j (asynxronn¥j,
okonn¥j, synxronn¥j) avtomat A y sostoqnye q0 πtoho avtomata takye,
çto Dom Af q, 0
= D, Dom Af q, 0
� = D̂ y f = f qA, 0
yly f̂ = f qA, 0
�
.
Razlyçn¥e çastyçn¥e avtomat¥ s v¥delenn¥my sostoqnyqmy (takye avtoma-
t¥ takΩe naz¥vagt ynycyal\n¥my) mohut opredelqt\ odnu y tu Ωe funkcyg
nad mnoΩestvamy slov yly ω-slov.
Opredelenye 3. Çastyçn¥e avtomat¥ A , B s v¥delenn¥my sostoqnyqmy
q1 y q2 naz¥vagtsq ravnosyl\n¥my, esly opredelqem¥e ymy funkcyy f qA, 1
�
,
f qB, 2
�
sovpadagt. Ony naz¥vagtsq ω -ravnosyl\n¥my, esly sovpadagt opre-
delqem¥e ymy funkcyy f qA, 1
, f qB, 2
.
Yz ravnosyl\nosty çastyçn¥x avtomatov s v¥delenn¥my sostoqnyqmy sle-
duet yx ω-ravnosyl\nost\. Obratnoe verno tol\ko dlq synxronn¥x avtomatov.
Lehko proverqetsq, çto suwestvugt ω-ravnosyl\n¥e asynxronn¥e y okonn¥e
ynycyal\n¥e avtomat¥, ne qvlqgwyesq ravnosyl\n¥my. Sootvetstvugwyj
prymer asynxronnoho avtomata pryveden v [5].
KaΩd¥j synxronn¥j avtomat ravnosylen nekotoromu avtomatu Mura, t.=e.
nekotoromu okonnomu avtomatu s ßyrynoj okna 1. KaΩd¥j okonn¥j avtomat
ravnosylen nekotoromu asynxronnomu avtomatu. Poπtomu klass (çastyçn¥x)
asynxronno avtomatn¥x funkcyj soderΩyt podklass (çastyçn¥x) okonno avto-
matn¥x funkcyj, a poslednyj, v svog oçered\, soderΩyt podklass (çastyçn¥x)
synxronno avtomatn¥x funkcyj nad zadann¥my alfavytamy.
Poskol\ku metryçeskye svojstva avtomatn¥x funkcyj formulyrugtsq v
termynax metryk na mnoΩestvax vsex ω-slov nad dann¥my alfavytamy X, Y,
dalee budem rassmatryvat\ lyß\ funkcyy na mnoΩestvax ω-slov.
Voobwe hovorq, asynxronn¥j avtomat moΩet preobrazov¥vat\ beskoneçn¥e
slova kak v beskoneçn¥e, tak y v koneçn¥e, poskol\ku znaçenyem eho funkcyy
v¥xoda moΩet\ b¥t\ pustoe slovo. Asynxronn¥j avtomat A budem naz¥vat\
nev¥roΩdenn¥m [7], esly v lgbom yz svoyx sostoqnyj on realyzuet çastyçnug
funkcyg yz Xω v Y ω . Dalee m¥ budem rassmatryvat\ tol\ko nev¥roΩden-
n¥e asynxronn¥e avtomat¥, t.=e. „asynxronn¥j avtomat” oznaçaet „nev¥roΩden-
n¥j asynxronn¥j avtomat”.
Sohlasno yzloΩennomu v¥ße, kaΩd¥j avtomat A, naxodqs\ v sostoqnyy q,
opredelqet çastyçnug funkcyg f qA, yz Xω v Y ω . Pust\ D qA, — oblast\
opredelenyq f qA, , V qA, — ee oblast\ znaçenyj. Pare ( , )A q sootvetstvuet
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
METRYÇESKYE SVOJSTVA FUNKCYJ, OPREDELQEMÁX … 1505
trojka ( ,D qA , f qA, , V qA, ) , hde D qA, � Xω , V qA, � Y ω , f qA, : D qA, → V qA,
— sgr\ektyvnoe otobraΩenye.
Lemma 4. Dlq proyzvol\noho avtomata A = X Y Q, , , ,ϕ ψ typa 1 – 3 y
lgboho eho sostoqnyq q mnoΩestva D qA, , V qA, qvlqgtsq zamknut¥my pod-
mnoΩestvamy toçek v metryçeskyx prostranstvax Xω y Y ω sootvetst-
venno.
Dokazatel\stvo. Posledovatel\nost\ x x1 2 =… , soderΩawaqsq v Xω
(yly Y ω ), prynadleΩyt D qA, (sootvetstvenno V qA, ) tohda y tol\ko tohda,
kohda v dyahramme Mura avtomata A suwestvuet oryentyrovann¥j put\ s naça-
lom v q takoj, çto konkatenacyq lev¥x (sootvetstvenno prav¥x) polovyn me-
tok strelok puty ravna x x1 2 =…=. Pust\ E — mnoΩestvo strelok dyahramm¥
Mura. MnoΩestvo vsex putej s naçalom v q qvlqetsq zamknut¥m podmnoΩest-
vom prqmoho (tyxonovskoho) proyzvedenyq E∞ , tak kak ono opredelqetsq us-
lovyqmy na otdel\n¥e koordynat¥ (konec strelky qvlqetsq naçalom sledug-
wej strelky, a naçalo pervoj strelky ravno q). Sledovatel\no, prostranstvo
vsex putej kompaktno. Funkcyq, stavqwaq v sootvetstvye puty konkatenacyg
eho lev¥x (prav¥x) metok, neprer¥vna (tak kak opredelena pokoordynatno).
Sledovatel\no, mnoΩestvo ee znaçenyj (ravnoe D qA, y V qA, sootvetstvenno)
takΩe kompaktno, a znaçyt, zamknuto.
Lemma 4 dokazana.
Pust\ A1 = X Y Q, , , ,1 1 1π λ y A2 = Y Z Q, , , ,2 2 2π λ — dva asynxronn¥x
avtomata. Opredelym nov¥j avtomat B = A A1 2∗ s mnoΩestvom sostoqnyj
Q Q1 2× , funkcyej perexodov π y funkcyej v¥xodov λ , zadann¥x ra-
venstvamy
π ( , ),q q x1 2( ) = π π λ1 1 2 2 1 1( , ), , ( , )q x q q x( )( ) ,
λ ( , ),q q x1 2( ) = λ λ2 2 1 1q q x, ( , )( ) .
Neposredstvenno proverqetsq, çto dlq lgb¥x sostoqnyj q Q1 1∈ y q Q2 2∈
ymeet mesto funkcyonal\noe ravenstvo
f fA q A q2 2 1 1, ,( ) = fB q q,( ),1 2
.
3. Katehoryy avtomatn¥x otobraΩenyj. 3.1. Katehoryg avtomatn¥x
otobraΩenyj opredelym sledugwym obrazom. Obæektamy katehoryy A qv-
lqgtsq zamknut¥e podmnoΩestva bez yzolyrovann¥x toçek v prostranstvax ω-
slov nad koneçn¥my alfavytamy. Morfyzmamy katehoryy A qvlqgtsq otob-
raΩenyq, opredelqem¥e asynxronn¥my avtomatamy.
Teorema 1. Pust\ X , Y — proyzvol\n¥e koneçn¥e alfavyt¥. Dlq lgb¥x
zamknut¥x podmnoΩestv U X⊆ ω
, V Y⊆ ω
, ne soderΩawyx yzolyrovann¥x
toçek, suwestvuet asynxronn¥j avtomat A s vxodn¥m alfavytom X y v¥-
xodn¥m alfavytom Y takoj, çto dlq nekotoroho vnutrenneho sostoqnyq q
spravedlyv¥ ravenstva D qA, = U, V qA, = V.
Dlq okonn¥x avtomatov analoh teorem¥=1 ne ymeet mesta, suwestvugt par¥
zamknut¥x podmnoΩestv U X⊆ ω
, V Y⊆ ω
, ne soderΩawyx yzolyrovann¥x
toçek, dlq kotor¥x ne suwestvugt okonn¥j avtomat A y eho sostoqnye q ta-
kye, çto D qA, = U, V qA, = V. Sootvetstvugwyj prymer budet pryveden v sle-
dugwem punkte.
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
1506 V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ
Sledugwaq teorema xarakteryzuet razlyçn¥e typ¥ avtomatn¥x otobraΩe-
nyj v topolohyçeskyx termynax.
Teorema 2. Pust\ U , V — proyzvol\n¥e zamknut¥e podmnoΩestva bez
yzolyrovann¥x toçek prostranstv Xω y Y ω sootvetstvenno. Sgr\ekcyq
f : U → V budet neprer¥vn¥m otobraΩenyem (sootvetstvenno lypßycev¥m
otobraΩenyem, ne uvelyçyvagwym rasstoqnyq) tohda y tol\ko tohda, kohda
f opredelqetsq nekotor¥m çastyçn¥m asynxronn¥m (sootvetstvenno okon-
n¥m, synxronn¥m) avtomatom nad alfavytamy X y Y.
V sluçae vsgdu opredelenn¥x asynxronn¥x avtomatov analoh teorem¥=2 do-
kazan v [5].
Katehoryq A soderΩyt dve estestvenn¥e podkatehoryy K A y M A s temy
Ωe obæektamy, çto y A . Morfyzmamy v pervoj yz nyx budut otobraΩenyq, za-
davaem¥e vsevozmoΩn¥my okonn¥my, a vo vtoroj — vsemy synxronn¥my avtoma-
tamy. ∏ty katehoryy s toçnost\g do πkvyvalentnosty mohut b¥t\ oxaraktery-
zovan¥ v termynax sootvetstvugwyx svojstv metryçeskyx prostranstv.
Neposredstvenn¥m sledstvyem teorem¥=2 qvlqetsq sledugwaq teorema.
Teorema 3. 1. Katehoryq A πkvyvalentna katehoryy ohranyçenn¥x kom-
paktn¥x ul\trametryçeskyx prostranstv bez yzolyrovann¥x toçek, morfyz-
mamy kotoroj qvlqgtsq neprer¥vn¥e otobraΩenyq.
2. Katehoryq K A πkvyvalentna katehoryy ohranyçenn¥x kompaktn¥x
ul\trametryçeskyx prostranstv bez yzolyrovann¥x toçek, morfyzmamy ko-
toroj qvlqgtsq lypßycev¥e otobraΩenyq.
3. Katehoryq M A πkvyvalentna katehoryy ohranyçenn¥x kompaktn¥x
ul\trametryçeskyx prostranstv bez yzolyrovann¥x toçek, morfyzmamy ko-
toroj qvlqgtsq otobraΩenyq, ne uvelyçyvagwye rasstoqnyq.
3.2. KaΩdaq yz ukazann¥x katehoryj avtomatn¥x otobraΩenyj ymeet ko-
neçnoavtomatn¥j analoh — katehoryg, obæektamy kotoroj qvlqgtsq tak naz¥-
vaem¥e racyonal\n¥e mnoΩestva ω-slov, a morfyzm¥ zadagtsq koneçn¥my av-
tomatamy sootvetstvugweho typa.
Racyonal\n¥e mnoΩestva opredelqgtsq sledugwym obrazom. Pust\ U �
� Xω — zamknutoe podmnoΩestvo ω-slov nad alfavytom X, ne soderΩawee
yzolyrovann¥x toçek, v ∈ ∗X — nekotoroe slovo nad X . PodmnoΩestvo
U( )v = w X w U∈ ∈{ }ω : v
nazovem podmnoΩestvom v-v¥çetov ω-slov yz U. MnoΩestva U( )v mohut
b¥t\ pust¥my, koneçn¥my yly beskoneçn¥my, mohut sovpadat\ dlq razlyçn¥x
v ∈ ∗X . Zamknutoe podmnoΩestvo U � Xω bez yzolyrovann¥x toçek nazovem
racyonal\n¥m, esly semejstvo podmnoΩestv eho v¥çetov qvlqetsq koneçn¥m:
U X( ) :v v ∈{ }∗ < ∞.
Teorema 4. Pust\ X , Y — fyksyrovann¥e alfavyt¥. Dlq proyzvol\n¥x
racyonal\n¥x podmnoΩestv U � Xω , V � Y ω suwestvuet koneçn¥j asynx-
ronn¥j avtomat A s v¥delenn¥m vnutrennym sostoqnyem q takoj , çto
D qA, = U, V qA, = V.
Dlq çastyçn¥x funkcyj yz Xω v Y ω opredelen¥ ponqtyq sostoqnyq
funkcyy y funkcyy s koneçn¥m çyslom sostoqnyj [9] . A ymenno, dlq çastyç-
noj funkcyy f : Xω → Y ω ee sostoqnyem, sootvetstvugwym slovu u X∈ ∗
,
naz¥vaetsq çastyçnaq funkcyq fu : Xω → Y ω , opredelqemaq ravenstvom
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
METRYÇESKYE SVOJSTVA FUNKCYJ, OPREDELQEMÁX … 1507
f w f uwu u( ) ( )= ( )Π , w X∈ ω
,
hde symvolom Πk oboznaçaetsq operator otsekanyq prefyksa dlyn¥ k v ω-
slovax. Hovorqt, çto f — funkcyq s koneçn¥m çyslom sostoqnyj, esly mno-
Ωestvo ee sostoqnyj koneçno.
Teorema 5. Pust\ U , V — proyzvol\n¥e racyonal\n¥e podmnoΩestva
prostranstv Xω y Y ω sootvetstvenno. Sgr\ekcyq f : U → V budet ne-
prer¥vn¥m (sootvetstvenno lypßycev¥m, yzometryçeskym) otobraΩenyem s
koneçn¥m çyslom sostoqnyj tohda y tol\ko tohda, kohda f zadaetsq koneç-
n¥m asynxronn¥m (sootvetstvenno okonn¥m, synxronn¥m) avtomatom nad
alfavytamy X, Y.
4. Dokazatel\stva. 4.1. Sformulyruem vnaçale rqd utverΩdenyj, yz ko-
tor¥x budut sledovat\ dokazatel\stva teorem=1 y 4.
Lemma 5. Pust\ X — alfavyt , A — nepustoe podmnoΩestvo prost-
ranstva Xω . Toçka ω ∈A budet yzolyrovannoj v A tohda y tol\ko toh-
da, kohda suwestvugt takoj prefyks u ω-slova w, çto D Au ∩ = w{ } .
Lemma sleduet yz opredelenyq yzolyrovannoj toçky y obweho vyda ßara v
prostranstve Xω .
Takym obrazom, v zamknutom podmnoΩestve bez yzolyrovann¥x toçek prost-
ranstva Xω kaΩd¥j prefyks lgboho ω-slova yz πtoho podmnoΩestva budet
prefyksom ewe odnoho ω-slova yz πtoho podmnoΩestva.
Zafyksyruem proyzvol\n¥e alfavyt¥ Xn = x xn1, ,…{ } , n ≥ 2, y dvuxπle-
mentn¥j alfavyt Y = 0 1,{ } . Dlq kaΩdoho natural\noho n ≥ 2 v¥berem mno-
Ωestvo Wn nepust¥x slov nad alfavytom Y , sostoqwee yz n πlementov, ko-
toroe soderΩyt kakoj-nybud\ prefyks kaΩdoho slova nad alfavytom Y, no
nykakoe slovo yz Wn ne qvlqetsq prefyksom druhoho slova yz Wn . V çast-
nosty, v kaçestve mnoΩestva W k2 moΩno v¥brat\ mnoΩestvo vsex slov dlyn¥
k, k ≥ 1, nad alfavytom Y. V obwem sluçae postroenye πtyx mnoΩestv moΩno
provodyt\ ynduktyvno, vklgçaq v Wn slovo 0 y vse slova vyda 1w, w Wn∈ −1 .
Dlq kaΩdoho A Xn⊂ , n ≥ 2, A = m ≥ 2, zafyksyruem nekotorug byekcyg
f A WA m: → .
Ponqtno, çto otobraΩenye
F A YA : ω ω→ ,
opredelqemoe ravenstvom
F y y yA( )1 2 3 … = f y f y f yA A A( ) ( ) ( )1 2 3 … , hde y y y A1 2 3 …∈ ω
,
qvlqetsq homeomorfyzmom.
Lemma 6. Dlq lgboho zamknutoho podmnoΩestva U Xn⊆ ω
, ne soderΩawe-
ho yzolyrovann¥x toçek, suwestvuet asynxronn¥j avtomat A s vxodn¥m al-
favytom Xn y v¥xodn¥m alfavytom Y takoj, çto dlq nekotoroho vnut-
rennoho sostoqnyq q spravedlyv¥ ravenstva D qA, = U, V qA, = Y ω . V slu-
çae racyonal\noho mnoΩestva U avtomat A moΩno v¥brat\ koneçn¥m.
Dokazatel\stvo. Postroym neobxodym¥j avtomat A v obwem sluçae.
Oboznaçym symvolom Π( )U mnoΩestvo vsex vozmoΩn¥x prefyksov vsex ω-
slov yz U. V kaçestve mnoΩestva vnutrennyx sostoqnyj avtomata A yspol\zu-
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
1508 V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ
em mnoΩestvo Π( )U . Oblast\g opredelenyq funkcyj perexodov ϕ y v¥xodov
ψ budet mnoΩestvo takyx par ( , )w x ∈ Π( )U × Xn , çto wx ∈ Π( )U . V πtom
sluçae polahaem ϕ( , )w x = wx.
Dlq kaΩdoho slova w ∈ Π( )U opredelym eho stepen\ vetvlenyq d w( ) kak
mownost\ podmnoΩestva Aw symvolov x alfavyta Xn takyx, çto
wx ∈ Π( )U . Dlq vsex slov w , ymegwyx stepen\ vetvlenyq 1, poloΩym
ψ( , )w x = ∅, v protyvnom sluçae polahaem ψ( , )w x = f xA( ) , hde A = Aw ,
x Aw∈ .
Tohda dlq vnutrenneho sostoqnyq q = ∅ tak opredelennoho avtomata A
budut v¥polnqt\sq ravenstva D qA, = U, V qA, = Y ω .
Zametym, çto dlq slov v, w ∈ Π( )U , dlq kotor¥x sootvetstvugwye ym pod-
mnoΩestva v¥çetov U( )v y U w( ) ravn¥, opredelqem¥e ymy funkcyy fA,v y
f wA, sovpadagt. ∏to oznaçaet, çto sostoqnyq v y w avtomata A moΩno
otoΩdestvyt\ y poluçenn¥j takym obrazom nov¥j avtomat takΩe budet udov-
letvorqt\ trebuem¥m v uslovyy ravenstvam. Esly Ωe mnoΩestvo U racyonal\-
no, to, otoΩdestvyv sostoqnyq, kotor¥m sootvetstvugt ravn¥e mnoΩestva v¥-
çetov, poluçym koneçn¥j avtomat, udovletvorqgwyj uslovyg.
Lemma 6 dokazana.
Lemma 7. Dlq lgboho zamknutoho podmnoΩestva U Xn⊆ ω
, ne soderΩawe-
ho yzolyrovann¥x toçek, suwestvuet asynxronn¥j avtomat A s vxodn¥m al-
favytom Xn y v¥xodn¥m alfavytom Y takoj, çto dlq nekotoroho vnut-
renneho sostoqnyq q spravedlyv¥ ravenstva D qA, = Y ω , V qA, = U. V sluçae
racyonal\noho mnoΩestva U avtomat A moΩno v¥brat\ koneçn¥m.
Dokazatel\stvo. Vnaçale postroym koneçn¥j avtomat A1 , ustanavly-
vagwyj homeomorfyzm meΩdu Y ω y Xn
ω
. MnoΩestvom eho vnutrennyx sos-
toqnyj budet mnoΩestvo Π( )Wn vsex prefyksov slov yz Wn . Dlq slova
v=∈ Π( )Wn y symvola y Y∈ znaçenyq funkcyj perexodov ϕ1 y v¥xodov ψ1
opredelym tak:
ϕ1( , )v y =
v v
v
y W
W
n
n
, ,
, ,
esly
esly
∉
∅ ∈
ψ1( , )v y =
∅ ∉
∈
−
, ,
( ), .
esly
esly
v
v v
y W
f y y W
n
X nn
1
Opredelqemoe avtomatom A1 v sostoqnyy ∅ otobraΩenye budet homeomor-
fyzmom Y ω na Xn
ω
.
Teper\ opredelym synxronn¥j avtomat A2 s vxodn¥m y v¥xodn¥m alfavy-
tom Xn y mnoΩestvom vnutrennyx sostoqnyj Xn
∗
. Dlq proyzvol\n¥x slova
v ∈ ∗Xn y symvola x Xn∈ znaçenye funkcyy perexodov ϕ2 poloΩym ravn¥m
vx . Esly vx ∈ Π( )U , to znaçenye funkcyy v¥xodov ψ2 budet ravn¥m x .
Esly Ωe vx ∉ Π( )U , to v¥berem symvol y Xn∈ y ω -slovo u takye, çto
vyw U∈ , pryçem dlq slov s ravn¥my podmnoΩestvamy v¥çetov v¥brann¥e sym-
vol y ω-slovo sootvetstvenno takΩe ravn¥. Opredelym ψ2( , )v x = ψ( , )v y .
TakΩe dlq lgboho slova v1 , prefyksom kotoroho qvlqetsq slovo vx , y lg-
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
METRYÇESKYE SVOJSTVA FUNKCYJ, OPREDELQEMÁX … 1509
boho symvola z Xn∈ poloΩym ψ2 1( , )v z = ψ2 1( , )u z , hde uz1 — prefyks ω-
slova vyw dlyn¥, ravnoj dlyne slova v1z . Takym obrazom, funkcyq v¥xodov
ψ2 budet vsgdu opredelennoj. Tak zadann¥j avtomat A2 v sostoqnyy ∅
realyzuet retrakcyg na Xn
∗
s oblast\g znaçenyj U. Zametym, çto dlq dvux
slov v , w ∈ Π( )U , dlq kotor¥x sootvetstvugwye ym podmnoΩestva v¥çetov
U( )v y U w( ) ravn¥, opredelqem¥e ymy funkcyy fA2 ,v y f wA2 , sovpadagt.
∏to oznaçaet, çto, kak y v dokazatel\stve lemm¥=6, v sluçae racyonal\noho
mnoΩestva U avtomat A2 moΩno zamenyt\ koneçn¥m.
Ostaetsq rassmotret\ superpozycyg postroenn¥x avtomatov, kotoraq v sos-
toqnyy ( , )∅ ∅ budet opredelqt\ trebuemoe otobraΩenye.
Lemma=7 dokazana.
Teorem¥ 1 y 4 sledugt teper\ yz lemm 6 y 7 pry prymenenyy superpozycyy
postroenn¥x v yx dokazatel\stve avtomatov.
4.2. Dlq dokazatel\stva ostavßyxsq teorem nam ponadobytsq sledugwee
opredelenye πntropyy.
Opredelenye 4. Pust\ U X⊂ ω
— zamknutoe mnoΩestvo. ∏ntropyej
mnoΩestva U naz¥vaetsq predel
h U( ) = lim
log
n
nU
n→∞
( )
,
esly on suwestvuet, hde Un — mnoΩestvo prefyksov dlyn¥ n πlementov
mnoΩestva U.
Lemma 8. Okonn¥e avtomat¥ opredelqgt lypßycev¥e otobraΩenyq y ne
uvelyçyvagt πntropyg mnoΩestv.
Dokazatel\stvo. Pust\ k — ßyryna okna ynycyal\noho okonnoho avto-
mata Aq . Tohda naçalo dlyn¥ n slova A wq ( ) zavysyt tol\ko ot naçala dly-
n¥ n + k slova w. Yz πtoho sleduet, çto otobraΩenye Aq lypßycevo. Krome
toho, esly U — nekotoroe mnoΩestvo beskoneçn¥x slov, to yz v¥ßeyzloΩen-
noho sleduet , çto
A Uq n( ) ≤ Un k+ .
Sledovatel\no,
h A Uq ( )( ) = lim
log ( )
n
q nA U
n→∞
( )
≤ lim
log
n
n kU
n→∞
+( )
=
= lim
log
n
n kU
n k→∞
+( )
+
= h U( ) .
Lemma=8 dokazana.
V çastnosty, neposredstvenno yz pred¥duwej lemm¥ sleduet, çto ne su-
westvuet okonnoho avtomata, byektyvno preobrazugweho Xω v Y ω dlq
X ≠ Y , poskol\ku h X( )ω = log X .
Lemma 9. Lgboe lypßycevo otobraΩenye zamknut¥x podmnoΩestv prost-
ranstv slov opredelqetsq nekotor¥m okonn¥m avtomatom.
Dokazatel\stvo. Neposredstvenno yz opredelenyq metryky na prost-
ranstve posledovatel\nostej sleduet, çto esly otobraΩenye f : U → V lypßy-
cevo, to suwestvuet takoe k, çto esly w1 , w U2 ∈ ymegt obwee naçalo dlyn¥
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
1510 V. V. NEKRAÍEVYÇ, A. S. OLYJNÁK, V. Y. SUWANSKYJ
n, to f w( )1 y f w( )2 ymegt obwee naçalo dlyn¥ n – k .
Yz πtoho sleduet, çto asynxronn¥j avtomat, realyzugwyj otobraΩenye f,
postroenn¥j v dokazatel\stve teorem¥ 2.4 v rabote [5], qvlqetsq lypßycev¥m.
Lemma 9 dokazana.
Teorem¥ 2 y 5 sledugt yz pred¥duwej lemm¥ y teorem¥ 2.4 rabot¥ [5].
1. Jean-Paul Allouche, Jeffrey Shallit. Automatic sequences: theory, applications, generalizations. –
Cambridge: Cambridge Univ. Press, 2003. – 588 p.
2. Pytheas Fogg N. Substitutions in dynamics, arithmetics and combinatorics. – Berlin etc.: Springer,
2002. – 402 p.
3. Dominique Perrin, Jean-Èric Pin. Infinite worlds: automata, semigroups, logic and games. –
Amsterdam etc.: Acad. Press, 2004. – 550 p.
4. Lind D., Marcus B. An introduction to symbolic dynamics and coding. – Cambridge: Cambridge
Univ. Press, 1995.
5. Hryhorçuk R. Y., Nekraßevyç V. V., Suwanskyj V. Y. Avtomat¥, dynamyçeskye system¥ y
hrupp¥ // Trud¥ Mat. yn-ta RAN. – 2000. – 231. – S. 134 – 214.
6. Nekrashevych V. Self-similar groups // Math. Surv. and Monogr. – Providence, RI: Amer. Math.
Soc., 2005. – 117.
7. Hryhorçuk R. Y., Nekraßevyç V. V. Hruppa asynxronn¥x avtomatov y racyonal\n¥e homeo-
morfyzm¥ Kantora // Mat. zametky. – 2001. – 67, # 5. – S. 680 – 685.
8. Eilenberg S. Automata, languages and machines. – New York; London: Acad. Press, 1974.
9. Raney G. N. Sequential functions // J. Assoc. Comput. Math. – 1958. – 5, # 2. – P. 177 – 180.
Poluçeno 22.10.09
ISSN 1027-3190. Ukr. mat. Ωurn., 2010, t. 62, # 11
|
| id | umjimathkievua-article-2974 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T02:33:50Z |
| publishDate | 2010 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/cc/fa72ed065123cf1f0abd89f6c52a5ecc.pdf |
| spelling | umjimathkievua-article-29742020-03-18T19:41:38Z Metric properties of functions defined by partial automata Метрические свойства функций, определяемых частичными автоматами Nekrashevich, V. V. Oliinyk, A. S. Sushchanskii, V. I. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. We characterize natural categories in which morphisms are defined by partial automata of the following three types: asynchronous automata, window automata, and automata synchronous over finite alphabets. We distinguish subcategories whose morphisms are defined by finite automata. Охарактеризовано природні категорії, морфізми в яких визначаються частковими автоматами трьох типів: асинхронними, віконними і синхронними над скінченними алфавітами. Виділено підкатегорії, морфізми яких визначені скінченними автоматами. Institute of Mathematics, NAS of Ukraine 2010-11-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2974 Ukrains’kyi Matematychnyi Zhurnal; Vol. 62 No. 11 (2010); 1500–1510 Український математичний журнал; Том 62 № 11 (2010); 1500–1510 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/2974/2698 https://umj.imath.kiev.ua/index.php/umj/article/view/2974/2699 Copyright (c) 2010 Nekrashevich V. V.; Oliinyk A. S.; Sushchanskii V. I. |
| spellingShingle | Nekrashevich, V. V. Oliinyk, A. S. Sushchanskii, V. I. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. Некрашевич, В. В. Олийнык, А. С. Сущанский, В. И. Metric properties of functions defined by partial automata |
| title | Metric properties of functions defined by partial automata |
| title_alt | Метрические свойства функций, определяемых частичными автоматами |
| title_full | Metric properties of functions defined by partial automata |
| title_fullStr | Metric properties of functions defined by partial automata |
| title_full_unstemmed | Metric properties of functions defined by partial automata |
| title_short | Metric properties of functions defined by partial automata |
| title_sort | metric properties of functions defined by partial automata |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2974 |
| work_keys_str_mv | AT nekrashevichvv metricpropertiesoffunctionsdefinedbypartialautomata AT oliinykas metricpropertiesoffunctionsdefinedbypartialautomata AT sushchanskiivi metricpropertiesoffunctionsdefinedbypartialautomata AT nekraševičvv metricpropertiesoffunctionsdefinedbypartialautomata AT olijnykas metricpropertiesoffunctionsdefinedbypartialautomata AT suŝanskijvi metricpropertiesoffunctionsdefinedbypartialautomata AT nekraševičvv metricpropertiesoffunctionsdefinedbypartialautomata AT olijnykas metricpropertiesoffunctionsdefinedbypartialautomata AT suŝanskijvi metricpropertiesoffunctionsdefinedbypartialautomata AT nekrashevichvv metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT oliinykas metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT sushchanskiivi metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT nekraševičvv metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT olijnykas metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT suŝanskijvi metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT nekraševičvv metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT olijnykas metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami AT suŝanskijvi metričeskiesvojstvafunkcijopredelâemyhčastičnymiavtomatami |