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

DOI10.1016/J.TCS.2007.04.003zbMATH Open1188.68170OpenAlexW2013770373MaRDI QIDQ995585FDOQ995585

Authors 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

context-free languagesbounded languagesrational relationsdecisional problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the structure and complexity of rational sets of regular languages
• scientific article; zbMATH DE number 3856432
• Independence results about context-free languages and lower bounds
• Context-Sensitive Languages, Rational Graphs and Determinism
• scientific article; zbMATH DE number 3880130
• scientific article; zbMATH DE number 3943060
• scientific article; zbMATH DE number 5519566
• A complete refinement procedure for regular separability of context-free languages
• On the separation question for tree languages
• On the separation question for tree languages

Cites work

• scientific article; zbMATH DE number 3880130 (Why is no real title available?)
• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1259068 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• A characterization of poly-slender context-free languages
• A regularity test for pushdown machines
• Bounded Regular Sets
• On the structure of the counting function of sparse context-free languages.
• Regularity and Related Problems for Deterministic Pushdown Automata
• Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable

Cited in

(5)

• The dissecting power of regular languages
• On bounded rational trace languages
• Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable
• Stefano Varricchio (1960-2008)
• A complete refinement procedure for regular separability of context-free languages

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

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