Automaton extensions of mappings on the set of words defined by finite Mealy automata

Automaton extensions of mappings on the set of words defined by finite Mealy automata

The properties of an automaton extensions of mappings on the set of words over a finite alphabet is discussed. We obtain the criterion whether the automaton extension of given mapping if defined by a finite automaton.

Збережено в:
Бібліографічні деталі
Дата:2005
Автор: Osys, M.
Формат: Стаття
Мова:English
Опубліковано: Інститут прикладної математики і механіки НАН України 2005
Назва видання:Algebra and Discrete Mathematics
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/157337
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Automaton extensions of mappings on the set of words defined by finite Mealy automata / M. Osys // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 36–47. — Бібліогр.: 7 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-157337
record_format dspace
spelling irk-123456789-1573372019-06-21T01:27:14Z Automaton extensions of mappings on the set of words defined by finite Mealy automata Osys, M. The properties of an automaton extensions of mappings on the set of words over a finite alphabet is discussed. We obtain the criterion whether the automaton extension of given mapping if defined by a finite automaton. 2005 Article Automaton extensions of mappings on the set of words defined by finite Mealy automata / M. Osys // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 36–47. — Бібліогр.: 7 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 68Q70, 68Q45. http://dspace.nbuv.gov.ua/handle/123456789/157337 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description The properties of an automaton extensions of mappings on the set of words over a finite alphabet is discussed. We obtain the criterion whether the automaton extension of given mapping if defined by a finite automaton.
format Article
author Osys, M.
spellingShingle Osys, M.
Automaton extensions of mappings on the set of words defined by finite Mealy automata
Algebra and Discrete Mathematics
author_facet Osys, M.
author_sort Osys, M.
title Automaton extensions of mappings on the set of words defined by finite Mealy automata
title_short Automaton extensions of mappings on the set of words defined by finite Mealy automata
title_full Automaton extensions of mappings on the set of words defined by finite Mealy automata
title_fullStr Automaton extensions of mappings on the set of words defined by finite Mealy automata
title_full_unstemmed Automaton extensions of mappings on the set of words defined by finite Mealy automata
title_sort automaton extensions of mappings on the set of words defined by finite mealy automata
publisher Інститут прикладної математики і механіки НАН України
publishDate 2005
url http://dspace.nbuv.gov.ua/handle/123456789/157337
citation_txt Automaton extensions of mappings on the set of words defined by finite Mealy automata / M. Osys // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 36–47. — Бібліогр.: 7 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT osysm automatonextensionsofmappingsonthesetofwordsdefinedbyfinitemealyautomata
first_indexed 2025-07-14T09:46:51Z
last_indexed 2025-07-14T09:46:51Z
_version_ 1837615191882203136
fulltext Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 4. (2005). pp. 36 – 47 c© Journal “Algebra and Discrete Mathematics” Automaton extensions of mappings on the set of words defined by finite Mealy automata Miros law Osys Communicated by V. I. Sushchansky Abstract. The properties of an automaton extensions of mappings on the set of words over a finite alphabet is discussed. We obtain the criterion whether the automaton extension of given mapping if defined by a finite automaton. Introduction In the set of all transformations of the set of finite words over given alphabet we distinguish a subset of the automaton mappings, i.e. trans- formations induced by (finite or infinite) Mealy automata . Although both sets are uncountable, not every function f : X∗ → X∗ is defined by certain automaton. In sixties of the XX century has been indicated (e.g. in [3]) that after addition a new symbol to the alphabet, arbitrary transformation can be extended to an automaton mapping, that uniquely determines the initial transformation. Moreover, an effective method for such constructions has been established. Algol 60 algorithm for finding the minimum necessary number of the new symbols is developed in [1]. Since mentioned extension is not unique, we define two different possi- bilities of the construction, the plain extension and the cyclic extension, and develop some basic properties of them. We discuss the problem whether exists a finite automaton inducing extension for given transfor- mation. The main result of this paper is 2000 Mathematics Subject Classification: 68Q70, 68Q45. Key words and phrases: automaton mapping, Mealy automaton. Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 37 Theorem 1. Let f̂ : X∗ α → X∗ α be the plain or cyclic extension of the transformation f : X∗ → X∗. The extension f̂ is a finite–state automaton mapping if and only if the following conditions are satisfied: 1. f(X∗) is a finite set, 2. the inverse image f−1(u) is a regular language for each u ∈ f(X∗). The contents are organized as follows. In Section 1 we list the basic notations and recall a notions of a Mealy automaton and a Rabin–Scott automaton. In Section 2 we define a notion of an automaton extension of the transformation. In Section 3 we prove Theorem 1. 1. Preliminaries 1.1. Let X be an alphabet, and X∗ be the free monoid over X with an empty word ε as a neutral element. We shall write uv for the product of u, v ∈ X∗ and uk for k︷ ︸︸ ︷ u . . . u. The length of the word u is denoted by |u|. The word u is a prefix of the word v (denoted by u ≤ v) if v = uw for the certain word w. The word v is a segment of u if there exist words u1, u2 ∈ X∗ such that u = u1vu2. 1.2. An initial Mealy-type automaton over the alphabet X is a tuple A = (Q, q0, X, δ, λ) which consists of the following data: ⊲ a set Q of the internal states, Q 6= ∅ ⊲ a distinguished state q0 ∈ Q called initial ⊲ the alphabet of the automaton, X 6= ∅ ⊲ a next-state function δ : Q × X → Q ⊲ an output function λ : Q × X → X A tuple A = (Q, q0, X, δ, λ) is partial Mealy automaton if either δ or λ is a partial function. The automaton A is finite if the sets Q and X are finite. We often use a notation qi x/y 7−→ qj Jo u rn al A lg eb ra D is cr et e M at h .38 Automaton extensions of mappings instead of δ(qi, x) = qj , λ(qi, x) = y . 1.3. The next–state function and the output function of the automaton A = (Q, q0, X, δ, λ) can be extended on the set Q × X∗ by the following recurrent equalities: δ(q, ε) = q , δ(q, ux) = δ(δ(q, u), x) , λ(q, ε) = ε , λ(q, ux) = λ(δ(q, u), x) , where x ∈ X and u ∈ X∗. An initial automaton A defines mapping fA : X∗ → X∗ as follows: fA(ε) = ε , fA(x1 . . . xk) = λ(q0, x1)λ(q0, x1x2) . . . λ(q0, x1 . . . xk) . In case of the partial automaton, fA is a partial function. Definition 1. [6] A function f : X∗ → X∗ is called an (finite–state) automaton mapping if there exists an (finite) automaton A, such that f = fA. Proposition 1. A function f : X∗ → X∗ is an automaton mapping if and only if it has the following properties: 1. it preserves the lengths of the words, that is |f(u)| = |u| for every u ∈ X∗ 2. (common prefix property) if u, v ∈ X∗ then each prefix w of these words is translated in the same manner, thus it follows that f(u) and f(v) have common prefix of the length greater or equal |w|. Definition 2. A function f : X∗ → X∗ is called an partial automaton mapping if there exists an partial automaton A, such that f = fA. Proposition 2. A function g : X∗ → X∗ is a partial automaton mapping if and only if it has the following properties: 1. domain of the function is prefix closed, that is, u ∈ Dom g and v ≤ u implies that v ∈ Dom g, 2. there exists an automaton mapping f : X∗ → X∗, such that g = f |Dom g . Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 39 For the details of the proofs refer to [6], [2], [5], [4]. 1.4. A Rabin–Scott automaton is a tuple A = (Q, q0, T, X, δ) , which is similar to the Mealy automaton, except deleted function λ and added set T ⊂ Q which collects the terminal nodes (or accept states). A set of the words L(A) = {u ∈ X∗ : δ(q0, u) ∈ T} will be referred to as the language recognizable by the automaton A. The language L ⊂ X∗ is said to be regular if there exists a finite automaton recognizing L. For more information refer to [7], [2]. 2. Automaton extension of mapping 2.1. Let f : X∗ → X∗ be a function that satisfies f(ε) = ε. Let Xα = X ∪ {α}, α 6∈ X be the extended alphabet. With a symbol t we will denote a homomorphism X∗ α → X∗ given by: t(α) = ε, t(x) = x, x ∈ X . Definition 3. An automaton mapping f̂ : X∗ α → X∗ α is called an au- tomaton extension mapping (or simply extension) of f : X∗ → X∗ if there exists an embedding µf : X∗ → X∗ α such that the following dia- gram is commutative: u ∈ X∗ f 7−→ f(u) ∈ X∗ µf ↓ ↑ t u′ ∈ X∗ α bf 7−→ f̂(u′) ∈ X∗ α . 2.2. The extension f̂ of an arbitrary function f : X∗ → X∗ will be defined in two steps: 1. a partial extension is constructed, that is function X∗ α → X∗ α defined on the certain fixed subset M ⊂ X∗ α, 2. the domain of the obtained function is extended on the monoid X∗ α. For the construction related to the first step we will apply a method described in [3], p.19. Jo u rn al A lg eb ra D is cr et e M at h .40 Automaton extensions of mappings Definition 4. For every u ∈ X∗ we define µf (u) = uα|f(u)| and introduce a set M = {v′ ∈ X∗ α : v′ ≤ µf (u), u ∈ X∗} . The mapping f̂ : M → X∗ α is defined as follows: a) if u′ has the form uα|f(u)|, u ∈ X∗ then f̂(u′) = f̂(uα|f(u)|) = α|u|f(u) , b) if v′ ∈ M and v′ ≤ u′ = uα|f(u)| then f̂(v′) = w′, w′ ≤ f̂(u′), |w′| = |v′| . Above definition of the function f̂ is correct since w′ does not depend on choosing the word u′. Also, for u′ = µf (u), the properties t(u′) = u and t(f̂(u′)) = f(u) hold. Thus, the diagram from the definition 3 is commutative. Proposition 3. The extension f̂ : X∗ α → X∗ α is a partial automaton mapping over the alphabet Xα. Proof. For every word u′ ∈ X∗ α of the form uα|f(u)| we have |u′| = |uα|f(u)|| = |α|u|f(u)| = |f̂(u′)| and for every prefix v′ ≤ u′ f̂(v′) ≤ f̂(u′), |f̂(v′)| = |v′|. Therefore f̂ preserves the lengths of the words and has the common prefix property. It is also clear that the set M is prefix closed. 2.3. Example. Consider a function f : X∗ → X∗, X = {0, 1} defined by f(u) =    0 |u| even, |u| > 0, 11 |u| odd, ε u = ε. Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 41 We agree that f is not an automaton mapping since it does not preserve either lengths nor has the common prefix property. Let us show how the extension mapping works. Instead 01 f 7−→ 0 and 101 f 7−→ 11 we have 01α bf 7−→ αα0 and 101αα bf 7−→ ααα11 . It can be seen that on the input side the letter α is utilized to terminate a sequence of letters from the set X, whereas on the output it plays role of an “empty” symbol while the automaton waits for completing the input word. 2.4. We introduce two different methods for extending f̂ on the set X∗ α, which will be referred to as ‘plain extension’ and ‘cyclic extension’. Definition 5. The plain extension of the transformation f : X∗ → X∗ is a mapping f̂1 : X∗ α → X∗ α defined by: • f̂1|M = f̂ , where f̂ is the automaton extension of f and M is the set established in definition 4, • f̂1(α kv′) = αkf̂1(v ′), • f̂1(uα|f(u)|v′) = α|u|f(u)α|v′|, • f̂1(uαmv′) = α|u|f(u)αn, m + |v′| = |f(u)| + n for m + |v′| ≥ |f(u)|, • f̂1(uαmv′) = α|u|v, v ≤ f(u), m + |v′| = |v| for m + |v′| < |f(u)| where u, v ∈ X∗ and v′ ∈ X∗ α. The automaton mapping defined this means ignores appended word v′ by treating it as a sequence of “empty” symbols. For the next definition recall that arbitrary word v′ ∈ X∗ α can be uniquely written as v′ = αk0u1α k1u2α k2 . . . unαkn , ui ∈ X∗ where k0, kn ≥ 0 and k1, . . . , kn−1 ≥ 1. Definition 6. The cyclic extension of the transformation f : X∗ → X∗ is a mapping f̂2 : X∗ α → X∗ α defined by: • f̂2|M = f̂ , where f̂ is the automaton extension of f and M is the set established in definition 4, Jo u rn al A lg eb ra D is cr et e M at h .42 Automaton extensions of mappings • f̂2(α k) = αk, • f̂2(uα|f(u)|αk) = α|u|f(u)αk, • f̂2(uαm) = α|u|v, v ≤ f(u), |v| = m for m < |f(u)|, • f̂2(v ′) = αk0 f̂2(u1α k1)f̂2(u2α k2) . . . f̂2(unαkn) where v′ = αk0u1α k1u2α k2 . . . unαkn . The mapping obtained that way translates independently every segment of the form uiα ki . 2.5. Example. Let f : {0, 1} → {0, 1} be function defined by f(u) =    11 if u = 0, 0 if u = 11, ε if u 6∈ {0, 11}. Then the plain extension f̂1 and the cyclic extension f̂2 translate words in the following manner: u ∈ X∗ α 0αα 0α 11α 11 0α0α 1α11α f̂1(u) α11 α1 αα0 αα α1αα ααααα f̂2(u) α11 α1 αα0 αα α1α1 αααα0 Proposition 4. 1. For every function f : X∗ → X∗, f(ε) = ε the following conditions hold: a) plain and cyclic extensions are well defined automaton map- pings over the alphabet X∗ α, b) f̂1 6= f̂2 unless f is trivial (i.e. f(u) = ε for all u ∈ X∗). 2. For every f, g : X∗ → X∗, such that f(ε) = g(ε) = ε and f 6= g, we have: f̂1 6= ĝ1, f̂2 6= ĝ2 . Proof. (1a) Clearly, the definitions allow us to calculate f̂1(u ′) and f̂2(u ′) for all u′ ∈ X∗ α thus extensions are well defined. Furthermore, directly from the definitions, it can be seen that extensions f̂1 and f̂2 are automa- ton mappings since for every u′ ∈ X∗ α |f̂1(u ′)| = |f̂2(u ′)| = |u′| Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 43 and the common prefix property holds as well, directly from definitions. (1b) If f is trivial, then f̂1(u ′) = f̂2(u ′) = α|u′| for all u′ ∈ X∗ α. Otherwise, there exists u ∈ X∗ such that f(u) = v 6= ε. The extensions are distinct, since f̂1(uα|v|uα|v|) = α|u|vα|u|α|v| and f̂2(uα|v|uα|v|) = α|u|vα|u|v . (2) It is sufficient to prove that f is uniquely determined by f̂ . Let f̂ : Xα → Xα be the plain or cyclic extension. We will show that for every u ∈ X∗ a word f(u) can be calculated. Indeed, take a sequence vi = f̂(uαi), i = 1, 2, . . . Then exists the number j, such that the last letters of the words vi, i ≤ j are distinct from α and all words vi, i > j end with the letter α. It is obvious that f(u) = t(vj), therefore the mapping f is determined by f̂ and the operations f 7→ f̂1 and f 7→ f̂2 are one-to-one. 3. Finite state extensions 3.1. The purpose of this part is to find conditions for the mapping f under which an automaton corresponding to the extension mapping f̂ is finite. We assume the set X is finite. Lemma 1. Let f : X∗ → X∗ be an arbitrary mapping and f̂ : X∗ α → X∗ α its plain or cyclic extension. If f̂ is finite–state automaton mapping then the set f(X∗) is finite. Proof. Let A = (Q, q0, Xα, δ, λ) be a finite automaton defining the map- ping f̂ . Consider words of the form u′ = uα|f(u)| , u ∈ X∗ . If the set f(X∗) is infinite then, since Q is finite, there exist the words u1 and u2 such that δ(q0, u1) = δ(q0, u2). Denote this common state by q. It is clear that λ(q, α|f(u1)|) = f(u1) and λ(q, α|f(u2)|) = f(u2) . If |f(u1)| = |f(u2)| then we at once obtain f(u1) = f(u2). In the opposite case we may assume that |f(u1)| < |f(u2)| and let k = |f(u2)| − |f(u1)|. By definition of f̂ we have f̂ : uα|f(u)|α 7→ α|u|f(u)α Jo u rn al A lg eb ra D is cr et e M at h .44 Automaton extensions of mappings and in particular: λ(q, α|f(u1)|αk) = f(u1)α k , λ(q, α|f(u2)|) = f(u2) . From α|f(u1)|αk = α|f(u2)| we obtain an equality f(u1)α k = f(u2) ∈ X∗ which is true only with k = 0 and f(u1) = f(u2). Although f(u) 7→ δ(q, u) need not to be a function (since a nonmin- imal automaton can include several paths to output f(u)), from above discussion it follows that for f(u1) 6= f(u2) we have δ(q0, u1) 6= δ(q0, u2). Thus the set f(X∗) is finite. 3.2. Example. Let P denote the set of prime numbers. Consider an alphabet X = {1, 2} and a function f(u) =    ε u = ε, 1 |u| ∈ P, 2 |u| 6∈ P. The extension mapping f̂ satisfies f̂ : uα 7→ { α|u|1 |u| ∈ P, α|u|2 |u| 6∈ P. The automaton defined by f̂ cannot be finite. Indeed, were automaton inducing f̂ be finite then by taking Q = {δ(q0, u) : |u| ∈ P} as the set of an accept states we obtain a contradiction since L = {u ∈ X∗ : |u| ∈ P} is not regular. 3.3. Proof of the main theorem. Both conditions state that a function f has the form f(u) =    u1 u ∈ L1, . . . uk u ∈ Lk, where Li, i = 1, . . . , k are regular languages satisfying X∗ = L1 ∪ L2 ∪ · · · ∪ Lk , Li ∩ Lj = ∅ . Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 45 (⇒) Let A = (Q, q0, Xα, δ, λ) be finite automaton inducing f̂ . From the previous lemma f(X∗) is a finite set. Furthermore, the language L = f−1(u) is recognizable by the automaton A′ = (Q, q0, T, X, δ′) where the set of an accept states is taken as T = {δ(q0, v) : f(v) = u} and the next-state function δ′ is obtained from δ by deleting arrows labeled with α on the input side of its label. Since A′ is finite, thus L is regular. (⇐) Let k = |f(X∗)| and Li, i = 1, . . . , k be pairwise distinct regular languages of the form f−1(u), u ∈ X∗. Then, for each i there exists a finite Rabin–Scott automaton Ai which accepts the language Li Ai = (Qi, q i 0, Ti, X, δi) where Qi are finite sets and 1 ≤ i ≤ k. The automaton A = (Q, q0, X, δ, λ) defining f̂ can be carried from above by taking 1. Q′ = Q1×· · ·×Qk, where Q′ ⊂ Q and the remaining elements of Q are introduced below, 2. q0 = (q1 0, . . . , q k 0 ), 3. (q1, . . . , qk) x/α 7→ (r1, . . . , rk) iff δi(q i, x) = ri for 1 ≤ i ≤ k. Since {Li : i = 1, . . . , k} forms a partition on X∗, then obtained par- tial automaton has the property, that for every state q = (q1, . . . , qk) exactly one component is an accept state in the automaton corresponding to its position. So far, for the partial automaton, the function δ does not accept symbol α as second argument and the automaton is not capable to produce symbols other than α. From earlier mentioned property, we claim that for every state q = (q1, . . . , qk) there exists corresponding language Lq = {u : δ(q0, u) = q} and |f(Lq)| = 1 that is all words from Lq are mapped into the same word, say v = x1 . . . xs. After adding paths of the form q α/x1 7−→ q1 α/x2 7−→ . . . α/xs 7−→ qs , (∗) Jo u rn al A lg eb ra D is cr et e M at h .46 Automaton extensions of mappings where q1, . . . , qs are new states, we have the finite partial automaton that follows the rule uα|f(u)| 7→ α|u|f(u) . While δ is still the partial mapping, it needs to be extended in order to obtain well-defined plain or cyclic extension. This can be done while preserving finite amount of states. In both cases, consider paths of the form (*). Let qs be a terminal state of the path. In case of the plain extension we define qs x′/α 7−→ qs, x′ ∈ Xα and qi x/xi 7−→ qs, x ∈ X, i = 1, . . . , s − 1 . However, for the cyclic extension we apply qs α/α 7−→ qs and qi x/α 7−→ δ(q0, x), x ∈ X, i = 1, . . . , s . Finally, for both plain and cyclic extensions we will apply q0 α/α 7−→ q0 . Above definitions complete a construction of the well-defined au- tomaton inducing the extension f̂ . Acknowledgments Thanks to Vitalii Sushchanskii for his kindness and for invaluable help. References [1] Čulik K. II, Construction of the Automaton Mapping, (in Russian) Aplikace Matematiky, Vol. 10, No. 6, 1965 [2] Eilenberg S., Automata, Languages and Machines, Volume A, Academic Press, New York, 1974 [3] Glushkov V. M., Abstract Theory of Automata, (in Russian) Russian Math. Surveys, Vol. XVI, 5(101), 1961, pp. 3–62 Jo u rn al A lg eb ra D is cr et e M at h .M. Osys 47 [4] Grigorchuk R. I., Nekrashevich V. V., Sushchanskii V. I., Automata, Dynamical Systems, and Groups, Proceedings of Steklov Institute of Mathematics, Vol. 231, 2000, pp. 128–203 [5] Mikolajczak B. (ed.), Algebraic and Structural Automata Theory, Annals of Discrete Mathematics, Vol. 44, North-Holland, 1991 [6] Raney G.N., Sequential Functions, J. Assoc. Comput. Math., Vol. 5, 1958, N2, pp. 177–180 [7] Sheng Yu, Regular Languages, In: Handbook of Formal Languages, Volume 1, Springer-Verlag, Berlin, 1997, pp. 41–110 Contact information Miros law Osys Silesian University of Technology, Faculty of Mathematics and Physics, ul. Kaszubska 23, 44-100 Gliwice, Poland E-Mail: odys@zeus.polsl.gliwice.pl URL: zeus.polsl.gliwice.pl/˜odys Received by the editors: 29.10.2004 and final form in 15.12.2005.

Схожі ресурси