Complexity of suffix-free regular languages

作者：

Highlights：

• There is no universal most complex sequence of suffix-free regular languages.

• There are two such sequences that together meet upper bounds for all basic measures.

• Transition semigroups of suffix-free languages meeting the bounds are characterized.

摘要

•There is no universal most complex sequence of suffix-free regular languages.•There are two such sequences that together meet upper bounds for all basic measures.•Transition semigroups of suffix-free languages meeting the bounds are characterized.

论文关键词：Most complex,Regular language,State complexity,Suffix-free,Syntactic complexity,Transition semigroup

论文评审过程：Received 10 December 2015, Revised 22 March 2017, Accepted 22 May 2017, Available online 19 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.05.011