Location automata for regular expressions with shuffle and intersection

• Tipo: Artigo em Revista Científica Internacional
• Data: 2023

Autores

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

Revista

Título: Information and Computation

Vol. 295

ISSN: 0890-5401

Editora: Elsevier

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 2 Citações

Outras Informações

ID Authenticus: 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/).

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 21