A bidimensional bifix (in short bibifix) of a square matrix T is a square submatrix of T which occurs in the top-left and bottom-right corners of T. This allows us to extend the definition of bifix-free words and cross-bifix-free set of words to bidimensional structures. In this paper we exhaustively generate all the bibifix-free square matrices and we construct a particular non-expandable cross- bibifix-free set of square matrices. Moreover, we provide a Gray code for listing this set.

Cross-bifix-free sets in two dimensions / Barcucci, Elena; Bernini, Antonio; Bilotta, Stefano; Pinzani, Renzo. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 664:(2017), pp. 29-38. [10.1016/j.tcs.2015.08.032]

Cross-bifix-free sets in two dimensions

BARCUCCI, ELENA;BERNINI, ANTONIO;BILOTTA, STEFANO;PINZANI, RENZO
2017

Abstract

A bidimensional bifix (in short bibifix) of a square matrix T is a square submatrix of T which occurs in the top-left and bottom-right corners of T. This allows us to extend the definition of bifix-free words and cross-bifix-free set of words to bidimensional structures. In this paper we exhaustively generate all the bibifix-free square matrices and we construct a particular non-expandable cross- bibifix-free set of square matrices. Moreover, we provide a Gray code for listing this set.
2017
664
29
38
Barcucci, Elena; Bernini, Antonio; Bilotta, Stefano; Pinzani, Renzo
File in questo prodotto:
File Dimensione Formato  
BiBifixFree_submitted.pdf

accesso aperto

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 359.25 kB
Formato Adobe PDF
359.25 kB Adobe PDF
1-s2.0-S0304397515007793-main.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 310.03 kB
Formato Adobe PDF
310.03 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1014695
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact