WQO is decidable for factorial languages

DOI10.1016/j.ic.2017.08.001zbMath1376.68083OpenAlexW2743994595MaRDI QIDQ2407108

Aistis Atminas, Vadim V. Lozin, Mikhail Ju. Moshkov

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10754/625350

zbMATH Keywords

permutationpolynomial-time algorithminduced subgraphwell-quasi-orderingfactorial language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations

Cites Work

• Unnamed Item
• Automata and forbidden words
• Partially well-ordered closed sets of permutations
• Graph minors. XX: Wagner's conjecture
• Labelled induced subgraphs and well-quasi-ordering
• When excluding one matroid prevents infinite antichains
• Well quasi-orders and regular languages
• Letter graphs and well-quasi-order by induced subgraphs
• Minimal antichains in well-founded quasi-orders with an application to tournaments
• An infinite antichain of permutations
• Two forbidden induced subgraphs and well-quasi-ordering
• Simple permutations: Decidability and unavoidable substructures
• The theory of well-quasi-ordering: a frequently discovered concept
• Subgraphs and well‐quasi‐ordering
• Deciding WQO for Factorial Languages
• Induced subgraphs and well‐quasi‐ordering
• Well-structured transition systems everywhere!