On the separability of sparse context-free languages and of bounded rational relations

DOI10.1016/j.tcs.2007.04.003zbMath1188.68170OpenAlexW2013770373MaRDI QIDQ995585

Christian Choffrut, Stefano Varricchio, Flavio D'Alessandro

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.003

zbMATH Keywords

bounded languagescontext-free languagesrational relationsdecisional problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

On bounded rational trace languages ⋮ Stefano Varricchio (1960-2008)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable
• On the structure of the counting function of sparse context-free languages.
• Regularity and Related Problems for Deterministic Pushdown Automata
• A characterization of poly-slender context-free languages
• Bounded Regular Sets
• A regularity test for pushdown machines

This page was built for publication: On the separability of sparse context-free languages and of bounded rational relations