Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Расскажите мне

СЯУ, что алгоритмы разбора контекстно-свободных языков глубоко связаны с алгоритмами перемножения матриц. В частности, существует следующее взаимно-однозначное соответствие:
- Из любого алгоритма разбора контекстно-свободных с ассимптотической сложностью O(f(n)·|G|) можно сделать алгоритм умножения матриц с асимптотической сложностью O(f(n)).
- Существует CYK-алгоритм (разбора контекстно-свободных языков), пользующийся в своих недрах перемножением битовых матриц. Если использовать алгоритм умножения сложности O(f(n)), получится алгоритм разбора сложности O(f(n)·|G|).

(* |G| "размер" грамматики, n = размер стороны матрицы/длина разбираемого текста.)

У самого обычного алгоритма перемножения матриц сложность O(n3), у самого обычного CYK-разбора O(n3·|G|). Однако в последине годы существует активная движуха вокруг степени 3: ещё в 1987-1990 году был предложен (абсолютно не пригодный на практике, но тем не менее чрезвычайно остроумный и интересный теоретически) алгоритм Копперсмита—Винограда, уменьшающий 3 до 2.3755. В последние четыре года новые работы последовательно снизили показатель степени сперва до 2.3727, а затем до 2.373, а в 2014 году до 2.3728642. Существуют две распространённые гипотезы, по поводу оптимального алгоритма: одна о том, что существуют алгоритмы с показателем сколь угодно близким к двойке, одна о том что существует алгоритм ровно O(n2) сложности. Статья "Group-theoretic Algorithms for Matrix Multiplication" (Cohn, Kleinberg, Szegedy, Umans) связывает последнюю гипотезу с двумя другими разумными гипотезами в комбинаторике и теории групп соответственно.

Может мне кто-нибудь рассказать какова глубинная связь между линейной алгеброй и контекстно-свободными языками, и можно ли подковёрную связь с теорией групп как-то понять на уровне контекстно-свободных языков?
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments