Cross-bifix-free sets in two dimensions

DOI10.1016/J.TCS.2015.08.032zbMATH Open1359.68157arXiv1502.05275OpenAlexW2963395384MaRDI QIDQ517032FDOQ517032

Authors: Elena Barcucci, Antonio Bernini, S. Bilotta, R. Pinzani 

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1502.05275

Recommendations

• Cross-bifix-free sets generation via Motzkin paths
• A simple suboptimal construction of cross-bifix-free codes
• Avoiding cross-bifix-free binary words

zbMATH Keywords

Gray codeexhaustive generationbidimensional code

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Title not available (Why is that?)
• Algorithms on Strings
• Two-dimensional prefix string matching and covering on square matrices
• A note on bifix-free sequences (Corresp.)
• A New Approach to Cross-Bifix-Free Sets
• Cross-Bifix-Free Codes Within a Constant Factor of Optimality
• Title not available (Why is that?)
• On Generating the N-ary Reflected Gray Codes
• Avoiding cross-bifix-free binary words
• Two-dimensional rational automata: a bridge unifying one- and two-dimensional language theory

Cited In (7)

• Sets of pictures avoiding overlaps
• A simple suboptimal construction of cross-bifix-free codes
• A 2D non-overlapping code over a \(q\)-ary alphabet
• Non-overlapping matrices via Dyck words
• A Construction for Variable Dimension Strong Non-Overlapping Matrices
• Cross-bifix-free sets generation via Motzkin paths
• Characterization and measure of infinite two-dimensional strong prefix codes

This page was built for publication: Cross-bifix-free sets in two dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517032)