Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Hermann Gruber; Markus Holzer 
Titel:
Language Operations with Regular Expressions of Polynomial Size 
Abstract:
This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a qu...    »
 
Stichworte:
regular expressions; derivatives; language quotient; cyclic shift; circular shift; descriptional complexity 
Jahr:
2008 
Jahr / Monat:
2008-05-01 00:00:00 
Seiten/Umfang:
16 
Versionen