Иерархии на обычных языках

14

Существует ли какая-либо известная «хорошая» иерархия L0L1L2 (может быть конечной) внутри класса регулярных языков ? К счастью, классы в каждой иерархии отражают различную выразительность / мощность / сложность. Кроме того, членство каждого класса «красиво» демонстрируется некоторыми элементами (в отличие от проблемы высоты звезды, которая может быть проблематичной).L

Спасибо!

raja.damanik
источник
3
Естественная иерархия - это та, которая индуцируется количеством состояний.
Марцио Де Биаси
9
Каноническая - это иерархия глубин точек, характеризующаяся чередованием кванторов в FO (<). По сути, чередование квантификаторов (логическое замыкание) дает вам надежные классы и иерархии.
Микаэль Кадилхак
Мне обоим кажется, что это очень хорошие ответы ...
Джошуа Грохов
4
Существует также высота звезды .
reinierpost
Что вы подразумеваете под «хорошей» иерархией по сравнению с «членством каждого класса,« красиво »демонстрируемым некоторыми элементами»? ». За пределами обычных языков, полиномиальная иерархия, кажется, считается хорошей иерархией, несмотря на то, что членство и даже существование реальной иерархии еще предстоит доказать.
J.-E. Pin

Ответы:

15

Вот список нескольких интересующих иерархий, некоторые из которых уже упоминались в других ответах.

  1. Конкатенация иерархий

Язык L является отмеченный продукт из L0,L1,,Ln , если L=L0a1L1anLn для некоторых букв 1 , ... , п . Иерархии конкатенации определяются чередующимися логическими операциями и полиномиальными операциями (= объединение и помеченный продукт). Иерархия Штраубинга-Териена (отправная точка { , A } )a1,,an{,A}) и иерархия глубины точек (начальная точка {,{1},A+,A})  относится к этому типу, но вы можете выбрать другие начальные точки, в частности, групповые языки (языки, принятые автоматом перестановок).

  1. Звездно-высотные иерархии

Общая схема состоит в подсчете минимального количества вложенных звездочек, необходимого для выражения языка, начинающегося с букв, но возможны несколько вариантов, в зависимости от того, какие основные операторы вы допускаете. Если вы разрешаете только объединение и произведение, вы определяете ограниченную высоту звезды, если вы разрешаете объединение, дополнение и произведение, вы определяете (обобщенную) высоту звезды, а если вы разрешаете объединение, пересечение и произведение, вы определяете промежуточную высоту звезды. , Существуют языки с ограниченным числом звездочек для каждого n, и он может эффективно вычислять высоту звезды данного обычного языка. Для высоты звезды звезда-высота 0 разрешима ( языки без звезды ), существуют языки высоты звезды 1nn01, но язык звездной высоты не известен! На промежуточной высоте звезды неизвестен результат. Смотрите эту статью для обзора.2

  1. Логические иерархии

Есть многие из них, но один из наиболее важных из них является так называемая иерархии. Формула называется Σ п -формула , если она эквивалентна формуле вида Q ( х 1 , . . . , Х к ) φ , где φ является квантификатором свободной и Q ( х 1 , . . . , Х k ) последовательность из nΣnΣnQ(x1,...,xk)φφQ(x1,...,xk)nблоки кванторов таким образом, что первый блок содержит только кванторы существования (обратите внимание , что этот первый блок может быть пустым), второй блок универсальные кванторы и т.д. Аналогично, если формируется из п Чередуя блоки кванторов, начинающиеся с блока универсальных квантификаторов (который опять может быть пустым), мы говорим, что φ является Π n- формулой. Обозначим через Σ n (соответственно Π n ) класс языков, которые можно определить с помощью Σ n -формулы (соответственно a ΠQ(x1,...,xk)nφΠnΣnΠnΣn формула) и B Σ n булево замыкание Σ n -языков. Пустьнаконец, Δ п = Σ пП п . Общая картина выглядит так. Нужно, конечно, указать подпись. Существует, как правило предикатадля каждой буквы (и через е средств есть буквав положении х в слове). Затем можно добавить двоичный символ <ΠnBΣnΣnΔn=ΣnΠnвведите описание изображения здесьaaxax<(соответствующая иерархия - иерархия Штраубинга-Териена), а также символ-преемник (соответствующая иерархия - иерархия глубины точек). Другие возможности включают в себя предиката, для подсчета по модулю N , и т.д. См снова эту бумагу для обзора.Modn

  1. Булевы иерархии

