Sökning: onr:"swepub:oai:DiVA.org:umu-153394" >
Minimisation and Ch...
Minimisation and Characterisation of Order-Preserving DAG Grammars
-
- Björklund, Henrik (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Björklund, Johanna (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Ericson, Petter, 1986- (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
(creator_code:org_t)
- Umeå : Umeå University, 2018
- Engelska 19 s.
-
Serie: Report / UMINF, 0348-0542 ; 18.15
- Relaterad länk:
-
https://webapps.cs.u...
-
visa fler...
-
https://umu.diva-por... (primary) (Raw object)
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- Order-preserving DAG grammars (OPDGs) is a formalism for processing semantic infor- mation in natural languages [5, 4]. OPDGs are sufficiently expressive to model abstract meaning representations, a graph-based form of semantic representation in which nodes en- code objects and edges relations. At the same time, they allow for efficient parsing in the uniform setting, where both the grammar and subject graph are taken as part of the input.In this article, we introduce an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars. This makes it possible to transfer a number of results from that domain to OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable in the so-called MAT setting. To conclude, we show that the languages generated by OPDGs are MSO-definable.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- graph grammars
- minimally adequate teacher
- order preservation
- weighted graph grammars
- weighted learning
- business data processing
- administrativ databehandling
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)