Вложенное слово

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

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

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

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

1. все ребра вложенности направлены вперед, то есть если i ↝ j , то i < j ;
2. ребра вложения никогда не имеют общей конечной позиции, то есть для −∞ < i < ∞ существует не более одной позиции h такой, что h ↝ i , и существует не более одной позиции j такой, что i ↝ j ; и
3. ребра вложения никогда не пересекаются, то есть не существует i < i ′ ≤ j < j ′ таких, что и i ↝ j , и i ′ ↝ j ′ .

Позиция i называется

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

Вложенное слово длины $\ell$ над алфавитом Σ — это пара ( w ,↝), где w — слово или строка длины $\ell$ над Σ и ↝ является отношением согласования длины $\ell$.

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

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

Пример

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

Автоматический

Автомат вложенных слов

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

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

Видимый автомат с выдвижным механизмом

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

Вслед за Алуром и Мадхусуданом, детерминированный автомат с видимым нажатием формально определяется как 6-кортежный $M=(Q,{\hat {\Sigma }},\Gamma ,\delta ,q_{0},F)$ где

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

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

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

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

Недетерминированные автоматы с видимым нажатием

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

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

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

Для двух недетерминированных автоматов A и B решение о том, является ли набор слов, принятый A , подмножеством слова, принятого B , является EXPTIME -полным. Также EXPTIME-полный, чтобы выяснить, есть ли недопустимое слово.

Языки

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

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

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

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

таким образом давая начало булевой алгебре .

• Клини звезда
• конкатенация
• разворот
• Струнный гомоморфизм

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

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

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

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

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

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

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

Связь с другими языковыми классами

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

Описание других моделей

Видимые грамматики с выталкиванием вниз

Языки с видимым расширением — это именно те языки, которые можно описать с помощью грамматик с видимым расширением .

Визуально раскрывающиеся грамматики можно определить как ограничение контекстно-свободных грамматик . Визуально раскрывающаяся грамматика G определяется четырехкортежом :

$G=(V=V^{0}\cup V^{1}\,,\Sigma \,,R\,,S\,)$ где

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

Здесь звездочка обозначает операцию звезды Клини , а $\epsilon$ это пустое слово.

Равномерные логические схемы

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

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

Регулярные языки над вложенными словами — это в точности набор языков, описываемых монадической логикой второго порядка с двумя унарными предикатами call и return , линейным преемником и отношением соответствия ↝.

См. также

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

Ссылки

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

Внешние ссылки

• Вложенные слова и языки с видимым смещением вниз
• Видимые автоматы с нажатием вниз - автоматы на вложенных словах.
• класс VPL в зоопарке «Комплексити»