Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:36:07 PM
Last modification on : Friday, November 29, 2019 - 5:01:49 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



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⟩