Scholarlink

<p>In the String Matching in Labeled Graphs (SMLG) problem, we need to determine whether a pattern string appears on a given labeled graph or a given automaton. Under the Orthogonal Vectors hypothesis, the SMLG problem cannot be solved in subquadratic time. In typical bioinformatics applications, pattern matching algorithms should be both fast and space-efficient, so we need to determine useful classes of graphs on which the SLMG problem can be solved efficiently. In this paper, we improve on a recent result that shows how to solve the SMLG problem in linear time on the compressed representation of Wheeler generalized automata, a class of string-labeled automata that extend de Bruijn graphs. More precisely, we show how to remove the assumption that the automata contain no <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\epsilon\)</EquationSource> </InlineEquation>-transitions (namely, edges labeled with the empty string), while retaining the same time and space bounds. This is a significant improvement because <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\epsilon\)</EquationSource> </InlineEquation>-transitions may considerably reduce the size of an automaton recognizing a given language, while capturing the complexity of regular expressions (through Thompson’s construction for converting a regular expression into an equivalent automaton). We prove that, to enable <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\epsilon\)</EquationSource> </InlineEquation>-transitions, we only need to store two additional bitvectors that can be constructed in linear time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fast pattern matching with epsilon transitions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年8月4日

查看全文
  • Nicola Cotumaccio

摘要

In the String Matching in Labeled Graphs (SMLG) problem, we need to determine whether a pattern string appears on a given labeled graph or a given automaton. Under the Orthogonal Vectors hypothesis, the SMLG problem cannot be solved in subquadratic time. In typical bioinformatics applications, pattern matching algorithms should be both fast and space-efficient, so we need to determine useful classes of graphs on which the SLMG problem can be solved efficiently. In this paper, we improve on a recent result that shows how to solve the SMLG problem in linear time on the compressed representation of Wheeler generalized automata, a class of string-labeled automata that extend de Bruijn graphs. More precisely, we show how to remove the assumption that the automata contain no \(\epsilon\) -transitions (namely, edges labeled with the empty string), while retaining the same time and space bounds. This is a significant improvement because \(\epsilon\) -transitions may considerably reduce the size of an automaton recognizing a given language, while capturing the complexity of regular expressions (through Thompson’s construction for converting a regular expression into an equivalent automaton). We prove that, to enable \(\epsilon\) -transitions, we only need to store two additional bitvectors that can be constructed in linear time.