16 citations · 21 across the 3 of their papers we have counts for
3 papers
cs.FL2011★ 5 cited
Isomorphism of regular trees and words
Markus Lohrey, Christian Mathissen
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…
math.GR2010
Compressed conjugacy and the word problem for outer automorphism groups of graph groups
Niko Haubold, Markus Lohrey, Christian Mathissen
It is shown that for graph groups (right-angled Artin groups) the conjugacy problem as well as a restricted version of the simultaneous conjugacy problem can be solved in polynomia…
cs.LO2010★ 16 cited
Weighted Logics for Nested Words and Algebraic Formal Power Series
Christian Mathissen
Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study neste…