REAL

The Syntactic Complexity of Semi-flower Languages

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] Text
DCFS_2019_semiflower.pdf
Restricted to Registered users only

Download (736kB)

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 Edit Item