umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A note on the complexity of deterministic tree-walking transducers
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-8722-5661
2013 (Engelska)Ingår i: Non-Classical Models of Automata and Applications (NCMA 2013), Österreichische Computer Gesellschaft , 2013Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Österreichische Computer Gesellschaft , 2013.
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-79716OAI: oai:DiVA.org:umu-79716DiVA, id: diva2:644031
Konferens
Non-Classical Models of Automata and Applications (NCMA 2013), August 13 - 14, 2013, Umeå, Sweden
Forskningsfinansiär
Vetenskapsrådet, 621-2011-6080Tillgänglig från: 2013-08-29 Skapad: 2013-08-29 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
Ingår i avhandling
1. Complexity and expressiveness for formal structures in Natural Language Processing
Öppna denna publikation i ny flik eller fönster >>Complexity and expressiveness for formal structures in Natural Language Processing
2017 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå Universitet, 2017. s. 18
Serie
Report / UMINF, ISSN 0348-0542 ; 17.13
Nyckelord
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
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-135014 (URN)9789176017227 (ISBN)
Presentation
2017-05-19, MA121, MIT-huset 901 87 Umeå, Umeå, 10:15 (Engelska)
Handledare
Tillgänglig från: 2017-05-17 Skapad: 2017-05-16 Senast uppdaterad: 2018-06-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Björklund, HenrikEricson, Petter

Sök vidare i DiVA

Av författaren/redaktören
Björklund, HenrikEricson, Petter
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 772 träffar
RefereraExporteraLänk till posten
Permanent länk

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