Вложенное слово - 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 \}}$ такой, что:

1. все грани вложения направлены вперед, т.е. если я ↝ j тогда я < j;
2. ребра вложенности никогда не имеют общего конечного положения, то есть для −∞ < я < ∞, есть не более одной позиции час такой, что час ↝ я, и есть не более одной позиции j такой, что я ↝ j; и
3. края вложенности никогда не пересекаются, то есть нет я < я ′ ≤ 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}=a}$ и я - это (возможно, ожидающая) позиция вызова, внутренняя позиция и (возможно, ожидающая) позиция возврата соответственно.

Пример

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

Автоматы

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

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

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

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

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

Следуя за Алуром и Мадхусуданом,^[2] детерминированный автомат с видимым выталкиванием формально определяется как набор из 6 ${\displaystyle M=(Q,{\hat {\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}}}$ это функция перехода, который разделен на три части, соответствующие переходам вызовов, переходам возврата и внутренним переходам, а именно
  • ${\displaystyle \delta _{\text{c}}\colon Q\times \Sigma _{\text{c}}\to Q\times \Gamma }$, то вызов функции перехода
  • ${\displaystyle \delta _{\text{r}}\colon 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\subseteq 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 O(|A|^{3}\ell )}$. В частности, проблема пустоты решается во времени. ${\displaystyle O(|A|^{3})}$.Если ${\displaystyle A}$ фиксировано, разрешимо во времени ${\displaystyle O(\ell )}$ и космос ${\displaystyle O(d)}$ куда ${\displaystyle d}$ глубина п в потоковом видении. Это также разрешимо с пространством ${\displaystyle O(\log(\ell ))}$ и время ${\displaystyle O(\ell ^{2}\log(\ell ))}$, и равномерной логической схемой глубины ${\displaystyle O(\log \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_{i})}$. Тогда для автомата 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 _{i}}$ символ стека выталкивается ${\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 _{i}}$ символ стека появляется ${\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) Ошибка harvtxt: нет цели: CITEREFOkhotin2011 (помощь) показывает, что линейные конъюнктивные языки образуют суперкласс явно вытесняемых языков. Таблица в конце этой статьи помещает семейство явно вытесняемых языков по отношению к другим языковым семьям в Иерархия Хомского Раджив Алур и Партхасарати Мадхусудан^[5][6] связывает подкласс обычных языков двоичного дерева с языками явно выталкивающего типа.

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

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

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

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

${\displaystyle G=(V=V^{0}\cup 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\,}$ к ${\displaystyle (V\cup \Sigma )^{*}}$ такой, что ${\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R}$. Члены ${\displaystyle R\,}$ называются (переписать) правилоs или производствоs грамматики. Есть три типа правил перезаписи. За ${\displaystyle X,Y\in V,Z\in V^{0}}$, ${\displaystyle a\in {\hat {\Sigma }}}$ и ${\displaystyle b\in {\hat {\Sigma }}}$
  • ${\displaystyle X\to \epsilon }$
  • ${\displaystyle X\to aY}$ и если ${\displaystyle X\in V^{0}}$ тогда ${\displaystyle Y\in V^{0}}$ и ${\displaystyle a\in \Sigma }$
  • ${\displaystyle X\to \langle aZb\rangle Y}$ и если ${\displaystyle X\in V^{0}}$ тогда ${\displaystyle Y\in V^{0}}$
• ${\displaystyle S\in V\,}$ это начальная переменная (или же начальный символ), используемый для представления всего предложения (или программы).

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

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

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

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

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

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

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

Примечания

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

Рекомендации

• Флойд, Р. В. (Июль 1963 г.). «Синтаксический анализ и приоритет операторов». Журнал ACM. 10 (3): 316–333. Дои:10.1145/321172.321179.
• Макнотон Р. (1967). "Скобки грамматики". Журнал ACM. 14 (3): 490–500. Дои:10.1145/321406.321411.
• Alur, R .; Арены, М .; Barcelo, P .; Этессами, К .; Иммерман, Н .; Либкин, Л. (2008). Грэдель, Эрих (ред.). «Первого порядка и временная логика для вложенных слов». Логические методы в информатике. 4 (4). arXiv:0811.0537. Дои:10.2168 / LMCS-4 (4:11) 2008 г..
• Креспи Регицци, Стефано; Мандриоли, Дино (2012). «Приоритет оператора и свойство видимого раскрытия» (PDF). Журнал компьютерных и системных наук. 78 (6): 1837–1867. Дои:10.1016 / j.jcss.2011.12.006. Архивировано из оригинал (PDF) на 2017-08-09. Получено 2014-02-11.
• Лонати, Виолетта; Мандриоли, Дино; Панелла, Федерика; Праделла, Маттео (2015). «Языки приоритета операторов: их автоматно-теоретическая и логическая характеризация». SIAM Журнал по вычислениям. 44 (4): 1026–1088. Дои:10.1137/140978818. HDL:2434/352809.
• Охотин Александр: Сравнение линейных конъюнктивных языков с подсемействами контекстно-свободных языков, 37-я Международная конференция «Современные тенденции в теории и практике компьютерных наук» (СОФСЕМ 2011).
• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. ISBN  978-0-201-02988-8.

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

• Вложенные слова и языки с явным раскрытием
• Заметно выталкивающие автоматы - Автоматы по вложенным словам
• класс VPL на Зоопарк сложности