The Syntactic Complexity of Semi-flower Languages - Descriptional Complexity of Formal Systems
Conference Papers Year : 2019

The Syntactic Complexity of Semi-flower Languages

Kitti Gelle
  • Function : Author
  • PersonId : 1024583
Szabolcs Iván
  • Function : Author
  • PersonId : 1022733

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.
Fichier principal
Vignette du fichier
480958_1_En_11_Chapter.pdf (328.23 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02387298 , version 1 (29-11-2019)

Licence

Identifiers

Cite

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⟩
44 View
43 Download

Altmetric

Share

More