Вложенное слово - Nested word

В Информатика, более конкретно в автоматы и формальный язык теория вложенные слова являются концепцией, предложенной Алур и Мадхусудан как совместное обобщение слова, как традиционно используется для моделирования линейно упорядоченный структур, а также заказанных безрейтинговых деревья, как традиционно используется для моделирования иерархических структур. Конечные акцепторы для вложенных слов, так называемые вложенные словесные автоматы, то дадим более выразительное обобщение конечные автоматы на словах. Линейные кодировки языков, принимаемые конечными автоматами с вложенными словами, дают класс явно выталкивающие языки. Последний языковой класс находится между обычные языки и детерминированные контекстно-свободные языки. С момента своего появления в 2004 году эти концепции вызвали множество исследований в этой области.^[1]

Формальное определение

Определять вложенные слова, сначала определите соответствующие отношения. Для неотрицательное целое число ${ displaystyle ell}$ , обозначение ${ displaystyle [ ell]}$ обозначает множество ${ Displaystyle {1,2, ldots, ell -1, ell }}$ , с особым случаем ${ displaystyle [0] = emptyset}$ .

А соответствие отношения ↝ длины ${ displaystyle ell geq 0}$ это подмножество ${ Displaystyle {- infty, 1,2, ldots, ell -1, ell } times {1,2, ldots, ell -1, ell, infty }}$ такой, что:

все грани вложения направлены вперед, т.е. если $я ↝ j$ тогда $я < j$ ;
ребра вложенности никогда не имеют общего конечного положения, то есть для $-\infty < я < \infty$ , есть не более одной позиции час такой, что $час ↝ я$ , и есть не более одной позиции j такой, что я ↝ j; и
края вложенности никогда не пересекаются, то есть нет $я < я' \leq j < j'$ так что оба $я ↝ j$ и $я' ↝ j'$ .

Позиция я упоминается как

а позиция вызова, если я ↝ j для некоторых j,
а ожидающий вызов если я ↝ ∞,
а вернуть позицию, если час ↝ я для некоторых час,
а ожидающий возврата если −∞ ↝ я, и
ан внутреннее положение во всех остальных случаях.

А вложенное слово длины ${ displaystyle ell}$ над алфавит Σ - пара (ш, ↝), где ш это слово, или нить, длины ${ displaystyle ell}$ над Σ и ↝ - отношение согласования длины ${ displaystyle ell}$ .

Кодирование вложенных слов в обычные слова

Вложенные слова по алфавиту ${ Displaystyle Sigma = {a_ {1}, a_ {2}, ldots, a_ {n} }}$ могут быть закодированы в "обычные" слова поверх отмеченный алфавит ${ displaystyle { hat { Sigma}}}$ , в котором каждый символ а из Σ имеет три помеченных аналога: символ ⟨A для кодирования позиции вызова во вложенном слове, помеченном а, символ а⟩ для кодирования позиции возврата, помеченной а, и, наконец, символ а сам для представления внутренней позиции, помеченной а. Точнее, пусть φ - функция, отображающая вложенные слова над Σ в слова над ${ displaystyle { hat { Sigma}}}$ так что каждое вложенное слово ( ${ displaystyle w_ {1} w_ {2} cdots w _ { ell}}$ , ↝) отображается в слово ${ displaystyle x_ {1} x_ {2} ... x _ { ell}}$ , где буква ${ displaystyle x_ {i}}$ равно ⟨A, а, и а⟩, если ${ displaystyle w_ {i} = а}$ и я - это (возможно, ожидающая) позиция вызова, внутренняя позиция и (возможно, ожидающая) позиция возврата соответственно.

Пример

Для иллюстрации пусть п = (ш, ↝) - вложенное слово над тернарным алфавитом с ш=abaabccca и соответствие отношения $↝ = {(-\infty,1),(2,\infty),(3,4),(5,7),(8,\infty)$ }. Тогда его кодировка как слово читается как φ(п) = а⟩⟨б⟨аа⟩⟨скрытая копия⟩⟨ок.

Автоматы

Вложенный словарный автомат

