Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/90789| Author(s): | Nelma Moreira Giovanni Pighizzini RogÃ(c)rio Reis |
| Title: | Universal Disjunctive Concatenation and Star |
| Issue Date: | 2015 |
| Abstract: | 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. (c) Springer International Publishing Switzerland 2015. |
| URI: | https://hdl.handle.net/10216/90789 |
| 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 | |
|---|---|---|---|---|
| 107484.pdf | 295.91 kB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.