Image reducing words and subgroups of free groups / Ananichev DS,Cherubini A,Volkov MV // THEORETICAL COMPUTER SCIENCE. - 2003. - V. 307, l. 1. - P. 77-92.

ISSN/EISSN:

0304-3975 / нет данных

Type:

Article; Proceedings Paper

Abstract:

A word w over a finite alphabet Sigma is said to be n-collapsing if for an arbitrary finite automaton A = the inequality \textbackslash{}Q . w\textbackslash{} less than or equal to \textbackslash{}Q\textbackslash{} - n holds provided that \textbackslash{}Q . u\textbackslash{} less than or equal to \textbackslash{}Q\textbackslash{} - n for some word u (depending on A). We give an algorithm to test whether a word is 2-collapsing. To this aim we associate to every word w a finite family of finitely generated subgroups in finitely generated free groups and prove that the property of being 2-collapsing reflects in the property that each of these subgroups has index at most 2 in the corresponding free group. We also find a similar characterization for the closely related class of so-called 2-synchronizing words. (C) 2003 Elsevier B.V. All rights reserved.

Author keywords:

synchronizing automata; compressible automata; 2-collapsing words; free groups

DOI:

10.1016/S0304-3975(03)00093-8

Web of Science ID:

ISI:000185446400005

Соавторы в МНС:

Другие поля

Поле	Значение
Month	SEP 26
Note	3rd Conference on WORDS, PALERMO, ITALY, SEP, 2001
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	13
Usage-Count-Since-2013	1
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	723RY