Isomorphism of regular trees and words

DOI10.1007/978-3-642-22012-8_16MaRDI QIDQ3012921zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Christian Mathissen

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

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

Abstract: The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be EXPTIME-complete (resp. P-complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be PSPACE-complete (resp. P-complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Esik and Bloom.

Recommendations

• Isomorphism of regular trees and words
• The isomorphism problem for tree-automatic ordinals with addition
• The isomorphism problem on classes of automatic structures with transitive relations
• Automatic linear orders and trees
• scientific article; zbMATH DE number 2053214

Cites work

• Algebraic linear orderings
• Alternation
• An undecidable property of context-free linear orders
• Automata, Languages and Programming
• Automatic Structures: Richness and Limitations
• CCS expressions, finite state processes, and three problems of equivalence
• Completeness results for graph isomorphism.
• scientific article; zbMATH DE number 3675332 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639170 (Why is no real title available?)
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• scientific article; zbMATH DE number 1929935 (Why is no real title available?)
• scientific article; zbMATH DE number 1418326 (Why is no real title available?)
• Isomorphism of regular trees and words
• On frontiers of regular trees
• Processing Compressed Texts: A Tractability Border
• The equational theory of regular words

Cited in

(4)

• Isomorphism of regular trees and words
• The isomorphism problem on classes of automatic structures with transitive relations
• scientific article; zbMATH DE number 2053214 (Why is no real title available?)
• Isomorphism Types of Trees

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

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