Further closure properties of input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion ins(L,K)={xyz|xz∈L,y∈K}, deletion del(L,K)={xz|xyz∈L,y∈K}, square root L={w|ww∈L}, the first half [Formula presented] and cyclic shift (Figure presented.). For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires exactly mn+2m states, as long as K is well-nested; deletion requires exactly 2n states, for well-nested K; square root requires n3−O(n2) states, for well-nested L; the well-nested subset of the first half is representable with 2O(n2) states; the well-nested subset of the cyclic shift requires exactly 2n2 states. Without the well-nestedness constraints, non-closure is established in each case.

Язык оригиналаанглийский
Страницы (с-по)65-77
ЖурналTheoretical Computer Science
Том798
Ранняя дата в режиме онлайн20 мая 2019
DOI
СостояниеОпубликовано - 17 дек 2019

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Further closure properties of input-driven pushdown automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать