Uniform Parsing for Hyperedge Replacement Grammars [Elektronisk resurs]
-
Björklund, Henrik (författare)
-
Drewes, Frank (författare)
-
Ericson, Petter, 1986- (författare)
-
Starke, Florian (författare)
-
Foundations of Language Processing (medarbetare)
-
Foundations of Language Processing (medarbetare)
-
Umeå universitet Teknisk-naturvetenskapliga fakulteten (utgivare)
- Publicerad: Elsevier, 2021
- Engelska.
-
Ingår i: Journal of computer and system sciences (Print). - 0022-0000. ; 118, 1-27
-
Läs hela texten
-
Läs hela texten
-
Läs hela texten
- Relaterad länk:
-
http://www.umu.se/ (Värdpublikation)
Sammanfattning
Ämnesord
Stäng
- It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomial-time algorithm that solves the uniform parsing problem for a restricted type of hyperedge-replacement grammars which we expect to be of interest for practical applications.
Ämnesord
- Natural Sciences (hsv)
- Computer and Information Sciences (hsv)
- Computer Sciences (hsv)
- Naturvetenskap (hsv)
- Data- och informationsvetenskap (hsv)
- Datavetenskap (datalogi) (hsv)
- Computer Science (umu)
- datalogi (umu)
Genre
- government publication (marcgt)
Indexterm och SAB-rubrik
- parsing
- graph language
- graph grammar
- abstract meaning representation
Inställningar
Hjälp
Ingår i annan publikation. Gå till titeln
Journal of computer and system sciences (Print)