The Quotient Operation on Input-Driven Pushdown Automata

Abstract : 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 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 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 $m^2n + O(m)$, where m and n is the number of states in the automata recognizing K and L, respectively.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.299-310, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_24〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657008
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:14
Dernière modification le : dimanche 25 février 2018 - 14:48:02

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Alexander Okhotin, Kai Salomaa. The Quotient Operation on Input-Driven Pushdown Automata. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.299-310, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_24〉. 〈hal-01657008〉

Partager

Métriques

Consultations de la notice

67