Syntactic complexity of bifix-free languages

DOI10.1007/978-3-319-60134-2_17MaRDI QIDQ2399256zbMATH OpenOpenAlexFDO

Publication date 22 August 2017

Full work available at URL https://arxiv.org/abs/1604.06936

Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Abstract: We study the properties of syntactic monoids of bifix-free regular languages. In particular, we solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a bifix-free language with state complexity

n

is at most

(n - 1)^{n - 3} + (n - 2)^{n - 3} + (n - 3) 2^{n - 3}

for

n g e 6

. The main proof uses a large construction with the method of injective function. Since this bound is known to be reachable, and the values for

n l e 5

are known, this completely settles the problem. We also prove that

(n - 2)^{n - 3} + (n - 3) 2^{n - 3} - 1

is the minimal size of the alphabet required to meet the bound for

n g e 6

. Finally, we show that the largest transition semigroups of minimal DFAs which recognize bifix-free languages are unique up to renaming the states.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Syntactic complexity of bifix-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399256)