Paper Info
Title
Partial Derivatives of Regular Expressions over Alphabet-Invariant and User-Defined Labels.
Abstract
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.
Year
DOI
Venue
2019
10.1007/978-3-030-23679-3_15
CIAA
Field
DocType
Citations 
Combinatorics,Regular expression,Partial derivative,Invariant (mathematics),Mathematics,Alphabet
Conference
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Stavros Konstantinidis128331.10
Nelma Moreira218033.98
João Pires300.34
Rogério Reis414025.74