Location Based Automata for Expressions with Shuffle

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2021

Autores

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

Ata de Conferência Internacional

Título: Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Milan, Italy, March 1-5, 2021, Proceedings

Páginas: 43-54

Indexação

Scopus - 2 Citações

Classificação Científica

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia do conhecimento ; Ciências Tecnológicas

FOS: Ciências exactas e naturais ; Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00T-GT5

DOI: 10.1007/978-3-030-68195-1_4

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 now be directly generalised to regular expressions with shuffle, as well as their known relationships. We also show that the partial derivative automaton (APD ) is a (right) quotient of the new position automaton, APOS. In previous work an automaton construction based on positions was studied (A¿ p o s ), and here we relate APOS and A¿ p o s. Finally, we extend the construction of the prefix automaton APre to the shuffle operator and show that it is not a quotient of APOS. © 2021, Springer Nature Switzerland AG.

Idioma: Inglês

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