Sökning: id:"swepub:oai:DiVA.org:umu-215936" >
Parsing unranked tr...
Parsing unranked tree languages, folded once
-
- Berglund, Martin, 1981- (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Björklund, Henrik (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Björklund, Johanna, 1961- (författare)
- Umeå universitet,Institutionen för datavetenskap
-
(creator_code:org_t)
- Springer Nature, 2023
- 2023
- Engelska.
-
Ingår i: Fundamentals of computation theory. - : Springer Nature. - 9783031435867 ; , s. 60-73
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 is 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 edges is discarded. We show that under these conditions, the problem is solvable in non-uniform polynomial time.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas