On a Problem of Satyanarayana Regarding the Recognizability of Codes
M. Satyanarayana posed a problem in 2001: which infinite codes are recognizable. Recognizable code means a code accepted by a finite automaton. Equivalently a code X is recognizable iff \(u^{-1}X\) is finite for \(u\in A^{*}\) . It is well known that fini
- PDF / 298,468 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 175 Views
Abstract M. Satyanarayana posed a problem in 2001: which infinite codes are recognizable. Recognizable code means a code accepted by a finite automaton. Equivalently a code X is recognizable iff u −1 X is finite for u ∈ A∗ . It is well known that finite codes are recognizable. We partially answer the problem of Satyanarayana. We know that a right complete semaphore suffix code is recognizable. We study here recognizablity of right complete semaphore codes with conditions other than suffix and further dropping semaphore condition also. Barring right completeness, the problem for general infinite codes is still open. Keywords Recognizability of codes · Right complete codes · Semaphore codes AMS Mathematics subject classification (2010)
20M45
1 Introduction An alphabet A is a non empty set of symbols, called letters. A word w over A is a finite concatenation of letters, a word without any letter is called the empty word denoted by 1. The set of all words including 1 under concatenation of words forms the free monoid A∗ generated by A. However non empty words over A forms a semigroup A+ . Thus A+ = A∗ − {1}. Any proper subset X of A+ is called a code if a message over X is unique namely x1 . . . xr = y1 . . . ys , with xi , y j ∈ X implies r = s and xi = yi . The set of messages x1 . . . xr forms a monoid X ∗ , called information. R.D. Giri (B) RTM Nagpur University, Nagpur, India e-mail: [email protected] © Springer Science+Business Media Singapore 2016 S.T. Rizvi et al. (eds.), Algebra and its Applications, Springer Proceedings in Mathematics & Statistics 174, DOI 10.1007/978-981-10-1651-6_27
421
422
R.D. Giri
A word u ∈ A∗ is called a left (right) factor of w if uv = w (vu = w) for some v ∈ A∗ . If v = 1, the factor is called improper otherwise if v = 1, it is called proper factor. Note that 1 is always a left (right) factor of any word w ∈ A+ .
2 Preliminaries In this section we provide some notation, basic definitions, and results. For a code X , the set of all left factors is denoted by PX and the set of all proper left factors is denoted by L X that is, L X = PX \(X ∪ 1). The set of all right factors is denoted by R X . Some basic definitions are provided with specific references. Definition 2.1 ([1]) A code X is called right complete if for every u ∈ A∗ , there exists a word v ∈ A∗ such that uv ∈ X ∗ . In other words, every word in A∗ can be completed on the right to a message. Remark 2.1 (Theorem 3.3. [1]) A maximal prefix code can be defined as a right complete prefix code. Definition 2.2 ([1, 3]) A code X over an alphabet A is said to satisfy F-1 condition if A+ X A+ ∩ X = φ. Definition 2.3 ([1, 3]) Maximal prefix codes which satisfy the F-1 condition are called semaphore codes. Definition 2.4 ([1]) A code X is said to be suffix PX -closed when uv ∈ PX implies v ∈ PX where PX is the set of all left factors of X-words. For example the sets X = b∗ a or X = a, b2 , ba are suffix PX -closed over A = {a, b}. Definition 2.5 ([1, 3]) A code X over an alphabet A is called a thin code if there exists a w
Data Loading...