А вложенное слово автомат имеет конечное число состояний и работает почти так же, как детерминированный конечный автомат на классических строках: классический конечный автомат читает входное слово ${ Displaystyle ш = ш_ {1} cdots ш _ { ell}}$ слева направо, а состояние автомата после прочтения jое письмо ${ displaystyle w_ {j}}$ зависит от того, в каком состоянии находился автомат перед чтением ${ displaystyle w_ {j}}$ .

Во вложенном словесном автомате позиция ${ displaystyle j}$ во вложенном слове (w, ↝) может быть позиция возврата; если да, то состояние после прочтения ${ displaystyle w_ {j}}$ будет зависеть не только от линейное состояние в котором был автомат до чтения ${ displaystyle w_ {j}}$ , но и на иерархическое состояние распространяются автоматом в то время, когда он находился в соответствующей позиции вызова. По аналогии с обычные языки слов, набор L вложенных слов называется обычный если это принимается некоторым (конечным) вложенным словесным автоматом.

Заметно выталкивающий автомат

Автоматы с вложенными словами - это модель автомата, принимающая вложенные слова. Существует эквивалентная модель автомата, работающая на (обычных) словах. А именно, понятие детерминированный автомат с видимым опусканием является ограничением понятия детерминированный автомат выталкивания.

Следуя за Алуром и Мадхусуданом,^[2] детерминированный автомат с видимым выталкиванием формально определяется как набор из 6 ${ Displaystyle M = (Q, { шляпа { Sigma}}, Gamma, delta, q_ {0}, F)}$ куда

${ displaystyle Q}$ конечный набор состояния,
${ displaystyle { hat { Sigma}}}$ это вводить алфавит, который - в отличие от обычных автоматов с выталкиванием - разделен на три набора ${ displaystyle Sigma _ { text {c}}}$ , ${ displaystyle Sigma _ { text {r}}}$ , и ${ displaystyle Sigma _ { text {int}}}$ . Алфавит ${ displaystyle Sigma _ { text {c}}}$ обозначает набор символы вызова, ${ displaystyle Sigma _ { text {r}}}$ содержит символы возврата, а множество ${ displaystyle Sigma _ { text {int}}}$ содержит внутренние символы,
${ displaystyle Gamma}$ конечное множество, которое называется сложить алфавит, содержащий специальный символ ${ displaystyle bot in Gamma}$ обозначает пустой стек,
${ displaystyle delta = delta _ { text {c}} cup delta _ { text {r}} cup delta _ { text {int}}}$ $delta = delta _ {{ text {c}}} cup delta _ {{ text {r}}} cup delta _ {{ text {int}}}$ это функция перехода, который разделен на три части, соответствующие переходам вызовов, переходам возврата и внутренним переходам, а именно
- ${ displaystyle delta _ { text {c}} двоеточие Q times Sigma _ { text {c}} to Q times Gamma}$ , то вызов функции перехода
- ${ displaystyle delta _ { text {r}} двоеточие Q times Sigma _ { text {r}} times Gamma to Q}$ , то вернуть функцию перехода
- ${ displaystyle delta _ { text {int}}: Q times Sigma _ { text {int}} to Q}$ , то функция внутреннего перехода,
${ displaystyle q_ {0} in , Q}$ это начальное состояние, и
${ Displaystyle F substeq Q}$ это набор принимающие государства.

Понятие вычисление явно выталкивающего автомата является ограничением того, что используется для выталкивающие автоматы. Заметно выталкивающие автоматы добавляют символ в стек только при чтении символа вызова ${ displaystyle a _ { text {c}} in Sigma _ { text {c}}}$ , они удаляют только верхний элемент из стека при чтении символа возврата ${ displaystyle a _ { text {r}} in Sigma _ { text {r}}}$ и они не изменяют стек при чтении внутреннего события ${ displaystyle a _ { text {i}} in Sigma _ { text {int}}}$ . Вычисление, заканчивающееся в состоянии принятия, является принятие вычисления.

В результате автомат с явным выталкиванием вниз не может нажимать и выталкивать из стека с одним и тем же входным символом. Таким образом, язык ${ displaystyle L = {a ^ {n} ba ^ {n} mid n in mathrm {N} }}$ не могут быть приняты автоматом видимого выталкивания для любого раздела ${ displaystyle Sigma}$ , однако есть автоматические устройства, поддерживающие этот язык.

