Parsing Unranked Tree Languages, Folded Once
Open Access
- 19 June 2024
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 17 (6) , 268
Abstract
A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.Keywords
Funding Information
- Vetenskapsrådet (2020-03852)
- Knut and Alice Wallenberg Foundation (2020-03852)
This publication has 15 references indexed in Scilit:
- Transduction from trees to graphs through foldingInformation and Computation, 2023
- Reachability in Vector Addition Systems is Ackermann-complete2022
- Graph Mining Applications to Social Network Analysis2010
- Database Programming Languages2005
- Generation that exploits corpus-based statistical knowledge1998
- The complexity of graph languages generated by hyperedge replacementActa Informatica, 1990
- A flexible interface for linking applications to Penman's sentence generator1989
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987
- Complexity of some problems in Petri netsTheoretical Computer Science, 1977
- Parallel program schemataJournal of Computer and System Sciences, 1969