Open katyacyfra opened 3 years ago
SiERic
commented
3 years ago Так, нет, тут не так. Я не пользуюсь леммой французов про O(n^2), я пользуюсь леммой челов из статьи про D1 o D1 достижимость (она написана чуть выше в этом же файлике) про то, что для двунаправленного графа найдётся путь, который хотя бы по одной координате всегда не сильно вложен. И в этом месте я рассматриваю кусочки путей, которые не вложены сильнее, чем 6n по обеим координатам.
katyacyfra
commented
3 years ago А, лол, я посмотрела на предыдущую главу по отсылке и подумала, что ты ДКА с n^2 состояний строишь. Не обратила внимание, что на картинке 6n. Внутри квадратика ок, хотя лучше формально расписать как конструируется пересечение. Осталось понять, что ты делаешь вне квадратика. Пока не понимаю, зачем авторам статьи столько телодвижений там, и нужны ли они.
https://github.com/SiERic/bachelor-diploma-cfpq/blob/3859272b8fdc0b7045017ce5c6c902b3a3414ec2/sections/dyck_1_1.tex#L43
Здесь есть проблема, которая ставит под сомнение всю конструкцию. Если я правильно поняла, ты используешь лемму французов про O(n^2). Но она не работает здесь (ибо язык другой)! Т.е. если ты сотрешь (заменишь на эпсилон) скобки из одного языка (пусть это будут квадратные), да, ты действительно на любом графе найдешь сбаланчированный путь длиной < O(n^2). Но это не гарантирует то, что когда ты вернёшь на место квадратные скобки, они будут тоже сбалансированными. Тогда у тебя есть более длинный путь из круглых скобок, зато квадратные сбалансированы на нём.
Поэтому нужно доказать отдельно утверждение про длины путей (число состояний) в ДКА. Скорее всего в общем случае ничего не получится (путь экспоненциальной длины скорее всего). Нужно использовать то, что граф двунаправленный, может благодаря этому всё заработает.
P.S. Некорторые твои идеи здесь выглядят более адекватными,чем у авторов статьи, которые довольно-таки активно занимаются перебором :)