Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
Abstract
The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. We prove that n(n-2) is a tight upper bound for prefix-free regular languages. We present properties of the syntactic semigroups of suffix-, bifix-, and factor-free regular languages, conjecture tight upper bounds on their size to be (n-1)(n-2) + (n-2), (n - 1)(n-3) + (n - 2)(n-3) + (n - 3)(n-3), and (n - 1)(n-3) + (n - 3)2(n-3) + 1, respectively, and exhibit languages with these syntactic complexities. (C) 2012 Elsevier B.V. All rights reserved.
Collections
Cite this version of the work
Janusz Brzozowski, Baiyu Li, Yuli Ye
(2012).
Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. UWSpace.
http://hdl.handle.net/10012/12622
Other formats
The following license files are associated with this item: