Tree indexing by pushdown automata and subtree repeats

Tomáš Flouri*, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problem of finding all subtree repeats in a given unranked ordered tree. We show a new, elegant, and simple method, which is based on the construction of a tree indexing structure called the subtree pushdown automaton. We propose a solution for computing all subtree repeats from the deterministic subtree pushdown automaton constructed over the subject tree. The method we present is directly analogous to the relationship between string deterministic suffix automata and factor repeats in a given string.

Original languageEnglish
Title of host publication2011 Federated Conference on Computer Science and Information Systems, FedCSIS 2011
Pages899-902
Number of pages4
Publication statusPublished - 14 Dec 2011
Externally publishedYes
Event2011 Federated Conference on Computer Science and Information Systems, FedCSIS 2011 - Szczecin, Poland
Duration: 18 Sep 201121 Sep 2011

Publication series

Name2011 Federated Conference on Computer Science and Information Systems, FedCSIS 2011

Conference

Conference2011 Federated Conference on Computer Science and Information Systems, FedCSIS 2011
Country/TerritoryPoland
CitySzczecin
Period18/09/1121/09/11

Cite this