Regularity Problems for Visibly Pushdown Languages. Bárány, V., Löding, C., & Serre, O. In Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2006), volume 3884, of Lecture Notes in Computer Science, pages 420-431, 2006. Springer-Verlag. abstract bibtex Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.
@inproceedings{BaranyLS06,
keywords = {perso,conf},
author = {Vince Bárány and
Christof Löding and
Olivier Serre},
title = {Regularity Problems for Visibly Pushdown Languages},
booktitle = {Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2006)},
year = {2006},
pages = {420-431},
volume = {3884},
publisher = "Springer-Verlag",
series = "Lecture Notes in Computer Science",
abstract = {Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.},
fulltexturl = {http://hal.archives-ouvertes.fr/hal-00016661},
}
Downloads: 0
{"_id":"QyKPkZaXTrvWjak8f","bibbaseid":"baacuteraacuteny-lding-serre-regularityproblemsforvisiblypushdownlanguages-2006","authorIDs":[],"author_short":["Bárány, V.","Löding, C.","Serre, O."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","keywords":"perso,conf","author":[{"firstnames":["Vince"],"propositions":[],"lastnames":["Bárány"],"suffixes":[]},{"firstnames":["Christof"],"propositions":[],"lastnames":["Löding"],"suffixes":[]},{"firstnames":["Olivier"],"propositions":[],"lastnames":["Serre"],"suffixes":[]}],"title":"Regularity Problems for Visibly Pushdown Languages","booktitle":"Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2006)","year":"2006","pages":"420-431","volume":"3884","publisher":"Springer-Verlag","series":"Lecture Notes in Computer Science","abstract":"Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.","fulltexturl":"http://hal.archives-ouvertes.fr/hal-00016661","bibtex":"@inproceedings{BaranyLS06,\n keywords = {perso,conf},\n author = {Vince Bárány and\n Christof Löding and\n Olivier Serre},\n title = {Regularity Problems for Visibly Pushdown Languages},\n booktitle = {Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2006)},\n year = {2006},\n pages = {420-431},\n volume = {3884},\n publisher = \"Springer-Verlag\",\n series = \"Lecture Notes in Computer Science\",\nabstract = {Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.},\nfulltexturl = {http://hal.archives-ouvertes.fr/hal-00016661},\n}\n\n","author_short":["Bárány, V.","Löding, C.","Serre, O."],"key":"BaranyLS06","id":"BaranyLS06","bibbaseid":"baacuteraacuteny-lding-serre-regularityproblemsforvisiblypushdownlanguages-2006","role":"author","urls":{},"keyword":["perso","conf"],"downloads":0},"bibtype":"inproceedings","biburl":"https://www.irif.fr/~serre/bibtex/conferences.bib","creationDate":"2019-05-07T09:10:55.259Z","downloads":0,"keywords":["perso","conf"],"search_terms":["regularity","problems","visibly","pushdown","languages","bárány","löding","serre"],"title":"Regularity Problems for Visibly Pushdown Languages","year":2006,"dataSources":["ymsPGsaH2xrv3xowd"]}