Если язык ${ displaystyle L}$ над отмеченным алфавитом ${ displaystyle { hat { Sigma}}}$ принимается детерминированным автоматом с видимым опусканием, тогда ${ displaystyle L}$ называется явно выталкивающий язык.

Недетерминированные явно выталкивающие автоматы

Недетерминированный явно выталкивающие автоматы столь же выразительны, как и детерминированные. Следовательно, можно преобразовать недетерминированный автомат с видимым выталкиванием вниз в детерминированный, но если бы недетерминированный автомат имел ${ displaystyle s}$ состояний, детерминированный может иметь до ${ displaystyle 2 ^ {s ^ {2}}}$ состояния.^[3]

Проблемы с решением

Позволять ${ displaystyle | A |}$ быть размером с описание автомата ${ displaystyle A}$ , то можно проверить, есть ли слово п принимается автоматом вовремя ${ Displaystyle О (| А | ^ {3} ell)}$ . В частности, проблема пустоты решается во времени. ${ Displaystyle O (| A | ^ {3})}$ .Если ${ displaystyle A}$ фиксировано, разрешимо во времени ${ Displaystyle О ( ell)}$ и космос ${ displaystyle O (d)}$ куда ${ displaystyle d}$ глубина п в потоковом видении. Это также разрешимо с пространством ${ Displaystyle О ( журнал ( ell))}$ и время ${ Displaystyle О ( ell ^ {2} журнал ( ell))}$ , и равномерной логической схемой глубины ${ Displaystyle О ( журнал ell)}$ .^[2]

Для двух недетерминированных автоматов А и B, решая, принимает ли набор слов А это подмножество слова, принятое B является EXPTIME -полный. Это также EXPTIME-complete, чтобы выяснить, есть ли слово, которое не принято.^[2]

Языки

Как показывает определение автоматов с видимым выталкиванием, детерминированные автоматы с видимым выталкиванием можно рассматривать как частный случай детерминированные автоматы выталкивания; таким образом, набор VPL языков явно вытесняющих ${ displaystyle , { hat { Sigma}}}$ образует подмножество множества DCFL из детерминированные контекстно-свободные языки над набором символов в ${ displaystyle , { hat { Sigma}}}$ . В частности, функция, которая удаляет отношение соответствия из вложенных слов, преобразует обычные языки вместо вложенных слов в контекстно-свободные языки.

Свойства закрытия

Набор языков с явным выталкиванием закрывается при следующих операциях:^[3]

установить операции:
- союз
- пересечение
- дополнение

таким образом породив логическая алгебра.

Для операции пересечения можно построить VPA M моделирование двух данных VPA ${ displaystyle M_ {1}}$ и ${ displaystyle M_ {2}}$ простой конструкцией продукта (Алур и Мадхусудан 2004 ): За ${ displaystyle i = 1,2}$ , предполагать ${ displaystyle M_ {i}}$ дается как ${ displaystyle (Q_ {i}, { hat { Sigma}}, Gamma _ {i}, delta _ {i}, s_ {i}, Z_ {i}, F_ { я})}$ . Тогда для автомата M, множество состояний ${ displaystyle , Q_ {1} times Q_ {2}}$ , начальное состояние ${ displaystyle left (s_ {1}, s_ {2} right)}$ , набор конечных состояний ${ displaystyle F_ {1} times F_ {2}}$ , стековый алфавит задается формулой ${ displaystyle , Gamma _ {1} times Gamma _ {2}}$ , а начальный символ стека - ${ displaystyle (Z_ {1}, Z_ {2})}$ .

Если ${ displaystyle M}$ в состоянии ${ displaystyle (p_ {1}, p_ {2})}$ при чтении символ вызова ${ displaystyle left langle a right.}$ , тогда ${ displaystyle M}$ толкает символ стека ${ displaystyle ( gamma _ {1}, gamma _ {2})}$ и идет к состоянию ${ displaystyle (q_ {1}, q_ {2})}$ , куда ${ displaystyle gamma _ {я}}$ символ стека выталкивается ${ displaystyle M_ {i}}$ при переходе из состояния ${ displaystyle p_ {i}}$ к ${ displaystyle q_ {i}}$ при чтении ввода ${ displaystyle left langle a right.}$ .

