Collapsing words: A progress report / Ananichev DS,Petrov IV,Volkov MV // . - 2005. - V. 3572, l. . - P. 11-21.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Article; Proceedings Paper

Abstract:

A word w over a finite alphabet Sigma 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:

IMAGE; SEMIGROUPS

DOI:

нет данных

Web of Science ID:

ISI:000230874600002

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

Другие поля

Поле	Значение
Editor	Felice, CD and Restivo, R
Booktitle	DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS
Series	LECTURE NOTES IN COMPUTER SCIENCE
Note	9th International Conference on Developments in Language Theory, Palermo, ITALY, JUL 04-08, 2005
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	3-540-26546-5
Keywords-Plus	IMAGE; SEMIGROUPS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Software Engineering; Computer Science, Theory \& Methods
Author-Email	Dmitry.Ananichev@usu.ru ilja\_petrov@pisem.net Mikhail.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	20
Doc-Delivery-Number	BCR07