On the structure and syntactic complexity of generalized definite languages
Szabolcs Iván, Judit Nagy-György · arXiv (Cornell University) · 2013
We give a forbidden pattern characterization for the class of generalized definite languages, show that the corresponding problem is NL-complete and can be solved in quadratic time. We also show that their syntactic complexity coincides with that of the definite languages and give an upper bound of n! for this measure.