umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Z-Automata for Compact and Direct Representation of Unranked Tree Languages
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
University of Padova, Italy.
2019 (English)In: 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, p. 83-94Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
Springer, 2019. p. 83-94
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11601
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-158624DOI: 10.1007/978-3-030-23679-3_7ISBN: 978-3-030-23678-6 (print)ISBN: 978-3-030-23679-3 (electronic)OAI: oai:DiVA.org:umu-158624DiVA, id: diva2:1313403
Conference
Implementation and Application of Automata - 24th International Conference (CIAA 2019), Slovakia, July 22-25, 2019
Available from: 2019-05-03 Created: 2019-05-03 Last updated: 2019-10-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Björklund, JohannaDrewes, Frank

Search in DiVA

By author/editor
Björklund, JohannaDrewes, Frank
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 332 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf