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

В информатике , а точнее в теории автоматов и формального языка , вложенные слова - это концепция, предложенная Алуром и Мадхусуданом как совместное обобщение слов , которые традиционно используются для моделирования линейно упорядоченных структур, и упорядоченных деревьев без ранжирования , которые традиционно используются для моделирования. иерархические структуры. Приемники конечных состояний для вложенных слов, так называемые автоматы вложенных слов , затем дают более выразительное обобщение конечных автоматов на словах. Линейные кодировки языков, принимаемые конечными автоматами с вложенными словами, дают классявно выталкивающие языки . Последний языковой класс должным образом находится между обычными языками и детерминированными контекстно-свободными языками . С момента своего появления в 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. все ребра вложения направлены вперед, то есть если i  ↝  j, то i  <  j ;
2. ребра вложенности никогда не имеют общего конечного положения, то есть для −∞ <  i  <∞ существует не более одной позиции h, такой что h  ↝  i , и не более одной позиции j, такой что i ↝ j ; и
3. ребра вложенности никогда не пересекаются, то есть не существует таких i  <  i  ′ ≤  j  <  j  ′ , что i  ↝  j и i  ′ ↝  j  ′ .

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

• положение вызова , если я ↝ J для некоторого J ,
• в ожидании вызова , если я ↝ ∞,
• позиция возврата , если ч ↝ я в течение некоторого ч ,
• в ожидании возвращения , если -∞ ↝ я , и
• внутреннее положение во всех остальных случаях.

Вложенное слово длины над алфавитом Е является парой ( ш , ↝), где W представляет собой слово или строка , длины над Е и ↝ комбинационного отношение длиной .${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle \ell }$

Кодирование вложенных слов в обычные слова [ править ]

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

Пример [ править ]

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

Автоматы [ править ]

Вложенный словарный автомат [ править ]

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

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

Заметно выталкивающий автомат [ править ]

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

Следуя Алуру и Мадхусудану ^[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}$

Недетерминированные явно выдвигающиеся автоматы [ править ]

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

Проблемы с решением [ править ]

Пусть - размер описания автомата , тогда можно проверить, принято ли слово n автоматом во времени . В частности, во времени разрешима проблема пустоты . Если фиксировано, оно разрешимо во времени и пространстве, где - глубина n в потоковом видении. Оно также разрешимо с помощью пространства и времени , а также с помощью однородной логической схемы глубины . ^[2]${\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 )}$

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

Языки [ править ]

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

Свойства закрытия [ править ]

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

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

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

• Клини звезда
• конкатенация

Для операции пересечения можно построить VPA M, моделирующую два заданных VPA, и с помощью простой конструкции произведения ( Alur & Madhusudan 2004 ): For , предположить , задано как . Тогда для автомата M набор состояний равен , начальное состояние , набор конечных состояний , алфавит стека равен , а начальный символ стека равен .${\displaystyle M_{1}}$${\displaystyle M_{2}}$${\displaystyle i=1,2}$${\displaystyle M_{i}}$${\displaystyle (Q_{i},\ {\hat {\Sigma }},\ \Gamma _{i},\ \delta _{i},\ s_{i},\ Z_{i},\ F_{i})}$${\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) . Как показали Crespi Reghizzi & Mandrioli (2012) , явно выталкиваемые языки, в свою очередь, строго содержатся в классе языков, описываемых грамматиками приоритета операторов , которые были введены Флойдом (1963) и обладают теми же свойствами и характеристиками замыкания (см. Lonati et al. (2015) для ω языков и характеризаций на основе логики и автоматов). По сравнению с конъюнктивными грамматиками , обобщением контекстно-свободных грамматик, Охотин (2011) harvtxt error: no target: CITEREFOkhotin2011 (help)показывает, что линейные конъюнктивные языки образуют суперкласс явно вытесняемых языков. Таблица в конце этой статьи помещает семейство явно вытесняемых языков по отношению к другим языковым семьям в иерархии Хомского . Раджив Алур и Партасарати Мадхусудан ^{[5] [6]} связали подкласс регулярных языков двоичных деревьев с языками, явно вытесняющими их вниз.

Другие модели описания [ править ]

Визуально разворачиваемый грамматик [ править ]

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

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

${\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\,}$${\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 }$

Однородные логические схемы [ править ]

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

Логическое описание [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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