Если ${ displaystyle M}$ в состоянии ${ displaystyle (p_ {1}, p_ {2})}$ при чтении внутренний символ ${ displaystyle a}$ , тогда ${ displaystyle M}$ переходит в состояние ${ displaystyle (q_ {1}, q_ {2})}$ , в любое время ${ displaystyle M_ {i}}$ переходы из состояния ${ displaystyle p_ {i}}$ к ${ displaystyle q_ {i}}$ по чтению а.

Если ${ displaystyle M}$ в состоянии ${ displaystyle (p_ {1}, p_ {2})}$ при чтении символ возврата ${ Displaystyle left.a right rangle}$ , тогда ${ displaystyle M}$ появляется символ ${ displaystyle ( gamma _ {1}, gamma _ {2})}$ из стека и переходит в состояние ${ displaystyle (q_ {1}, q_ {2})}$ , куда ${ displaystyle gamma _ {я}}$ символ стека появляется ${ displaystyle M_ {i}}$ при переходе из состояния ${ displaystyle p_ {i}}$ к ${ displaystyle q_ {i}}$ по чтению ${ Displaystyle left.a right rangle}$ .

Правильность приведенной выше конструкции во многом зависит от того факта, что толкающие и толкающие действия моделируемых машин ${ displaystyle M_ {1}}$ и ${ displaystyle M_ {2}}$ синхронизируются по считанным входным символам. Фактически, подобное моделирование уже невозможно для детерминированные автоматы выталкивания, поскольку более широкий класс детерминированных контекстно-свободных языков больше не замкнут при пересечении.

В отличие от конструкции конкатенации, показанной выше, конструкция дополнения для явно выталкивающих автоматов параллельна стандартной конструкции^[4] для детерминированных автоматов выталкивания.

Более того, как и класс контекстно-свободных языков, класс языков с явным выталкиванием закрывается под закрытие префикса и разворот, отсюда и закрытие суффикса.

Отношение к другим языковым классам

Алур и Мадхусудан (2004) обратите внимание на то, что языки с явным выталкиванием являются более общими, чем языки скобок, предложенные в Макнотон (1967). Как показано Креспи Регицци и Мандриоли (2012), явно выталкиваемые языки, в свою очередь, строго входят в класс языков, описанных грамматики приоритета операторов, которые были введены Флойд (1963) и пользоваться теми же свойствами и характеристиками закрытия (см. Lonati et al. (2015) для ω языков и характеризаций на основе логики и автоматов). В сравнении с конъюнктивные грамматики, обобщение контекстно-свободных грамматик, Охотин (2011) показывает, что линейные конъюнктивные языки образуют суперкласс явно вытесняемых языков. Таблица в конце этой статьи помещает семейство явно вытесняемых языков по отношению к другим языковым семьям в Иерархия Хомского Раджив Алур и Партхасарати Мадхусудан^[5]^[6] связывает подкласс обычных языков двоичного дерева с языками явно выталкивающего типа.

Другие модели описания

Заметно выталкивающие грамматики

Языки явно выталкивающего типа - это именно те языки, которые можно описать с помощью явно выталкивающие грамматики.^[2]

Заметно выталкивающие грамматики можно определить как ограничение контекстно-свободные грамматики. Заметная грамматика грамм определяется 4-кортеж:

${ Displaystyle G = (В = В ^ {0} чашка V ^ {1} ,, Sigma ,, R ,, S ,)}$ куда

