Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/90784
Author(s): Sabine Broda
António Machiavelo
Nelma Moreira
Rogé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. © Springer International Publishing Switzerland 2015.
URI: http://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 SizeFormat 
106927.pdf281.06 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.