Well quasi ordering finite posets and formal languages

DOI10.1006/JCTB.1995.1045MaRDI QIDQ1898732zbMATH OpenOpenAlexFDO

Authors Jens Gustedt

Publication date 15 January 1996

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1995.1045

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15)

Review text

We show that the set of finite posets is a well-quasi-ordering with respect to a certain relation \(\preceq\), called chain minor relation. To prove this we introduce a similar relation on finite formal languages which also has this property. As a consequence we get that every property which is hereditary with respect to \(\preceq\) has a test in \(O (|P |^c)\) whereas \(c\) depends on the property. This test has an easy parallelization with the same costs. On a parallel machine \(\text{(CRCW} \backslash \text{PRAM)}\) it may be implemented in such a way that it runs in constant time and needs \(O (|P |^c)\) processors.

Recommendations

• Well Quasi-orders in Formal Language Theory
• On well quasiordering of finite languages
• Well quasi-orders and regular languages
• scientific article; zbMATH DE number 475611
• scientific article; zbMATH DE number 2040909
• Well-quasi-orders and regular \(\omega\)-languages
• Well quasi-orders and context-free grammars
• Regular solutions of language inequalities and well quasi-orders
• Automata, Languages and Programming
• Well rewrite orderings and well quasi-orderings

Cited in

(12)

• A new class of unique product monoids with applications to ring theory.
• On quasi orders of words and the confluence property
• On well quasiordering of finite languages
• A note on well quasi-orderings for powersets
• Chain minors are FPT
• Well-quasi-orders and regular \(\omega\)-languages
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• Well Quasi-orders in Formal Language Theory
• scientific article; zbMATH DE number 108280 (Why is no real title available?)
• scientific article; zbMATH DE number 475611 (Why is no real title available?)
• Automata, Languages and Programming
• Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations

This page was built for publication: Well quasi ordering finite posets and formal languages

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