Inferring strings from position heaps in linear time

DOI10.1007/978-3-031-27051-2_11MaRDI QIDQ6091154zbMATH OpenFDO

Authors Koshiro Kumagai, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Publication date 24 November 2023

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.12405

zbMATH Keywords

enumerationposition heapsreverse engineering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This paper is concerned with variants of the inverse problem of position heap construction and gives linear-time algorithms for those problems. The basic problem is to restore a text string from a rooted tree with labeled edges and numbered nodes. In the variant problems, the input trees may miss edge labels or node numbers which we must restore as well.

Cites work

• A fast string searching algorithm
• Algorithms on Strings, Trees and Sequences
• Border array on bounded alphabet
• Complete inverted files for efficient text retrieval and analysis
• Efficient validation and construction of border arrays and validation of string matching automata
• Eulerian graphs and related topics. Part 1, Volume 1
• Fast Pattern Matching in Strings
• Finding All Spanning Trees of Directed and Undirected Graphs
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 1774199 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• Inferring strings from suffix trees and links on a binary alphabet
• Mathematical Foundations of Computer Science 2003
• On-line construction of position heaps
• Position heaps: a simple and dynamic text indexing data structure
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Reverse engineering prefix tables
• String inference from longest-common-prefix array
• Suffix Arrays: A New Method for On-Line String Searches
• The nature of computation
• The smallest automaton recognizing the subwords of a text
• Words over an ordered alphabet and suffix permutations

This page was built for publication: Inferring strings from position heaps in linear time

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