Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/90784| Author(s): | Sabine Broda António Machiavelo Nelma Moreira RogÃ(c)rio Reis |
| Title: | Partial Derivative Automaton for Regular Expressions with Shuffle |
| Issue Date: | 2015 |
| Abstract: | 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. (c) Springer International Publishing Switzerland 2015. |
| URI: | https://hdl.handle.net/10216/90784 |
| Source: | Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings |
| Document Type: | Artigo em Livro de Atas de Conferência Internacional |
| Rights: | openAccess |
| Appears in Collections: | FCUP - Artigo em Livro de Atas de Conferência Internacional |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 106927.pdf | 281.06 kB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.