Another generalization of Higman's well quasi order result on ^*

DOI10.1016/0012-365X(85)90176-1zbMATH Open0583.68039OpenAlexW2078146321MaRDI QIDQ1069312FDOQ1069312

Authors 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)

Recommendations

• On well-quasi-ordering finite sequences
• Well quasi-orders generated by a word-shuffle rewriting
• Well Quasi-orders in Formal Language Theory
• On well quasiordering of finite languages
• Well Quasi Orders and the Shuffle Closure of Finite Sets

Cites work

• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• On regularity of context-free languages
• On the complexity of iterated shuffle
• Ordering by Divisibility in Abstract Algebras
• Software Descriptions with Flow Expressions
• The power of synchronizing operations on strings
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(11)

• Well quasi-orders, unavoidable sets, and derivation systems
• Well Quasi Orders and the Shuffle Closure of Finite Sets
• Well quasi-orders generated by a word-shuffle rewriting
• Une généralisation des théorèmes de Higman et de Simon aux mots infinis
• Well quasi-orders and context-free grammars
• Well-quasi-ordering and the Hausdorff quasi-uniformity
• Galvin's question on non-\( \sigma \)-well ordered linear orders
• \(\Sigma_1\)-wellorders without collapsing
• Developments in Language Theory
• Well Quasi-orders in Formal Language Theory
• Termination of rewriting

This page was built for publication: Another generalization of Higman's well quasi order result on \(\Sigma ^*\)

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