О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя

Герман, Ю. О.; Герман, О. В.

О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя

Дата публикации: 2018

Дата публикации в реестре: 2024-03-01T13:36:38Z

Аннотация:

Статья излагает новый взгляд на проблему сложности распознавания языков. Показано, что сложность распознавания языка не адекватна в общем сложности сложности алгоритма, реализуемого распознающей машиной.

Ключевые слова:
публикации ученых, машина Тьюринга, полиномиальная сложность, распознавание языков

Тип: Статья

О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя

Связанные документы (рекомендация CORE)

Партнеры

Индексация