TY - JOUR

T1 - State Complexity of the Quotient Operation on Input-Driven Pushdown Automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2019/9/1

Y1 - 2019/9/1

N2 - The quotient of a formal language K by another language L is the set of all strings obtained by taking a string from K that ends with a suffix of a string from L, and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of languages recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be exactly m2n, where m and n are the numbers of states in the automata recognizing K and L, respectively.

AB - The quotient of a formal language K by another language L is the set of all strings obtained by taking a string from K that ends with a suffix of a string from L, and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of languages recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be exactly m2n, where m and n are the numbers of states in the automata recognizing K and L, respectively.

KW - closure properties

KW - Input-driven automata

KW - quotient

KW - state complexity

KW - visibly pushdown automata

KW - LANGUAGES

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

UR - http://www.mendeley.com/research/state-complexity-quotient-operation-inputdriven-pushdown-automata

U2 - 10.1142/S0129054119400367

DO - 10.1142/S0129054119400367

M3 - Article

AN - SCOPUS:85072917173

VL - 30

SP - 1217

EP - 1235

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 6-7

ER -