Inexact tree pattern matching with 1-degree edit distance using finite automata

DOI10.1016/J.DAM.2023.01.003MaRDI QIDQ2689648zbMATH OpenOpenAlexFDO

Authors Eliška Šestáková, Ondřej Guth, Jan Janoušek

Publication date 13 March 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.01.003

zbMATH Keywords

1-degree edit distanceapproximate tree pattern matchingdynamic programmingfinite automatoninexact tree pattern matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 826058
• A constrained edit distance between unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• An efficient algorithm for some tree matching problems
• Efficient exponential time algorithms for edit distance between unordered trees

Cites work

• A full and linear index of a tree for tree patterns
• An optimal decomposition algorithm for tree edit distance
• On the editing distance between unordered labeled trees
• The Tree-to-Tree Correction Problem
• The tree-to-tree editing problem
• Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)

Cited in

(2)

• scientific article; zbMATH DE number 4135424 (Why is no real title available?)
• Approximate matching of XML document with regular hedge grammar

This page was built for publication: Inexact tree pattern matching with 1-degree edit distance using finite automata

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