Well quasi ordering finite posets and formal languages
type: Item
instance of: scholarly article
title: Well quasi ordering finite posets and formal languages
zbMATH Open document ID: 0829.68076
author: Jens Gustedt
published in: Journal of Combinatorial Theory. Series B
publication date: 1996-01-15T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 798759
MaRDI profile type: Publication
full work available at URL: jctb.1995.1045
OpenAlex ID: W2084949487
DOI: 10.1006/JCTB.1995.1045
Recommended article: Well Quasi-orders in Formal Language Theory
Recommended article: On well quasiordering of finite languages
Recommended article: Well quasi-orders and regular languages
Recommended article: Q4273867
Recommended article: Q4452065
Recommended article: Well-quasi-orders and regular \(\omega\)-languages
Recommended article: Well quasi-orders and context-free grammars
Recommended article: Regular solutions of language inequalities and well quasi-orders
Recommended article: Automata, Languages and Programming
Recommended article: Well rewrite orderings and well quasi-orderings
description: scientific article; zbMATH DE number 798759