# The Syntactic Complexity of Semi-flower Languages

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 $q_0$, 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.
Document type :
Conference papers
Domain :

Cited literature [15 references]

https://hal.inria.fr/hal-02387298
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, November 29, 2019 - 4:36:07 PM
Last modification on : Friday, November 29, 2019 - 5:01:49 PM

### File

480958_1_En_11_Chapter.pdf
Files produced by the author(s)

### Citation

Kitti Gelle, Szabolcs Iván. The Syntactic Complexity of Semi-flower Languages. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.147-157, ⟨10.1007/978-3-030-23247-4_11⟩. ⟨hal-02387298⟩

Record views