Abstract
Straight-line (linear) context-free tree (slt) grammars have been used to compactly represent ordered trees. Equivalence of slt grammars is decidable in polynomial time. Here we extend this result and show that isomorphism of unordered trees given as slt grammars is decidable in polynomial time. The result generalizes to isomorphism of unrooted trees and bisimulation equivalence. For non-linear slt grammars which can have double-exponential compression ratios, we prove that unordered isomorphism and bisimulation equivalence are \(\textsc {pspace}\)-hard and in \(\textsc {exptime}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)
Balcázar, J., Gabarró, J., Sántha, M.: Deciding bisimilarity is P-complete. Formal Aspects of Computing 4, 638–648 (1992)
Brenguier, R., Göller, S., Sankur, O.: A comparison of succinctly represented finite-state systems. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 147–161. Springer, Heidelberg (2012)
Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst. 33(4–5), 456–474 (2008)
Buss, S.R.: Alogtime algorithms for tree isomorphism, comparison, and canonization. Kurt Gödel Colloquium 97, 18–33 (1997)
Charikar, M., Lehman, E., Lehman, A., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554–2576 (2005)
Das, B., Scharpfenecker, P., Torán, J.: Succinct encodings of graph isomorphism. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 285–296. Springer, Heidelberg (2014)
Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Contr. 56, 183–198 (1983)
Jenner, B., Köbler, J., McKenzie, P., Torán, J.: Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3), 549–566 (2003)
Lengauer, T., Wagner, K.W.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63–93 (1992)
Lindell, S.: A logspace algorithm for tree canonization (extended abstract). In: Proc. STOC 1992, pp. 400–404. ACM (1992)
Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complexity Cryptology 4(2), 241–299 (2012)
Lohrey, M., Maneth, S., Peternek, F.: Compressed tree canonization (2015). arXiv.org http://arxiv.org/abs/1502.04625
Lohrey, M., Maneth, S., Schmidt-Schauß, M.: Parameter reduction and automata evaluation for grammar-compressed trees. J. Comput. Syst. Sci. 78(5), 1651–1669 (2012)
Lohrey, M., Mathissen, C.: Isomorphism of regular trees and words. Inf. Comput. 224, 71–105 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lohrey, M., Maneth, S., Peternek, F. (2015). Compressed Tree Canonization. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)