Cross-bifix-free sets generation via Motzkin paths
Barcucci, Elena1 ; Bilotta, Stefano1 ; Pergola, Elisa1 ; Pinzani, Renzo1 ; Succi, Jonathan1
1 Dipartimento di Matematica e Informatica “U.Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65, 50134 Firenze, Italy
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 81-91.

Cross-bifix-free sets are sets of words such that no proper prefix of any word is a proper suffix of any other word. In this paper, we introduce a general constructive method for the sets of cross-bifix-free q-ary words of fixed length. It enables us to determine a cross-bifix-free words subset which has the property to be non-expandable.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016008
Classification : 68R05, 68P30
Mots-clés : Codes, Motzkin paths
Barcucci, Elena 1 ; Bilotta, Stefano 1 ; Pergola, Elisa 1 ; Pinzani, Renzo 1 ; Succi, Jonathan 1

1 Dipartimento di Matematica e Informatica “U.Dini”, Università degli Studi di Firenze, Viale G.B. Morgagni 65, 50134 Firenze, Italy 
@article{ITA_2016__50_1_81_0,
     author = {Barcucci, Elena and Bilotta, Stefano and Pergola, Elisa and Pinzani, Renzo and Succi, Jonathan},
     title = {Cross-bifix-free sets generation via {Motzkin} paths},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {81--91},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ita/2016008},
     zbl = {1371.68219},
     mrnumber = {3518160},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2016008/}
}
TY  - JOUR
AU  - Barcucci, Elena
AU  - Bilotta, Stefano
AU  - Pergola, Elisa
AU  - Pinzani, Renzo
AU  - Succi, Jonathan
TI  - Cross-bifix-free sets generation via Motzkin paths
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 81
EP  - 91
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2016008/
DO  - 10.1051/ita/2016008
LA  - en
ID  - ITA_2016__50_1_81_0
ER  - 
%0 Journal Article
%A Barcucci, Elena
%A Bilotta, Stefano
%A Pergola, Elisa
%A Pinzani, Renzo
%A Succi, Jonathan
%T Cross-bifix-free sets generation via Motzkin paths
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 81-91
%V 50
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2016008/
%R 10.1051/ita/2016008
%G en
%F ITA_2016__50_1_81_0
Barcucci, Elena; Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo; Succi, Jonathan. Cross-bifix-free sets generation via Motzkin paths. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 81-91. doi : 10.1051/ita/2016008. http://archive.numdam.org/articles/10.1051/ita/2016008/

M. Aigner, Motzkin numbers. Eur. J. Combin. 19 (1998) 663–675. | DOI | MR | Zbl

D. Bajic, On construction of cross-bifix-free kernel sets, in Proc. of Conference on 2nd MCM COST 2100 (2007) TD(07)237.

D. Bajic and T. Loncar-Turukalo, A simple suboptimal construction of cross-bifix-free codes. Cryptogr. Commun. 6 (2014) 27–37. | DOI | Zbl

D. Bajic and J. Stojanovic, Distributed sequences and search process, in Proc. of IEEE International Conference on Communications ICC 2004 (2004) 514–518.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for enumerating k-coloured Motzkin paths. Lect. Notes Comput. Sci. 959 (1995) 254–263. | DOI | MR

R.H. Barker, Group Synchronizing of Binary Digital Systems, Communication theory, London, Butterworth (1953) 273–287.

J. Berstel, D. Perrin and C. Reutenauer, Codes and Automata. Encycl. Math. Appl. Cambridge University Press (2009). | MR | Zbl

S. Bilotta, E. Grazzini, E. Pergola and R. Pinzani, Avoiding cross-bifix-free binary words. Acta Inform. 50 (2013) 157–173. | DOI | MR | Zbl

S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets. IEEE Trans. Inform. Theory 58 (2012) 4058–4063. | DOI | MR | Zbl

S. Blackburn. Non-overlapping codes. IEEE Trans. Inform. Theory 61 (2015) 4890–4894. | DOI | MR | Zbl

Y.M. Chee, H.M. Kiah, P. Purkayastha and C. Wang, Cross-bifix-free codes within a constant factor of optimality. IEEE Trans. Inform. Theory 59 (2013) 4668–4674. | DOI | MR | Zbl

M. Crochemore, C. Hancart and T. Lecroq, Algorithms on Strings. Cambridge University Press (2007). | MR | Zbl

A.J. De Lind Van Wijngaarden and T.J. Willink, Frame Synchronization Using Distributed Sequences. IEEE Trans. Commun. 48 (2000) 2127–2138. | DOI

V.I. Levenshtein, Maximun number of words in codes without overlaps. Probl. Inf. Transm. 6 (1970) 355–357. | MR | Zbl

C. Levesque, On mth order linear recurrences. Fibonacci Quart. 23 (1985) 290–293. | MR | Zbl

J. Lindner, Binary sequences up to length 40 with best possible autocorrelation function. Electron. Lett. 11 (1975) 507. | DOI

P.T. Nielsen, On the expected duration of a search for a fixed pattern in random data. IEEE Trans. Inform. Theory 29 (1973) 702–704. | DOI | MR | Zbl

P.T. Nielsen. A note on bifix-free sequences. IEEE Trans. Inform. Theory 29 (1973) 704–706. | DOI | MR | Zbl

A. Sapounakis and P. Tsikouras, On k-colored Motzkin words. J. Integer Seq. 7 (2004) 04.2.5. | MR | Zbl

R.A. Scholtz, Frame synchronization techniques. IEEE Trans. Commun. 20 (1980) 1204–1213. | DOI

Cité par Sources :