Well quasi-orders and context-free grammars

DOI10.1016/j.tcs.2004.03.069zbMath1071.68033OpenAlexW2003401299MaRDI QIDQ703570

Flavio D'Alessandro, Stefano Varricchio

Publication date: 11 January 2005

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

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

zbMATH Keywords

Context-free grammarsUnavoidable sets of wordsWell quasi-orders

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (5)

A characterization of (regular) circular languages generated by monotone complete splicing systems ⋮ Well quasi-orders generated by a word-shuffle rewriting ⋮ Well Quasi-orders in Formal Language Theory ⋮ Stefano Varricchio (1960-2008) ⋮ Well quasi-orders, unavoidable sets, and derivation systems

Cites Work

• Unnamed Item
• Unnamed Item
• On regularity of context-free languages
• Another generalization of Higman's well quasi order result on \(\Sigma ^*\)
• On the regularity of languages on a binary alphabet generated by copying systems
• On well quasi orders of free monoids
• On quasi orders of words and the confluence property
• Well quasi-orders and regular languages
• On the generalization of Higman and Kruskal's theorems to regular languages and rational trees
• The theory of well-quasi-ordering: a frequently discovered concept
• Ordering by Divisibility in Abstract Algebras

This page was built for publication: Well quasi-orders and context-free grammars