Preset Distinguishing Sequences and Diameter of Transformation Semigroups

Информация о цитировании статьи получена из Scopus
Дата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.

Автор: Panteleev Pavel
Сборник: Language and Automata Theory and Applications
Серия: Lecture Notes in Computer Science
Том: 8977
Год издания: 2015
Место издания: Springer International Publishing
Первая страница: 353
Последняя страница: 364
DOI: 10.1007/978-3-319-15579-1_27
Аннотация: We investigate the length $\ell(n,k)$ of a shortest preset distinguishing sequence (PDS) in the worst case for a $k$-element subset of an $n$-state Mealy automaton. It was mentioned by Sokolovskii that this problem is closely related to the problem of finding the maximal subsemigroup diameter $\ell(T_n)$ for the full transformation semigroup $T_n$ of an $n$-element set. We prove that $\ell(T_n)=2^n\exp\{\sqrt{\frac{n}{2}\ln n}(1+ o(1))\}$ as $n\to\infty$ and, using approach of Sokolovskii, find the asymptotics of $\log_2 \ell(n,k)$ as $n,k\to\infty$ and $k/n\to a\in (0,1)$.
Добавил в систему: Пантелеев Павел Анатольевич

	ИСТИНА	Войти в систему Регистрация
	Интеллектуальная Система Тематического Исследования НАукометрических данных
	Главная Поиск Статистика О проекте Помощь

ИСТИНА