Non-overlapping matrices

DOI10.1016/J.TCS.2016.05.009MaRDI QIDQ728263zbMATH OpenOpenAlexFDO

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

Publication date 19 December 2016

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

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

zbMATH Keywords

bidimensional codenon-overlapping matricesunbordered matrices

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computing methodologies for image processing (68U10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: Two matrices are said non-overlapping if one of them can not be put on the other one in a way such that the corresponding entries coincide. We provide a set of non-overlapping binary matrices and a formula to enumerate it which involves the $k$-generalized Fibonacci numbers. Moreover, the generating function for the enumerating sequence is easily seen to be rational.

Recommendations

• Non-overlapping matrices via Dyck words
• A 2D non-overlapping code over a q-ary alphabet
• Binary vectors with exactly k nonoverlapping m-tuples of consecutive ones
• scientific article; zbMATH DE number 2039061
• Binary matrices

Cites work

• scientific article; zbMATH DE number 2186901 (Why is no real title available?)
• scientific article; zbMATH DE number 2016134 (Why is no real title available?)
• A New Approach to Cross-Bifix-Free Sets
• A note on bifix-free sequences (Corresp.)
• A simple suboptimal construction of cross-bifix-free codes
• Cross-Bifix-Free Codes Within a Constant Factor of Optimality
• Non-Overlapping Codes
• Structure and measure of a decidable class of two-dimensional codes
• Two-dimensional prefix string matching and covering on square matrices
• Two-dimensional rational automata: a bridge unifying one- and two-dimensional language theory
• Unbordered pictures: properties and construction

Cited in

(5)

• Sets of pictures avoiding overlaps
• 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
• Non-expandable non-overlapping sets of pictures

This page was built for publication: Non-overlapping matrices

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