1 Search Results for "Chida, Nariyoshi"

Document

DOI: 10.4230/LIPIcs.FSCD.2022.15

On Lookaheads in Regular Expressions with Backreferences

Authors: Nariyoshi Chida and Tachio Terauchi

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Abstract

Many modern regular expression engines employ various extensions to give more expressive support for real-world usages. Among the major extensions employed by many of the modern regular expression engines are backreferences and lookaheads. A question of interest about these extended regular expressions is their expressive power. Previous works have shown that (i) the extension by lookaheads does not enhance the expressive power, i.e., the expressive power of regular expressions with lookaheads is still regular, and that (ii) the extension by backreferences enhances the expressive power, i.e., the expressive power of regular expressions with backreferences (abbreviated as rewb) is no longer regular. This raises the following natural question: Does the extension of regular expressions with backreferences by lookaheads enhance the expressive power of regular expressions with backreferences? This paper answers the question positively by proving that adding either positive lookaheads or negative lookaheads increases the expressive power of rewb (the former abbreviated as rewbl_p and the latter as rewbl_n). A consequence of our result is that neither the class of finite state automata nor that of memory automata (MFA) of Schmid [Markus L. Schmid, 2016] (which corresponds to regular expressions with backreferenes but without lookaheads) corresponds to rewbl_p or rewbl_n. To fill the void, as a first step toward building such automata, we propose a new class of automata called memory automata with positive lookaheads (PLMFA) that corresponds to rewbl_p. The key idea of PLMFA is to extend MFA with a new kind of memories, called positive-lookahead memory, that is used to simulate the backtracking behavior of positive lookaheads. Interestingly, our positive-lookahead memories are almost perfectly symmetric to the capturing-group memories of MFA. Therefore, our PLMFA can be seen as a natural extension of MFA that can be obtained independently of its original intended purpose of simulating rewbl_p.

Cite as

Nariyoshi Chida and Tachio Terauchi. On Lookaheads in Regular Expressions with Backreferences. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chida_et_al:LIPIcs.FSCD.2022.15,
  author =	{Chida, Nariyoshi and Terauchi, Tachio},
  title =	{{On Lookaheads in Regular Expressions with Backreferences}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.15},
  URN =		{urn:nbn:de:0030-drops-162965},
  doi =		{10.4230/LIPIcs.FSCD.2022.15},
  annote =	{Keywords: Regular expressions, Lookaheads, Backreferences, Memory automata}
}

Refine by Author
1 Chida, Nariyoshi
1 Terauchi, Tachio

Refine by Classification
1 Theory of computation → Formal languages and automata theory

Refine by Keyword
1 Backreferences
1 Lookaheads
1 Memory automata
1 Regular expressions

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Chida, Nariyoshi"

On Lookaheads in Regular Expressions with Backreferences

Abstract

Cite as

Thanks for your feedback!

Could not send message