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
UR - http://www.scopus.com/inward/record.url?scp=85067178569&partnerID=8YFLogxK
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 -