Further closure properties of input-driven pushdown automata

Standard

Further closure properties of input-driven pushdown automata. / Okhotin, Alexander; Salomaa, Kai.

In: Theoretical Computer Science, Vol. 798, 17.12.2019, p. 65-77.

Research output: Contribution to journal › Article › peer-review

Author

Okhotin, Alexander ; Salomaa, Kai. / Further closure properties of input-driven pushdown automata. In: Theoretical Computer Science. 2019 ; Vol. 798. pp. 65-77.

BibTeX

@article{2a74437a2f0348e7b48ddb6184c90503,

title = "Further closure properties of input-driven pushdown automata",

abstract = "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.",

keywords = "Cyclic shift, Deletion, Input-driven automata, Insertion, Proportional removals, Square root, Visibly pushdown automata, STATE COMPLEXITY, REGULAR LANGUAGES",

author = "Alexander Okhotin and Kai Salomaa",

year = "2019",

month = dec,

day = "17",

doi = "10.1016/j.tcs.2019.04.006",

language = "English",

volume = "798",

pages = "65--77",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Further closure properties of input-driven pushdown automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2019/12/17

Y1 - 2019/12/17

N2 - 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.

AB - 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.

KW - Cyclic shift

KW - Deletion

KW - Input-driven automata

KW - Insertion

KW - Proportional removals

KW - Square root

KW - Visibly pushdown automata

KW - STATE COMPLEXITY

KW - REGULAR LANGUAGES

UR - http://www.scopus.com/inward/record.url?scp=85067178569&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/further-closure-properties-inputdriven-pushdown-automata

U2 - 10.1016/j.tcs.2019.04.006

DO - 10.1016/j.tcs.2019.04.006

M3 - Article

AN - SCOPUS:85067178569

VL - 798

SP - 65

EP - 77

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 49647708