Metraipolis › archive › dc_2fbe547c718d

Translation of Regular Expression with Lookahead into Finite State Automaton — arXiv:2608.03167

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.03167
License (as archived)
CC0-1.0
Archived
2026-10-31T13:10:35.567Z
SHA-256 of the archived text
0f051ea912910cb171cee24c6423452b576b075a1ac614a7bae3142cc8be0ad4
Stable URL of this page
https://metraipolis.com/documento/dc_2fbe547c718d

How to cite

Translation of Regular Expression with Lookahead into Finite State Automaton — arXiv:2608.03167 — arXiv (en), https://arxiv.org/abs/2608.03167 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2fbe547c718d (Metraipolis archive dc_2fbe547c718d, sha256 0f051ea912910cb171cee24c6423452b576b075a1ac614a7bae3142cc8be0ad4)
BibTeX
@misc{dc2fbe547c718d,
  title = {Translation of Regular Expression with Lookahead into Finite State Automaton — arXiv:2608.03167},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03167},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2fbe547c718d; sha256 0f051ea912910cb171cee24c6423452b576b075a1ac614a7bae3142cc8be0ad4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03167. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Most of the conventional implementations of regular expressions are based on backtracking. Such implementations are slow in the worst case, and thus, we would like to develop a better matching algorithm. However, it is nontrivial to provide an efficient matching algorithm that can deal with practical extensions including submatch addressing. This paper studies regular expression with lookaheads and negative lookaheads, abbreviated to REwLA. First, we propose a transformation from a REwLA of size $m$ to a deterministic finite automaton of $\mr{O}(2^{2^m})$ states. Next, we consider weighted regular expressions, which enable us to calculate submatch addressing. We propose a transformation from a weighted REwLA of size $m$ to a weighted nondeterministic finite automaton of $\mr{O}(2^{2^m})$ states.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2608.03167 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:58:27.423Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).