Invisible Pushdown Languages

DOI10.1145/2933575.2933579zbMATH Open1390.68403arXiv1511.00289OpenAlexW1903463847MaRDI QIDQ4635951FDOQ4635951

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)

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.

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)

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Resynchronized uniformization and definability problems for rational relations

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)