Partial Derivative Automaton for Regular Expressions with Shuffle

Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/90784

Full metadata record

DC Field	Value	Language
dc.creator	Sabine Broda
dc.creator	AntÃ³nio Machiavelo
dc.creator	Nelma Moreira
dc.creator	RogÃ(c)rio Reis
dc.date.accessioned	2019-10-04T23:15:03Z	-
dc.date.available	2019-10-04T23:15:03Z	-
dc.date.issued	2015
dc.identifier.other	sigarra:106927
dc.identifier.uri	https://hdl.handle.net/10216/90784	-
dc.description.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.
dc.language.iso	eng
dc.relation.ispartof	Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings
dc.rights	openAccess
dc.title	Partial Derivative Automaton for Regular Expressions with Shuffle
dc.type	Artigo em Livro de Atas de Conferência Internacional
dc.contributor.uporto	Faculdade de Ciências
dc.identifier.doi	10.1007/978-3-319-19225-3_2
dc.identifier.authenticus	P-00G-6GC
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