Количество состояний локальных автоматов

10

Детерминированный автомат называется k- локальным при k > 0, если для каждого w X k множество { δ ( q , w ) : q Q } содержит не более один элемент. Интуитивно это означает, что если слово w длины k приводит к состоянию, то это состояние уникально или сказано иначе, чем произвольное слово длиныAзнак равно(Икс,Q,Q0,F,δ)КК>0весИксК{δ(Q,вес):QQ}весК последние k символов определяют состояние, к которому оно приводит.>КК

Теперь, если автомат является локальным, то он не должен быть k -локальным для некоторого k < k , но он должен быть k -локальным для k > k, чтобы последние символы некоторого слова | ш | > k определить состояние, если оно есть, однозначно.КК'К'<КК'К'>К|вес|>К

Теперь я пытаюсь связать число состояний и локальность автомата. Я предполагаю:К

Лемма: Пусть = ( X , Q , Q 0 , F , δ ) быть к -local, если | Q | < k, то автомат тоже | Q | -местный.Aзнак равно(Икс,Q,Q0,F,δ)К|Q|<К|Q|

Но я не смог доказать, какие-либо предложения или идеи?

Я надеюсь , что с помощью этой леммы , чтобы получить что - то о количестве состояний автомата, не -local для всех к N при фиксированном N > 0 , но к -local для некоторых к > N .ККNN>0КК>N

StefanH
источник

Ответы:

7

Поскольку вы говорите, что должно содержать не более одного элемента, я предполагаю, что вы используете версию DFA, где δ может быть частичным. Тогда это контрпример: X = { a , b } , Q = { 0 , 1 , 2 , 3 , 4 } , δ ( q , a ) =Tвесзнак равно{δ(Q,вес):QQ}δ для q < 4 и δ ( 1 , b ) = 2 , δ ( 2 , b ) = 3 , δ ( 4 , b ) = 0 . F и q 0, очевидно, не имеют значения для этого вопроса.Иксзнак равно{a,б},Qзнак равно{0,1,2,3,4},δ(Q,a)знак равноQ+1Q<4δ(1,б)знак равно2,δ(2,б)знак равно3,δ(4,б)знак равно0FQ0

Автомат является локальным, но не 5- локальным, поскольку T a b a a b = { 0 , 3 } .65Taбaaбзнак равно{0,3}

Изменить: этот контрпример не работает, я буду держать его, чтобы комментарии имели смысл. Следующее делает, хотя.

Возьмем , с переходами 0 1 ( a ) , 1 2 ( a ) , 2 3 ( a ) , 2 0 ( b ) , 3 2 ( б ) . Этот автомат 5Иксзнак равно{a,б},Qзнак равно{0,1,2,3}01(a),12(a),23(a),20(б),32(б)5-локальный, но не локальный: для a a b a мы получаем пути 0 1 2 0 1 и 1 2 3 2 3 , т.е. T a a b a = { 1 , 3 } .4aaбa0120112323Taaбaзнак равно{1,3}

Клаус Дрегер
источник
что-то не так с вашими автоматами, вы забыли определенные переходы? Слово приводит ни к какому состоянию, независимо от того, с чего я начинаю ...aбaaб
StefanH
Я думаю , что это должно быть правильным - сказал немного по- другому, переходы: и 4 0 ( б ) . Тогда пути, которые вы получите для a b a a b, будут 0 1 2 01(a),12(a,б),23(a,б),34(a),40(б)abaab и 3 4 0 1 2 3 . 012340340123
Клаус Дрегер
извините вы правы!
StefanH
О, вообще-то нет, но по другой причине. Вы получаете эти пути, но тогда вы можете просто повторять бесконечно - этот автомат не является k- локальным для любого k . abaabkk
Клаус Дрегер
конечно, в общем случае автомат не может быть локальным, если существует два различных и слово w, такое что δ ( p , w ) = p и δ ( q , w ) = q . p,qwδ(p,w)=pδ(q,w)=q
StefanH
8

Поздний ответ, но ограничение задержки синхронизации было изучено для нескольких классов автоматов: см., Например, Однозначные автоматы; Беал и др. MCS'08 .

В частности; существует семейство детерминированных автоматов с задержкой как показано в разделе «На границе задержки синхронизации локального автомата»; Беал и др. TCS'98 , который соответствует соответствующей верхней границе O ( | Q | 2 ) .Ω(|Q|2)O(|Q|2)

PS задержка синхронизации, определенная в статье, является минимальным для которого детерминированный локальный автомат является k- локальным .kk

Джозеф Стэк
источник
Вы, кажется, подразумеваете, что задержка синхронизации эквивалентна k-local ....?
ВЗН
1
В статье TCS'08, которую я цитирую, для локальных DFA «задержка синхронизации составляет 1+ длины самой длинной несинхронизирующей последовательности», где несинхронизирующая последовательность - это слово, которое может привести к двум различным состояниям. Для меня это по определению наименьшее для которого автомат является k- локальным. Вы думаете, я ошибаюсь? kk
Джозеф Стэк
хороший ответ не пропустит ключевые детали. возможно, они (почти? точно?) эквивалентны, но тогда это будет новый "мост thm", а не в газете или опубликованной связи ...? если так, то это нужно где-то детализировать ...
vzn
1
Хорошо. Я отредактировал ответ, чтобы подчеркнуть суть. Я не думаю, что нужен какой-либо мост, кроме проверки определения.
Джозеф Стэк
предложить, чтобы оба определения были указаны точно, а затем доказано, что они эквивалентны. спасибо за разъяснение до сих пор.
ВЗН