Invisible pushdown languages

DOI10.1145/2933575.2933579MaRDI QIDQ4635951zbMATH OpenOpenAlexFDO

Authors Eryk Kopczyński

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.00289

zbMATH Keywords

XMLseparabilityvisibly pushdown automataregular languages of trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Context free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore some of these properties by making the structure of the tree visible, such as is done by visibly pushdown languages, or finite automata on trees. In this paper, we show that the structure given by such approaches remains invisible when it is read by a finite automaton (on word). In particular, we show that separability with a regular language is undecidable for visibly pushdown languages, just as it is undecidable for general context free languages.

Recommendations

• Visibly pushdown languages
• Regularity Problems for Visibly Pushdown Languages
• Automata, Languages and Programming
• On the Membership Problem for Visibly Pushdown Languages
• Visibly Pushdown Transducers

Cited in

(3)

• Resynchronized uniformization and definability problems for rational relations
• Regular separability of well-structured transition systems
• Regular separability of one counter automata

This page was built for publication: Invisible pushdown languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635951)