The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] prefix code(6hit)

1-6hit
  • A Class by Principal Congruence of a Syntactically Embedded Language

    Tetsuo MORIYA  

     
    LETTER-Automata and Formal Language Theory

      Vol:
    E90-D No:6
      Page(s):
    975-978

    In this paper, we introduce a syntactically embedded (s-embedded) language, and consider its principal congruence. The following three results are proved, where PL is the principal congruence of a language L, and W(L) is the residual of L. (1) For a language K, s-embedded in M, K is equal to a PM class. (2) For a language K, s-embedded in an infix language M, K is equal to a PW(M) class. (3) For a nonempty s-embedded language L, if L is double-unitary, then L is equal to a PW(M) class. From the above results, we can obtain those for principal congruence of some codes. For example, Ln is equal to a PLn+1 class for an inter code L of index n.

  • A Note on Parses of Codes

    Tetsuo MORIYA  

     
    LETTER-Theory of Automata, Formal Language Theory

      Vol:
    E86-D No:11
      Page(s):
    2472-2474

    In this note, we present some results about parses of codes. First we present a sufficient condition of a bifix code to have the bounded indicator. Next we consider a proper parse, introduced notion. We prove that for a strongly infix code, the number of proper parses is at most three under some condition. We also prove that if a code X has a unique proper parse for each word under the same condition, then X is a strongly infix code.

  • Power-Properties of Codes

    Tetsuo MORIYA  

     
    LETTER-Theory of Automata, Formal Language Theory

      Vol:
    E85-D No:3
      Page(s):
    577-579

    We consider the following three statements for a code L. (P1) For every n 2, both wn Ln and wn+1 Ln+1 imply w L. (P2) For every n 2, if wn Ln, then w L. (P3) For every m, k 2 with m k, wk Lm implies w L. First we show that for every code L, P1 holds. Next we show that for every infix code L, P2 holds, and that a code L is an infix code iff P2 holds and L is a weakly infix code. Last we show that for every strongly infix code L, P3 holds, and that a code L is a strongly infix code iff P3 holds and L is a hyper infix code.

  • Syntactic Congruences of Codes

    Tetsuo MORIYA  Itaru KATAOKA  

     
    LETTER-Theory of Automata, Formal Language Theory

      Vol:
    E84-D No:3
      Page(s):
    415-418

    We consider syntactic congruences of some codes. As a main result, for an infix code L, it is proved that the following (i) and (ii) are equivalent and that (iii) implies (i), where PL is the syntactic congruence of L. (i) L is a PL2-class. (ii) Lm is a PLk-class, for given two integers m and k with 1 m k. (iii)L* is a PL*-class. Next we show that every (i), (ii) and (iii) holds for a strongly infix code L. Moreover we consider properties of syntactic conguences of a residue W(L) for a strongly outfix code L.

  • A Note on the Fix-Free Code Property

    Kazuyoshi HARADA  Kingo KOBAYASHI  

     
    PAPER-Source Coding/Image Processing

      Vol:
    E82-A No:10
      Page(s):
    2121-2128

    We study some sufficient conditions of codeword lengths for the existence of a fix-free code. Ahlswede et al. proposed the 3/4 conjecture that Σi=1n a-li 3/4 implies the existence of a fix-free code with lengths li when a=2 i. e. the alphabet is binary. We propose a more general conjecture, and prove that the upper bound of our conjecture is not greater than 3/4 for any finite alphabet. Moreover, we show that for any a2 our conjecture is true if codeword lengths l1,l2,. . . consist of only two kinds of lengths.

  • Composition of Strongly Infix Codes

    Tetsuo MORIYA  

     
    LETTER-Automata,Languages and Theory of Computing

      Vol:
    E81-D No:6
      Page(s):
    609-611

    We introduce a strongly infix code. A code X is a strongly infix code if X is an infix code and any catenation of two words in X has no proper factor in X, which is neither a left factor nor a right factor. We show that the class of strongly infix codes is closed under composition, and, as the dual result, that the property to be strongly infix is inherited by a component of a decomposition.