The Ideal Approach to Computing Closed Subsets in Well-Quasi-Ordering

2019/04/24 by Jean Goubault-Larrecq, Goubault-Larrecq, Jean, Simon Halfon +7 · 1 citation
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1904.10703

Abstract

Elegant and general algorithms for handling upwards-closed and downwards-closed subsets of WQOs can be developed using the filter-based and ideal-based representation for these sets. These algorithms can be built in a generic or parameterized way, in parallel with the way complex WQOs are obtained by combining or modifying simpler WQOs.

Cited by

• Generalized Higman's Theorem and iterated ideals

Related

• Well Quasiorders and Hierarchy Theory
• Measuring well quasi-ordered finitary powersets
• PTL-separability and closures for WQOs on words
• A new order theory of set systems and better quasi-orderings
• On the ABK Conjecture, alpha-well Quasi Orders and Dress-Schiffels product