The complexity of verbal languages over groups

التفاصيل البيبلوغرافية
العنوان: The complexity of verbal languages over groups
المؤلفون: Frank Stephan, Alexei Miasnikov, Sanjay Jain
المصدر: LICS
بيانات النشر: Elsevier BV, 2019.
سنة النشر: 2019
مصطلحات موضوعية: General Computer Science, Computer Networks and Communications, Computer science, Chomsky hierarchy, Representation (arts), computer.software_genre, Theoretical Computer Science, Indexed language, Recursively enumerable language, Regular language, Formal language, Context-sensitive language, Mathematics, Sparse language, business.industry, Singleton, Group (mathematics), Applied Mathematics, Context-free language, Abstract family of languages, Cone (formal languages), Linguistics, Computational Theory and Mathematics, Artificial intelligence, business, computer, Natural language processing, Word (group theory)
الوصف: This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.
تدمد: 0022-0000
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::291fe914d59092b193e90f6148b6094e
https://doi.org/10.1016/j.jcss.2018.10.005
حقوق: CLOSED
رقم الأكسشن: edsair.doi.dedup.....291fe914d59092b193e90f6148b6094e
قاعدة البيانات: OpenAIRE