An inverse automata algorithm for recognizing 2-collapsing words / Ananichev DS,Cherubini A,Volkov MV // . - 2003. - V. 2450, l. . - P. 270-282.

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 \textbackslash{}delta(Q, w)\textbackslash{} less than or equal to \textbackslash{}Q\textbackslash{} - n holds provided that \textbackslash{}delta(Q, u)\textbackslash{} less than or equal to \textbackslash{}Q\textbackslash{} - n for some word u is an element of Sigma(+) (depending on A). We give a new algorithm to test whether a word w is 2-collapsing. In contrast to our previous group-theoretic algorithm, the present algorithm is of a geometric nature, and if the word w is an element of Sigma{*} is not 2-collapsing, it directly produces a DFA A(w) = (Q, Sigma, delta) such that \textbackslash{}Q\textbackslash{} < max\{\textbackslash{}w\textbackslash{

Author keywords:

нет данных

DOI:

нет данных

Web of Science ID:

ISI:000185510600023

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

Другие поля

Поле	Значение
Editor	Ito, M and Toyama, M
Booktitle	DEVELOPMENTS IN LANGUAGE THEORY
Series	LECTURE NOTES IN COMPUTER SCIENCE
Note	6th International Conference on Developments in Language Theory (DLT 2002), KYOTO SANGYO UNIV, KYOTO, JAPAN, SEP 18-21, 2002
Organization	Inoue Fdn Sci; Kayamori Sci Fdn; Asahi Glass Fdn; EATCS
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	3-540-40431-7
Research-Areas	Computer Science; Mathematics
Web-of-Science-Categories	Computer Science, Theory \& Methods; Mathematics
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	12
Usage-Count-Since-2013	1
Doc-Delivery-Number	BX50A