Gelle, Kitti and Iván, Szabolcs (2019) The Syntactic Complexity of Semi-flower Languages. LECTURE NOTES IN COMPUTER SCIENCE, 11612. pp. 147-157. ISSN 0302-9743
![[img]](http://real.mtak.hu/style/images/fileicons/text.png) |
Text
DCFS_2019_semiflower.pdf Restricted to Registered users only Download (736kB) |
Official URL: http://doi.org/10.1007/978-3-030-23247-4_11
Abstract
Semi-flower languages are those of the form L* for some finite maximal prefix code L, or equivalently, those recognizable by a so-called semi-flower automaton, in which all the cycles have a common state q0, which happens to be the initial state and the only accepting state. We show that the syntactic complexity of these languages is exactly n^n - n! + n (where n stands for the state complexity as usual) and that this bound is reachable with an alphabet of size n.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | PhD Szabolcs Iván |
| Date Deposited: | 23 Sep 2019 11:45 |
| Last Modified: | 23 Sep 2019 11:45 |
| URI: | http://real.mtak.hu/id/eprint/100494 |
Actions (login required)
 |
Edit Item |
