Reducing the local alphabet size in tiling systems by means of 2D comma-free codes

DOI10.1016/J.TCS.2022.09.010MaRDI QIDQ2676458zbMATH OpenOpenAlexFDO

Authors Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro

Publication date 27 September 2022

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

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

zbMATH Keywords

picture languagescomma-free codesMedvedev's theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Two-Dimensional Constrained Coding Based on Tiling
• Obtaining Binary Perfect Codes Out of Tilings
• On the structure of cube tiling codes
• Two-dimensional comma-free and cylindric codes
• scientific article; zbMATH DE number 7731171
• Graph encoding of 2D-gon tilings
• Bounds on the redundancy of binary alphabetical codes
• Two-dimensional weight-constrained codes through enumeration bounds
• Alphabet-almost-simple 2-neighbour-transitive codes

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3316963 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup
• Cellular automata complexity trade-offs
• Classifying regular events in symbolic logic
• Comma-Free Codes
• From regular to strictly locally testable languages
• Hall sets, Lazard sets and comma-free codes
• Homomorphic characterization of tree languages based on comma-free encoding
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Non-expandable non-overlapping sets of pictures
• On a question of McNaughton and Papert
• On the construction of comma-free codes
• Periodicity in rectangular arrays
• Properties of code events and homomorphisms over regular events
• Reducing local alphabet size in recognizable picture languages
• Regular languages as local functions with small alphabets
• Two-dimensional comma-free and cylindric codes
• Two-dimensional models

Cited in

(2)

• Regular languages as images of local functions over small alphabets
• From words to pictures: row-column combinations and Chomsky-Schützenberger theorem

This page was built for publication: Reducing the local alphabet size in tiling systems by means of 2D comma-free codes

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