The Quotient Operation on Input-Driven Pushdown Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

The Quotient Operation on Input-Driven Pushdown Automata

Alexander Okhotin
  • Fonction : Auteur
  • PersonId : 1024589
Kai Salomaa
  • Fonction : Auteur
  • PersonId : 1022715

Résumé

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.
Fichier principal
Vignette du fichier
440206_1_En_24_Chapter.pdf (342.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01657008 , version 1 (06-12-2017)

Licence

Paternité

Identifiants

Citer

Alexander Okhotin, Kai Salomaa. The Quotient Operation on Input-Driven Pushdown Automata. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.299-310, ⟨10.1007/978-3-319-60252-3_24⟩. ⟨hal-01657008⟩
117 Consultations
161 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More