Universal Disjunctive Concatenation and Star

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

Authors

Nelma Moreira (Author) FCUP; Giovanni Pighizzini (Author) Other; 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: 197-208

Indexing

ISI Web of Knowledge

Scopus - 1 Citation

Other information

Authenticus ID: P-00G-6GD

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

Abstract (EN): Two language operations that can be expressed by suitably combining complement with concatenation and star, respectively, are introduced. The state complexity of those operations on regular languages is investigated. In the deterministic case, optimal exponential state gaps are proved for both operations. In the nondeterministic case, for one operation an optimal exponential gap is also proved, while for the other operation an exponential upper bound is obtained. © Springer International Publishing Switzerland 2015.

Language: English

Type (Professor's evaluation): Scientific