Location automata for regular expressions with shuffle and intersection

• Type: Article in International Scientific Journal
• Date: 2023

Authors

Broda, S (Author) FCUP; António Machiavelo (Author) FCUP; Nelma Moreira (Author) FCUP; Rogério Reis (Author) FCUP

Journal

Title: Information and Computation

Vol. 295

ISSN: 0890-5401

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 2 Citations

Other information

Authenticus ID: P-00W-FNY

DOI: 10.1016/j.ic.2022.104917

Abstract (EN): We define the notion of location for regular expressions with shuffle by extending the notion of position in standard regular expressions. Locations allow for the definition of the sets Follow, First, and Last with their usual semantics. From these, we construct an automaton for regular expressions with shuffle (APOS), which generalises the standard position/Glushkov automaton. The sets mentioned above are also the foundation for other constructions, such as the Follow automaton, and automata based on pointed expressions. As a consequence, all these constructions can be generalised to the shuffle operator. We show that the partial derivative automaton is a right-quotient of APOS. We relate APOS with another automaton construction based on positions that has been previously studied (A partial differential pos). The prefix automaton is extended to the shuffle operator and shown not to be a quotient of APOS. Locations are also used to define a position automaton for regular expressions with the intersection.(c) 2022 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 21