Another generalization of Higman's well quasi order result on \(\Sigma ^*\)

DOI10.1016/0012-365X(85)90176-1zbMath0583.68039OpenAlexW2078146321MaRDI QIDQ1069312

David Haussler

Publication date: 1985

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(85)90176-1

zbMATH Keywords

regular languagefinitely generated free monoiditerated shufflesubsequence embedding

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Termination of rewriting, Well quasi-orders generated by a word-shuffle rewriting, Well Quasi-orders in Formal Language Theory, Well quasi-orders and context-free grammars, Well quasi-orders, unavoidable sets, and derivation systems

Cites Work

• Unnamed Item
• On regularity of context-free languages
• On the complexity of iterated shuffle
• The power of synchronizing operations on strings
• The theory of well-quasi-ordering: a frequently discovered concept
• Software Descriptions with Flow Expressions
• Ordering by Divisibility in Abstract Algebras