Homomorphic definitions of tree languages via comma-free tree codes

MaRDI QIDQ6894348zbMATH OpenFDO

Authors Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date 25 November 2025

Published in Journal of Automata, Languages and Combinatorics (Search for Journal in Brave)

Full work available at URL https://jalc.de/issues/2025/issue_30_1-3/jalc-2025-049-076.php

zbMATH Keywords

comma-free tree codesMedvedev's theoremminimal alphabetregular tree languagesstrict local testability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Prefix, length-variable, comma-free codes (94A45)

Cites work

• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup
• A decidable characterization of locally testable tree languages
• A medvedev characterization of sets recognized by generalized finite automata
• Codes and equations on trees
• Comma-Free Codes
• From regular to strictly locally testable languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Homomorphic characterization of tree languages based on comma-free encoding
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 475410 (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?)
• Language theoretic properties of regular DAG languages
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• On the construction of comma-free codes
• Properties of code events and homomorphisms over regular events
• Reducing the local alphabet size in tiling systems by means of 2D comma-free codes

This page was built for publication: Homomorphic definitions of tree languages via comma-free tree codes

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