Top

Acta Informatica

Published in:

08-09-2023 | Original Article

The second step in characterizing a three-word code

Authors: Chunhua Cao, Jiao Xu, Lei Liao, Di Yang, Guichuan Jia, Qian Du

Published in: Acta Informatica | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In the fields of combinatorics on words and theory of codes, a two-word language \(\{x, y\}\) is a code if and only if \(xy \not = yx\). But up to now, corresponding characterizations for a three-word language, which forms a code, have not been completely found. Let \(X=\{x,\ y,\ z\}\) be a three-word language and \(|x|,\ |y|,\ |z|\) be their lengths. When \(|x| = |y| < |z|\), a necessary and sufficient condition for X to be a code was obtained in 2018. If \(|x| < |y| = |z| \le 2|x|\), a necessary and sufficient condition for X to be a code is proposed in this paper.

previous article On first-order runtime enforcement of branching-time properties

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge Press, Cambridge (2009)CrossRefMATH

Budkina, L.G., Markov, A.A.: On \(F-\)semigroups with three generators. Math. Notes 14, 711–716 (1973)MathSciNetCrossRefMATH

Cao, C., Qing, L., Yang, D.: A first step in characterizing three-element codes. Acta Inform. 55, 445–457 (2018)MathSciNetCrossRefMATH

Derencourt, D.: A three-word code which is not prefix–suffix composed. Theor. Comput. Sci. 163, 145–160 (1996)MathSciNetCrossRefMATH

Fan, C.M., Shyr, H.J., Yu, S.S.: \(d\)-words and \(d\)-languages. Acta Inform. 35, 709–727 (1998)MathSciNetCrossRefMATH

Harju, T., Nowotka, D.: On the independence of equations in three variables. Theor. Comput. Sci. 307, 139–172 (2003)MathSciNetCrossRefMATH

Karhumäki, J.: On three-element codes. Theor. Comput. Sci. 40, 3–11 (1985)MathSciNetCrossRefMATH

Karhumäki, J.: A property of three-element codes. Theor. Comput. Sci. 41, 215–222 (1985)MathSciNetCrossRefMATH

Karhumäki, J., Petre, I.: Conway’s problem for three-word sets. Theor. Comput. Sci. 289, 705–725 (2002)MathSciNetCrossRefMATH

10.

Li, Z.Z., Tsai, Y.S., Yih, G.C.: Characterizations on codes with three elements. Soochow J. Math. 30, 177–196 (2004)MathSciNetMATH

11.

Li, Z.Z., Tsai, Y.S.: Three-element codes with one \(d-\)primitive word. Acta Inform. 41, 171–180 (2004)MathSciNetCrossRefMATH

12.

Lothaire, M.: Combinatorics on Words, Encyclopedia of Mathematics and Its Applications. Addison Wesley Publishing Company, Boston (1983)MATH

13.

Markov, A.A.: An example of an independent system of words which cannot be included in a finite complete system. Math. Zametki 1, 87–90 (1967)MathSciNetMATH

14.

Restivo, A., Salemi, S., Sportelli, T.: Completing codes. RAIRO Theor. Inform. Appl. 23, 135–147 (1989)MathSciNetCrossRefMATH

15.

Spehner, J.-C.: Quelques problèmes d’extension, de conjugaison et de présentation des sous-monoïdes d’un monoïde libre. Université de Paris VII, Thèse de Doctorat d’État (1976)

16.

Spehner, J.-C.: Les présentations des sous-monoïdes de rang 3 d’un monoïde libre, Lecture Notes in Math. 855, Semigroups (Proc. Conf. Math. Res. Inst., Oberwolfach, 1978), pp. 116–155. Springer, Berlin (1981)

17.

Spehner, J.-C.: Les présentations des sous-monoïdes de rang 3 d’un monoïde libre: une correction. Publications Mathématiques 31, Université de Haute Alsace (1985)

18.

Shyr, H.J.: Free Monoids and Languages, 3rd edn. Hon Min Book Company, Taichung (2001)MATH

Title: The second step in characterizing a three-word code
Authors: Chunhua Cao
Jiao Xu
Lei Liao
Di Yang
Guichuan Jia
Qian Du
Publication date: 08-09-2023
Publisher: Springer Berlin Heidelberg
Published in: Acta Informatica / Issue 4/2023
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-023-00444-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2023

On first-order runtime enforcement of branching-time properties

Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms

Testing membership for timed automata

Editorial 2023: changes and invariants

Premium Partner