Decidability in geometric grid classes of permutations

DOI10.1090/PROC/17083MaRDI QIDQ7028984zbMATH OpenFDO

Authors Samuel Braunfeld

Publication date 11 February 2025

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/PROC/17083

zbMATH Keywords

graph classes of bounded lettericitymonadic second-order logic

Mathematics Subject Classification ID

Higher-order logic (03B16) Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45) Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Cites work

• Algebraic and geometric methods in enumerative combinatorics
• An algorithm computing combinatorial specifications of permutation classes
• Combinatorics on traces
• Geometric grid classes of permutations
• scientific article; zbMATH DE number 475617 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Inflations of geometric grid classes of permutations
• Labelled well-quasi-order for permutation classes
• Letter graphs and geometric grid classes of permutations
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Monadic stability and growth rates of ω$\omega$‐categorical structures
• On computing graph minor obstruction sets
• On the effective and automatic enumeration of polynomial permutation classes
• Permutation classes
• The Complexity of Translating Logic to Finite Automata
• The enumeration of permutations avoiding 3124 and 4312
• Well quasi-order in combinatorics: embeddings and homomorphisms

Cited in

(2)

• Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
• On the asymptotic enumeration and limit shapes of monotone grid classes of permutations

This page was built for publication: Decidability in geometric grid classes of permutations

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