Partial Derivative Automaton for Regular Expressions with Shuffle

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

Authors

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

Conference proceedings International

Title: Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings

Pages: 21-32

Indexing

ISI Web of Knowledge

Scopus - 0 Citations

Other information

Authenticus ID: P-00G-6GC

DOI: 10.1007/978-3-319-19225-3_2

Abstract (EN): We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial derivative automata is in the worst case at most 2m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4\3)m. © Springer International Publishing Switzerland 2015.

Language: English

Type (Professor's evaluation): Scientific