Martin Berglund
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Martin Berglund has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Brink van der Merwe
Stellenbosch University
5 shared publications Brink van der Merwe
3 shared publications- Henrik Björklund
Umeå University
3 shared publications - Johanna Björklund
Department of Computing Science, Umeå University, Umeå, Sweden
2 shared publications - Willeke Martens
Umeå University
2 shared publications - Anna Jonsson
Umeå University
1 shared publication
Latest Publications
- Open Access
- 23 June 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1083
Constructing a BPE tokenization DFA
- 23 June 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1083
Open AccessConstructing a BPE tokenization DFA
- 23 August 2025
- Published by Springer Nature
- p. 27-40
Constructing Compact BPE Token DFAs
- Open Access
- 19 June 2024
- Published by MDPI AG in Algorithms
- Vol. 17 (6) , 268
Parsing Unranked Tree Languages, Folded Once
A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.
- 19 June 2024
- Published by MDPI AG in Algorithms
- Vol. 17 (6) , 268
Open AccessParsing Unranked Tree Languages, Folded Once
A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.
- 21 September 2023
- Published by Springer Nature
- p. 60-73
Parsing Unranked Tree Languages, Folded Once
- Open Access
- 15 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 388, 16-27
Formalizing BPE Tokenization
In this paper, we formalize practical byte pair encoding tokenization as it is used in large language models and other NLP systems, in particular we formally define and investigate the semantics of the SentencePiece and HuggingFace tokenizers, in particular how they relate to each other, depending on how the tokenization rules are constructed. Beyond this we consider how tokenization can be performed in an incremental fashion, as well as doing it left-to-right using an amount of memory constant in the length of the string, enabling e.g. using a finite state string-to-string transducer.
- 15 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 388, 16-27
Open AccessFormalizing BPE Tokenization
In this paper, we formalize practical byte pair encoding tokenization as it is used in large language models and other NLP systems, in particular we formally define and investigate the semantics of the SentencePiece and HuggingFace tokenizers, in particular how they relate to each other, depending on how the tokenization rules are constructed. Beyond this we consider how tokenization can be performed in an incremental fashion, as well as doing it left-to-right using an amount of memory constant in the length of the string, enabling e.g. using a finite state string-to-string transducer.
- 15 October 2018
- Published by Springer Nature
- p. 99-115
Formalising Boost POSIX Regular Expression Matching
- 15 October 2018
- Published by Springer Nature
- p. 99-115
Formalising Boost POSIX Regular Expression Matching
- 1 May 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 679, 69-82
On the semantics of regular expression parsing in the wild
- 1 May 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 679, 69-82
On the semantics of regular expression parsing in the wild
- Open Access
- 11 May 2016
- Published by MDPI AG in Algorithms
- Vol. 9 (2) , 32
Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.
- 11 May 2016
- Published by MDPI AG in Algorithms
- Vol. 9 (2) , 32
Open AccessUniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.