Non-expandable non-overlapping sets of pictures

DOI10.1016/J.TCS.2016.09.025zbMATH Open1355.68298arXiv1605.09061OpenAlexW2529751054MaRDI QIDQ346246FDOQ346246

Authors: Marcella Anselmo, Dora Giammarresi, Maria Madonia 

Publication date: 5 December 2016

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

Abstract: The non-overlapping sets of pictures are sets such that no two pictures in the set (properly) overlap. They are the generalization to two dimensions of the cross-bifix-free sets of strings. Non-overlapping sets of pictures are non-expandable when no other picture can be added without violating the property. We present a construction of non-expandable non-overlapping (NENO) sets of pictures and show some examples of application.

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

Recommendations

• Sets of pictures avoiding overlaps
• Avoiding overlaps in pictures
• Nonmeasurable images
• Binary pictures with excluded patterns
• Image sets with regularity of differences
• Full sets of pictures to encode pictures
• Image sets of perfectly nonlinear maps
• Minimal non-deletable sets and minimal non-codeletable sets in binary images
• Non-partitionable point sets
• Non-overlapping matrices

zbMATH Keywords

cross-bifix-free sets of stringsnon-overlapping setsunbordered pictures

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• A logical approach to locality in pictures languages
• Two-dimensional prefix string matching and covering on square matrices
• A simple suboptimal construction of cross-bifix-free codes
• Multiset, Set and Numerically Decipherable Codes over Directed Figures
• Unbordered pictures: properties and construction
• A survey on picture-walking automata
• Picture codes
• Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages
• A note on bifix-free sequences (Corresp.)
• Picture codes and deciphering delay
• Prefix picture codes: a decidable class of two-dimensional codes
• A New Approach to Cross-Bifix-Free Sets
• Two dimensional prefix codes of pictures
• Cross-Bifix-Free Codes Within a Constant Factor of Optimality
• Restarting tiling automata
• A unifying approach to picture grammars
• Two-dimensional comma-free and cylindric codes
• Non-overlapping matrices
• A computational model for tiling recognizable two-dimensional languages

Cited In (10)

• Sets of pictures avoiding overlaps
• Reducing local alphabet size in recognizable picture languages
• The alphabetic complexity in homomorphic definitions of word, tree and picture languages
• Avoiding overlaps in pictures
• Non-symmetry and overlapping anti-packing representation with square sub-patterns
• A 2D non-overlapping code over a \(q\)-ary alphabet
• Non-overlapping matrices via Dyck words
• Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
• Density of \(k\)-ary words with 0, 1, 2-error overlaps
• Isometric words and edit distance: main notions and new variations

This page was built for publication: Non-expandable non-overlapping sets of pictures

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