Umeå University's logo

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

Direct link
Referera
Referensformat
  • apa
  • ieee
  • 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
Constructing a BPE tokenization DFA
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-3692-6994
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Department of Computer Science, Stellenbosch University, Stellenbosch, South Africa; National Institute for Theoretical and Computational Sciences, Stellenbosch, South Africa.
2026 (engelsk)Inngår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 1083, artikkel-id 116131Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficient construction of deterministic finite automata (DFA) designed to operate directly on tokenizations produced by the popular byte pair encoding (BPE) technique. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways. The construction preserves some key properties of the automaton, and we use this to establish asymptotic bounds on the state complexity of the automata that result. Finally, we demonstrate how to construct an input-deterministic (subsequential) string-to-string transducer which precisely describes the relationship between strings and their correct tokenizations.

sted, utgiver, år, opplag, sider
Elsevier, 2026. Vol. 1083, artikkel-id 116131
Emneord [en]
Automata theory, Byte pair encoding, Tokenization
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-257600DOI: 10.1016/j.tcs.2026.116131ISI: 001815056100001Scopus ID: 2-s2.0-105043575844OAI: oai:DiVA.org:umu-257600DiVA, id: diva2:2092282
Forskningsfinansiär
Wallenberg AI, Autonomous Systems and Software Program (WASP)Tilgjengelig fra: 2026-08-14 Laget: 2026-08-14 Sist oppdatert: 2026-08-14bibliografisk kontrollert

Open Access i DiVA

fulltext(2530 kB)22 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 2530 kBChecksum SHA-512
f4d17cb40cc455b04158e71078697726f2e8b1a565b172cacf78d72eab2b771cf8752b55e5fa634106f65d5f40b3b8d6526f6565fbf4c28e5d1bceb0d95de58d
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Berglund, MartinMartens, Willeke

Søk i DiVA

Av forfatter/redaktør
Berglund, MartinMartens, Willeke
Av organisasjonen
I samme tidsskrift
Theoretical Computer Science

Søk utenfor DiVA

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

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 1411 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • 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