On the structure and syntactic complexity of generalized definite languages

Autor:	Ivan, Szabolcs, Nagy-Gyorgy, Judit
Rok vydání:	2013
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1304.5714 Zobrazit plný text záznamu View this record from Arxiv