Общая закономерность (которая не характерна для обычных языков) обусловлена ​​Хаусдорфом. Пусть - класс языков, содержащий пустое множество и полный набор и замкнутый относительно конечного пересечения и конечного объединения. Пусть Д п ( Ь ) класс всех языков вида Х = Х 1 - Х 2 + ⋯ & plusmn ; Х п , где Х яL и X 1X 2X 3Х н . посколькуLDn(L)

X=X1X2+±Xn
XiLX1X2X3Xn, классы D п ( L ) определяют иерархию и их объединение логическое замыкание L . Опять же, возможны различные отправные точки.Dn(L)Dn+1(L)Dn(L)L
  1. Групповая сложность

Результат Крона-Родса (1966) гласит, что каждый DFA может быть смоделирован каскадом автоматов сброса (также называемых триггером) и автоматами, полугруппы переходов которых являются конечными группами. Групповая сложность языка - это наименьшее количество групп, участвующих в такой декомпозиции минимального DFA языка. Языки сложности - это языки без звезд, и существуют языки любой сложности. Однако эффективная характеристика языков сложности 1 не известна.01

  1. Иерархии унаследованы от сложности схемы

Отправной точкой является хорошая статья которой, в частности, показано, что класс A C 0R e g разрешим. Пусть A C C ( q ) = { L { 0 , 1 } L A C 0 M O D q } , где M O D q = { u { 0 , 1 }[1]AC0RegACC(q)={L{0,1}LAC0MODq} . Если q делит q , то A C C ( q ) A C C ( q ) . Интересный вопрос состоит в том, чтобы узнать,разрешимали A C C ( q ) R e g для любого q .MODq={u{0,1}|u|10modq}qqACC(q)ACC(q)ACC(q)Regq

Баррингтон, Дэвид А. Микс; Комптон, Кевин; Штраубинг, Говард; Териен, Денис. Обычные языки в N C 1 . J. Comput. System Sci. 44(1992)[1]NC1

J.-E. Штырь
источник
12

Расширяя комментарий: естественная иерархия - это та, которая вызвана количеством состояний DFA.

Мы можем определить Ln={L exists an n-states DFA D s.t. L(D)=L}

( , | Q | = n )D={Q,Σ,δ,q0,F}|Q|=n

Ясно, что (просто используйте мертвые состояния)LnLn+1

Чтобы показать правильное включение мы можем просто выбрать язык: L n + 1 = { a ii n } L n + 1LnLn+1Ln+1={aiin}Ln+1

Очень неформально: (минимальный) DFA, который распознает должен быть «цепочкой состояний» длиной n + 1 : q 0 a q 1 a . , , a q n , F = { q n } и q n a q n ( q n имеет самоконтроль). Так что n + 1 состояний достаточно, чтобы принять{aiin}n+1q0aq1a...aqnF={qn}qnaqnqnn+1 . Но каждый принимающий путь от q 0 до конечного состояния q f, который строго короче, чем n + 1, должен принимать некоторый a i с i < n, который не принадлежит L n + 1 , поэтому DFA с n или меньшим числом состояний не может принять L n + 1 .Ln+1q0qfn+1aii<nLn+1nLn+1

Марцио де Биаси
источник
8

Недавно я наткнулся на эту статью, которая может привести другой соответствующий пример (см. Последнее предложение тезисов):

Гийом Бонфанте, Флориан Делуп: Род регулярных языков.

Из аннотации: в статье определен и изучен род конечных состояний детерминированных автоматов (ФСА) и регулярных языков. Действительно, FSA можно рассматривать как график, для которого возникает понятие рода. В то же время, FSA имеет семантику через свой базовый язык. Тогда естественно установить связь между языками и понятием рода. После того, как мы вводим и оправдываем понятие рода для регулярных языков, [...] мы строим регулярные языки произвольного большого рода: понятие рода определяет правильную иерархию регулярных языков.

Дамиано Мазза
источник
5

Для обычных языков бесконечных слов существует несколько естественных иерархий, которые, например, передают понятие «сложность языка»:

  • Количество рангов, необходимых в автомате детерминированной четности
  • Вейджевая (или вагнеровская) иерархия: топологическая сложность, уровни .ωω

Эти иерархии могут быть обобщены для обычных языков бесконечных деревьев, для которых появляются новые иерархии, см., Например, этот ответ .

Денис
источник