Isomorphism of Regular Trees and Words

DOI10.1007/978-3-642-22012-8_16zbMath1333.68126arXiv1102.2782MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68R15: Combinatorics on words

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03C57: Computable structure theory, computable model theory

Related Items

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