On the structure and syntactic complexity of generalized definite languages
classification
💻 cs.FL
cs.DS
keywords
definitelanguagescomplexitygeneralizedgivesyntacticboundcharacterization
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.