Isomorphism of Regular Trees and Words

DOI10.1007/978-3-642-22012-8_16zbMath1333.68126arXiv1102.2782OpenAlexW2156773558MaRDI QIDQ3012921

Christian Mathissen, Markus Lohrey

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

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 (1)

The isomorphism problem on classes of automatic structures with transitive relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• CCS expressions, finite state processes, and three problems of equivalence
• Completeness results for graph isomorphism.
• The equational theory of regular words
• An undecidable property of context-free linear orders
• Isomorphism of regular trees and words
• ALGEBRAIC LINEAR ORDERINGS
• Processing Compressed Texts: A Tractability Border
• On frontiers of regular trees
• Alternation
• Automatic Structures: Richness and Limitations
• Automata, Languages and Programming

This page was built for publication: Isomorphism of Regular Trees and Words