Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A bottom-up automaton for tree adjoining languages
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-8722-5661
2015 (engelsk)Rapport (Annet vitenskapelig)
Abstract [en]

Current tree parsing algorithms for nonregular tree languages all have superlinear running times, possibly limiting their practical applicability. We present a bottom-up tree automaton that captures exactly the tree-adjoining languages in the non-deterministic case. The determinstic case captures a strict superset of the regular tree languages, while preserving running times linear in the size of the tree.

sted, utgiver, år, opplag, sider
Umeå: Umeå universitet , 2015. , s. 7
Serie
Report / UMINF, ISSN 0348-0542 ; 15.14
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-134999OAI: oai:DiVA.org:umu-134999DiVA, id: diva2:1095714
Tilgjengelig fra: 2017-05-15 Laget: 2017-05-15 Sist oppdatert: 2018-06-09bibliografisk kontrollert
Inngår i avhandling
1. Complexity and expressiveness for formal structures in Natural Language Processing
Åpne denne publikasjonen i ny fane eller vindu >>Complexity and expressiveness for formal structures in Natural Language Processing
2017 (engelsk)Licentiatavhandling, med artikler (Annet vitenskapelig)
Abstract [en]

The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. Our research studies formal systems working not just on strings, but on more complex structures such as trees and graphs, in particular syntax trees and semantic graphs. The field of mildly context-sensitive languages concerns attempts to find a useful class of formal languages between the context-free and context-sensitive. We study formalisms defining two candidates for this class; tree-adjoining languages and the languages defined by linear context-free rewriting systems. For the former, we specifically investigate the tree languages, and define a subclass and tree automaton with linear parsing complexity. For the latter, we use the framework of parameterized complexity theory to investigate more deeply the related parsing problems, as well as the connections between various formalisms defining the class. The field of semantic modelling aims towards formally and accurately modelling not only the syntax of natural language statements, but also the meaning. In particular, recent work in semantic graphs motivates our study of graph grammars and graph parsing. To the best of our knowledge, the formalism presented in Paper III of this thesis is the first graph grammar where the uniform parsing problem has polynomial parsing complexity, even for input graphs of unbounded node degree.

sted, utgiver, år, opplag, sider
Umeå: Umeå Universitet, 2017. s. 18
Serie
Report / UMINF, ISSN 0348-0542 ; 17.13
Emneord
graph grammars, formal languages, natural language processing, parameterized complexity, abstract meaning representation, tree automata, deterministic tree-walking transducers, mildly context-sensitive languages, hyperedge replacement, tree adjoining languages, minimally adequate teacher
HSV kategori
Identifikatorer
urn:nbn:se:umu:diva-135014 (URN)9789176017227 (ISBN)
Presentation
2017-05-19, MA121, MIT-huset 901 87 Umeå, Umeå, 10:15 (engelsk)
Veileder
Tilgjengelig fra: 2017-05-17 Laget: 2017-05-16 Sist oppdatert: 2018-06-09bibliografisk kontrollert

Open Access i DiVA

fulltext(212 kB)259 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 212 kBChecksum SHA-512
5331d9733cc4aa952edcb583ac65c296b0f96c58f8dbe25009baa85c9be1381c4ea5bd2670e4a15a6ed2acb4d52872bd72a5b3bdc5cc52c00eb1e808111c99d6
Type fulltextMimetype application/pdf

Andre lenker

URL

Person

Ericson, Petter

Søk i DiVA

Av forfatter/redaktør
Ericson, Petter
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 259 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 510 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf