Partial Derivatives of Regular Expressions over Alphabet-Invariant and User-Defined Labels

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

Authors

Konstantinidis, S (Author) Other; Nelma Moreira (Author) FCUP; Pires, J (Author) Other; Rogério Reis (Author) FCUP

Conference proceedings International

Title: Implementation and Application of Automata - 24th International Conference, CIAA 2019, Ko¨ice, Slovakia, July 22-25, 2019, Proceedings

Pages: 184-196

24th International Conference on Implementation and Application of Automata, CIAA 2019

22 July 2019 through 25 July 2019

Indexing

Scopus - 2 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Other information

Authenticus ID: P-00Q-WSG

DOI: 10.1007/978-3-030-23679-3_15

Abstract (EN): We are interested in regular expressions that represent word relations in an alphabet-invariant way¿for example, the set of all word pairs u, v where v is a prefix of u independently of what the alphabet is. This is the second part of a recent paper on this topic which focused on labelled graphs (transducers and automata) with alphabet-invariant and user-defined labels. In this paper we study derivatives of regular expressions over labels (atomic objects) in some set B. These labels can be any strings as long as the strings represent subsets of a certain monoid. We show that one can define partial derivative labelled graphs of type B expressions, whose transition labels can be elements of another label set X as long as X and B refer to the same monoid. We also show how to use derivatives directly to decide whether a given word pair is in the relation of a regular expression over pairing specs. Set specs and pairing specs are useful label sets allowing one to express languages and relations over large alphabets in a natural and compact way. © 2019, Springer Nature Switzerland AG.

Language: English

Type (Professor's evaluation): Scientific