Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? / Bulatov Andrei A.,Karpova Olga,Shur Arseny M.,Startsev Konstantin // ELECTRONIC JOURNAL OF COMBINATORICS. - 2017. - V. 24, l. 3.

ISSN/EISSN:

1077-8926 / нет данных

Type:

Article

Abstract:

The words separation problem, originally formulated by Goralcik and Koubek (1986), is stated as follows. Let Sep(n) be the minimum number such that for any two words of length, <= n there is a deterministic finite automaton with Sep(n) states, accepting exactly one of them. The problem is to find the asymptotics of the function Sep. This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups T-k. The known lower bound on Sep stems from the unary identity in T-k. We find the first series of identities in T-k which are shorter than the corresponding unary identity for infinitely many values of k, and thus slightly improve the lower bound on Sep(n). Then we present some short positive identities in symmetric groups, improving the lower bound on separating words by permutational automata by a multiplicative constant. Finally, we present the results of computer search for short identities for small k.

Author keywords:

Words separation; finite automaton; transformation semigroup; symmetric; group; identity AUTOMATA

DOI:

нет данных

Web of Science ID:

ISI:000414865100003

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

—

Другие поля

Поле	Значение
Month	AUG 25
Publisher	ELECTRONIC JOURNAL OF COMBINATORICS
Address	C/O FELIX LAZEBNIK, RM 507, EWING HALL, UNIV DELAWARE, DEPT MATHEMATICAL SCIENCES, NEWARK, DE 19716 USA
Language	English
Article-Number	P3.35
Keywords-Plus	AUTOMATA
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	andrei.bulatov@gmail.com sckleppi@gmail.com arseny.shur@urfu.ru kon7075@yandex.ru
Funding-Acknowledgement	NSERC Discovery grant; Russian Foundation for Basic Research {[}16-01-00795]
Funding-Text	Supported by an NSERC Discovery grant; Partially supported by the grant 16-01-00795 of the Russian Foundation for Basic Research
Number-of-Cited-References	13
Journal-ISO	Electron. J. Comb.
Doc-Delivery-Number	FM2XE