Non-expandable non-overlapping sets of pictures

DOI10.1016/J.TCS.2016.09.025MaRDI QIDQ346246zbMATH OpenOpenAlexFDO

Authors Marcella Anselmo, Dora Giammarresi, Maria Madonia

Publication date 5 December 2016

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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.

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

Cites work

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

Cited in

(10)

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

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)