Collapsing words: A progress report / Ananichev DS,Petrov IV,Volkov MV // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2006. - V. 17, l. 3. - P. 507-518.

ISSN/EISSN:

0129-0541 / нет данных

Type:

Article; Proceedings Paper

Abstract:

A word w over a finite alphabet E is n-collapsing if for an arbitrary DFA A = < Q,Sigma,delta >, the inequality vertical bar delta(Q,w)vertical bar <= vertical bar Q vertical bar - n holds provided that vertical bar delta(Q,u)vertical bar <= vertical bar Q vertical bar - n for some word u is an element of Sigma(+) (depending on A). We overview some recent results related to this notion. One of these results implies that the property of being n-collapsing is algorithmically recognizable for any given positive integer n.

Author keywords:

deterministic finite automaton; n-compressing word; n-collapsing word; identity checking problem EQUIVALENCE PROBLEM; FINITE-GROUPS; IMAGE; SEMIGROUPS

DOI:

10.1142/S0129054106003966

Web of Science ID:

ISI:000238454100003

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

Другие поля

Поле	Значение
Month	JUN
Note	9th International Conference on Developments in Language Theory, Palermo, ITALY, JUL 04-08, 2005
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
Keywords-Plus	EQUIVALENCE PROBLEM; FINITE-GROUPS; IMAGE; SEMIGROUPS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	Mikhail.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	22
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	055MF