Location Based Automata for Expressions with Shuffle

• Type: Article in International Conference Proceedings Book
• Date: 2021

Authors

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

Conference proceedings International

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

Pages: 43-54

Indexing

Scopus - 2 Citations

Scientific classification

CORDIS: Technological sciences > Engineering > Knowledge engineering ; Technological sciences

FOS: Natural sciences ; Natural sciences > Computer and information sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific