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
Z-Automata for Compact and Direct Representation of Unranked Tree Languages
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
University of Padova, Italy.
2019 (Engelska)Ingår i: Implementation and Application of Automata: 24th International Conference, CIAA 2019 Košice, Slovakia, July 22–25, 2019, Proceedings / [ed] Michal Hospodár, Galina Jirásková, Springer, 2019, s. 83-94Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Unranked tree languages are valuable in natural language processing for modelling dependency trees. We introduce a new type of automaton for unranked tree languages, called Z-automaton, that is tailored for this particular application. The Z-automaton offers a compact form of representation, and unlike the closely related notion of stepwise automata, does not require a binary encoding of its input. We establish an arc-factored normal form, and prove the membership problem of Z-automata in normal form to be in O(mn), where m is the size of the transition table of the Z-automaton and n is the size of the input tree.

Ort, förlag, år, upplaga, sidor
Springer, 2019. s. 83-94
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11601
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-158624DOI: 10.1007/978-3-030-23679-3_7ISBN: 978-3-030-23678-6 (tryckt)ISBN: 978-3-030-23679-3 (digital)OAI: oai:DiVA.org:umu-158624DiVA, id: diva2:1313403
Konferens
Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019
Tillgänglig från: 2019-05-03 Skapad: 2019-05-03 Senast uppdaterad: 2019-10-29Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Björklund, JohannaDrewes, Frank

Sök vidare i DiVA

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

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 519 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