${ Displaystyle V ^ {0} ,}$ и ${ Displaystyle V ^ {1} ,}$ непересекающиеся конечные множества; каждый элемент ${ displaystyle v in V}$ называется нетерминальный персонаж или Переменная. Каждая переменная представляет отдельный тип фразы или предложения в предложении. Каждая переменная определяет подъязык языка, определяемого ${ Displaystyle G ,}$ , и подязыки ${ Displaystyle V ^ {0} ,}$ без ожидающих вызовов или ожидающих возвратов.
${ Displaystyle Sigma ,}$ конечный набор Терминалs, не пересекается с ${ Displaystyle V ,}$ , которые составляют фактическое содержание предложения. Набор терминалов - это алфавит языка, определенный грамматикой ${ Displaystyle G ,}$ .
${ Displaystyle R ,}$ $Р,$ конечное отношение из ${ Displaystyle V ,}$ $V ,$ к ${ Displaystyle (В чашка Sigma) ^ {*}}$ $(В чашка Сигма) ^ {*}$ такой, что ${ Displaystyle существует , вес в (В чашка Sigma) ^ {*} :( S, ш) в R}$ $существует , w in (V cup Sigma) ^ {{*}} :( S, w) in R$ . Члены ${ Displaystyle R ,}$ $Р,$ называются (переписать) правилоs или производствоs грамматики. Есть три типа правил перезаписи. За ${ Displaystyle X, Y in V, Z in V ^ {0}}$ $X, Y in V, Z in V ^ {0}$ , ${ Displaystyle а ин { шляпа { Sigma}}}$ $а in { hat Sigma}$ и ${ displaystyle b in { hat { Sigma}}}$ $б in { hat Sigma}$
- ${ displaystyle X to epsilon}$
- ${ displaystyle X to aY}$ и если ${ Displaystyle X в V ^ {0}}$ тогда ${ displaystyle Y in V ^ {0}}$ и ${ displaystyle a in Sigma}$
- ${ displaystyle X to langle aZb rangle Y}$ и если ${ Displaystyle X в V ^ {0}}$ тогда ${ displaystyle Y in V ^ {0}}$
${ Displaystyle S в V ,}$ это начальная переменная (или же начальный символ), используемый для представления всего предложения (или программы).

Здесь звездочка обозначает Клини звезда операция и ${ displaystyle epsilon}$ это пустое слово.

Равномерные булевы схемы

Проблема в том, длинное ли слово ${ displaystyle ell}$ принимается данным вложенным словом автомат может быть решен единообразным логические схемы глубины ${ Displaystyle mathrm {O} ( log ell)}$ .^[2]

Логическое описание

Обычные языки по вложенным словам - это в точности набор языков, описанных монадический логика второго порядка с двумя унарными предикатами вызов и возвращаться, линейный преемник и отношение согласования ↝.^[2]

Смотрите также

Проверка модели

Примечания

^ Результаты поиска Google Scholar для "вложенных слов" ИЛИ "явно выдвигающегося вниз"
^ ^а ^б ^c ^d ^е ^ж Алур и Мадхусудан (2009)
^ ^а ^б Алур и Мадхусудан (2004)
^ Хопкрофт и Ульман (1979), п. 238 е).
^ Alur, R .; Мадхусудан, П. (2004). «Языки с явным раскрытием» (PDF). Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04. С. 202–211. Дои:10.1145/1007352.1007390. ISBN 978-1581138528.CS1 maint: ref = harv (связь) Раздел 4, теорема 5,
^ Alur, R .; Мадхусудан, П. (2009). «Добавление структуры вложенности к словам» (PDF). Журнал ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. Дои:10.1145/1516512.1516518.CS1 maint: ref = harv (связь) Раздел 7

внешняя ссылка

[1] Результаты поиска Google Scholar для "вложенных слов" ИЛИ "явно выдвигающегося вниз"

[AlurMadhu09-2] а ^б ^c ^d ^е ^ж Алур и Мадхусудан (2009)

[AlurMadhu04-3] а ^б Алур и Мадхусудан (2004)

[4] Хопкрофт и Ульман (1979), п. 238 е).

[Alur2004-5] Alur, R .; Мадхусудан, П. (2004). «Языки с явным раскрытием» (PDF). Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04. С. 202–211. Дои:10.1145/1007352.1007390. ISBN 978-1581138528.CS1 maint: ref = harv (связь) Раздел 4, теорема 5,

[Alur2009-6] Alur, R .; Мадхусудан, П. (2009). «Добавление структуры вложенности к словам» (PDF). Журнал ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. Дои:10.1145/1516512.1516518.CS1 maint: ref = harv (связь) Раздел 7

[1]

[2]

[3]

[4]

[5]

[6]