Extended to multi-tilde-bar regular expressions and efficient finite automata constructions

DOI10.1016/J.JDA.2015.03.001MaRDI QIDQ491616zbMATH OpenOpenAlexFDO

Authors Faissal Ouardi, Jean-Marc Champarnaud, Djelloul Ziadi

Publication date 18 August 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3507

zbMATH Keywords

computational complexityfinite automataformal languagesregular expressions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Abstract: Several algorithms have been designed to convert a regular expression into an equivalent finite automaton. One of the most popular constructions, due to Glushkov and to McNaughton and Yamada, is based on the computation of the Null, First, Last and Follow sets (called Glushkov functions) associated with a linearized version of the expression. Recently Mignot considered a family of extended expressions called Extended to multi-tilde-bar Regular Expressions (EmtbREs) and he showed that, under some restrictions, Glushkov functions can be defined for an EmtbRE. In this paper we present an algorithm which efficiently computes the Glushkov functions of an unrestricted EmtbRE. Our approach is based on a recursive definition of the language associated with an EmtbRE which enlightens the fact that the worst case time complexity of the conversion of an EmtbRE into an automaton is related to the worst case time complexity of the computation of the Null function. Finally we show how to extend the ZPC-structure to EmtbREs, which allows us to apply to this family of extended expressions the efficient constructions based on this structure (in particular the construction of the c-continuation automaton, the position automaton, the follow automaton and the equation automaton).

Recommendations

• Multi-tilde-bar expressions and their automata
• Some results on regular expressions for multitape finite automata
• An optimal construction of finite automata from regular expressions
• Embedding finite automata within regular expressions
• scientific article; zbMATH DE number 1159571
• scientific article; zbMATH DE number 1948484
• Regular expressions into finite automata
• Short Regular Expressions from Finite Automata: Empirical Results
• More Concise Representation of Regular Languages by Automata and Regular Expressions
• More concise representation of regular languages by automata and regular expressions

Cites work

• Acyclic automata and small expressions using multi-tilde-bar operators
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Derivatives of Regular Expressions
• Fast equation automaton computation
• Follow automata.
• From regular expressions to deterministic automata
• From regular expressions to finite automata^∗
• FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA
• FROM THE $\mathcal{ZPC}$ STRUCTURE OF A REGULAR EXPRESSION TO ITS FOLLOW AUTOMATON
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• Local languages and the Berry-Sethi algorithm
• Multi-tilde-bar expressions and their automata
• Partial derivatives of regular expressions and finite automaton constructions
• Regular expressions into finite automata
• THE ABSTRACT THEORY OF AUTOMATA
• The passing of a rational expression to a nondeterministic finite automaton

Cited in

(5)

• Acyclic automata and small expressions using multi-tilde-bar operators
• Multi-tilde Operators and Their Glushkov Automata
• Small Extended Expressions for Acyclic Automata
• A Unified Construction of the Glushkov, Follow, and Antimirov Automata
• Multi-tilde-bar expressions and their automata

This page was built for publication: Extended to multi-tilde-bar regular expressions and efficient finite automata constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491616)