RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 1, 2005, том 12, номер 2, страницы 78–99 (Mi da67)  

Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)

Комбинаторная сложность рациональных языков

А. М. Шур

Уральский государственный университет им. А. М. Горького

Аннотация: Комбинаторной сложностью языка $L$ называется функция, сопоставляющая числу $n$ число различных слов длины $n$ в языке $L$. Точному вычислению и оценкам комбинаторной сложности различных языков посвящены десятки работ. В статье приводится классификация по сложности произвольных рациональных языков и доказывается, что все эти классы остаются нетривиальными при переходе к подклассу рациональных языков – языкам с конечными антисловарями. Для таких языков известен алгоритм оценки сложности. Этот алгоритм экспоненциален по памяти, но находит практическое применение. Обсуждаются приближения произвольных факторных языков языками с конечными антисловарями, доказывается теорема о приближениях языка Туэ–Морса и формулируется общая гипотеза о сложности таких приближений.

Полный текст: PDF файл (338 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
УДК: 519.718
Статья поступила: 18.08.2004
Переработанный вариант: 27.12.2004

Образец цитирования: А. М. Шур, “Комбинаторная сложность рациональных языков”, Дискретн. анализ и исслед. опер., сер. 1, 12:2 (2005), 78–99

Цитирование в формате AMSBIB
\RBibitem{Shu05}
\by А.~М.~Шур
\paper Комбинаторная сложность рациональных языков
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2005
\vol 12
\issue 2
\pages 78--99
\mathnet{http://mi.mathnet.ru/da67}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2168157}
\zmath{https://zbmath.org/?q=an:1249.68107}
\elib{http://elibrary.ru/item.asp?id=9529848}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da67
  • http://mi.mathnet.ru/rus/da/v12/s1/i2/p78

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Shur A.M., “Factorial languages of low combinatorial complexity”, Developments in language theory, Lecture Notes in Comput. Sci., 4036, Springer, Berlin, 2006, 397–407  crossref  mathscinet  zmath  isi  scopus
    2. Avgustinovich S.V., Frid A.E., “Canonical decomposition of a regular factorial language”, Computer science—theory and applications, Lecture Notes in Comput. Sci., 3967, Springer, Berlin, 2006, 18–22  crossref  mathscinet  zmath  isi  scopus
    3. Shur A.M., “Rational approximations of polynomial factorial languages”, Internat. J. Found. Comput. Sci., 18:3 (2007), 655–665  crossref  mathscinet  zmath  isi  elib  scopus
    4. Shur A.M., “Comparing complexity functions of a language and its extendable part”, Theor. Inform. Appl., 42:3 (2008), 647–655  crossref  mathscinet  zmath  isi  scopus
    5. Gawrychowski P., Krieger D., Rampersad N., Shallit J., “Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time”, Developments in Language Theory, Proceedings, Lecture Notes in Computer Science, 5257, 2008, 339–358  crossref  mathscinet  zmath  isi  scopus
    6. Shur A.M., “Combinatorial complexity of regular languages”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, 2008, 289–301  crossref  mathscinet  zmath  isi  scopus
    7. Shur A.M., “On intermediate factorial languages”, Discrete Appl. Math., 157:7 (2009), 1669–1675  crossref  mathscinet  zmath  isi  elib  scopus
    8. Shur A.M., “Polynomial languages with finite antidictionaries”, Theor. Inform. Appl., 43:2 (2009), 269–279  crossref  mathscinet  zmath  isi  scopus
    9. Gawrychowski P., Krieger D., Rampersad N., Shallit J., “Finding the growth rate of a regular or context-free language in polynomial time”, Internat. J. Found. Comput. Sci., 21:4 (2010), 597–618  crossref  mathscinet  zmath  isi  elib  scopus
    10. Martin Torres G., “on the Accuracy of Rough Approximations of Regular Languages”, Fundam. Inform., 132:4 (2014), 533–545  crossref  mathscinet  zmath  isi  scopus
    11. Du Ch.F., Shallit J., Shur A.M., “Optimal Bounds For the Similarity Density of the Thue-Morse Word With Overlap-Free and 7/3-Power-Free Infinite Binary Words”, Int. J. Found. Comput. Sci., 26:8 (2015), 1147–1165  crossref  mathscinet  zmath  isi  elib
    12. Currie J.D., Rampersad N., Saari K., “Suffix Conjugates For a Class of Morphic Subshifts”, Ergod. Theory Dyn. Syst., 35:6 (2015), 1767–1782  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:479
    Полный текст:156
    Литература:47
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020