Isomorphism of regular trees and words

DOI10.1016/j.ic.2013.01.002zbMath1295.68124OpenAlexW2554299284MaRDI QIDQ1951601

Markus Lohrey, Christian Mathissen

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.01.002

zbMATH Keywords

computational complexityregular treesfinite automataregular languagesautomatic structuresregular wordsisomorphism problemsgeneralized words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computable structure theory, computable model theory (03C57)

Related Items (9)

Compressed Tree Canonization ⋮ Grammar-Based Tree Compression ⋮ Processing succinct matrices and vectors ⋮ Isomorphisms of scattered automatic linear orders ⋮ The Order Type of Scattered Context-Free Orderings of Rank One Is Computable ⋮ Tree compression using string grammars ⋮ Isomorphism of Regular Trees and Words ⋮ Pro-aperiodic monoids via saturated models ⋮ The ordinal generated by an ordinal grammar is computable

This page was built for publication: Isomorphism of regular trees and words