{"entities":{"Q1898732":{"pageid":1909474,"ns":120,"title":"Item:Q1898732","lastrevid":69228852,"modified":"2026-04-13T05:37:15Z","type":"item","id":"Q1898732","labels":{"en":{"language":"en","value":"Well quasi ordering finite posets and formal languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 798759"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898732$1F34CDEE-5699-4ADD-BC7C-6CB97BE33684","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff7c9fdeff44ce2a51c06334176e736f3f260f23","datavalue":{"value":{"text":"Well quasi ordering finite posets and formal languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898732$7556CB49-C231-4D78-82D7-9AEF5AA93570","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4bc08bf44fa3dbd9c60c566eafebf71dd02c04c","datavalue":{"value":"0829.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$19E90AE8-0AFE-42B9-A97A-BC3AE013C33C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e89db102d8bcca1d9e21dab092378fca0af3b615","datavalue":{"value":{"entity-type":"item","numeric-id":666106,"id":"Q666106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898732$E543621A-00B9-42B9-AA76-F2054CA1B44F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898732$DE8B290E-9DEE-4EBC-BA19-E70EC538C5B0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"556c75146a38246bf29cd3f9c2668d597d55ab94","datavalue":{"value":{"time":"+1996-01-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898732$882F6F8A-8499-4E38-9949-0913D8F946AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f248854a1bf82b9df4e321b4ffc673c590ea83f","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898732$69EA9158-31D2-4680-9B51-46F86E06B146","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$0CFDEB6E-AB90-4CDB-B777-1CF9E104CDCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$FC0E3D50-DE0B-4E13-BE98-4A1BDE4F7CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$046F4C49-9C23-4F64-BA7A-35CA6C50FF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$70ED8383-E750-4B76-B5EB-7F6280C734B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7939904086fb2c72b22d1717b9d99fade3a1565","datavalue":{"value":"798759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$81796C0C-119A-42CC-A8F4-A0063B076265","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898732$EB5735F0-51C4-4022-88D6-BFCEA9C522B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d892df915ace51a2e7ff3bc7a2b13c4df39e6c17","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1045","type":"string"},"datatype":"url"},"type":"statement","id":"Q1898732$FB142FE8-530C-4D03-8AEF-EDDD8AE74A0E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6d6f48127a5b0ab220eaebb0fd6442e94779763b","datavalue":{"value":"W2084949487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$453FAB42-4C71-4F71-AD8A-A15098CBBE38","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f7d1a79a8495ac384881170557e443d701ff008","datavalue":{"value":"10.1006/JCTB.1995.1045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898732$BF6C135C-FC53-46B7-84A3-94CF45F24E4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420f2d90a84e42e09ee8510bb2e2e5291c22b099","datavalue":{"value":{"entity-type":"item","numeric-id":3533001,"id":"Q3533001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8889d80998c9bb8f18914b1e5da4f8c7194dc9a7","datavalue":{"value":{"amount":"+0.94594157","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$D550FFC6-18F4-4737-BBDA-B0AE8486D14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd61075b7901f939396737670a55b11f958210a8","datavalue":{"value":{"entity-type":"item","numeric-id":1356526,"id":"Q1356526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7124b25c6cb19f1bc07cefe237739c19148ab23","datavalue":{"value":{"amount":"+0.9396334","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$5BE61620-9249-4E9E-8F92-EF74C88E6DD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4052ecbf118147c9b05d244f96136467523a7309","datavalue":{"value":{"entity-type":"item","numeric-id":1338899,"id":"Q1338899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a0e08da9397b8a3cfcd5db78ec7b9f567b6a9c9","datavalue":{"value":{"amount":"+0.93412864","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$2050F19D-6418-4E1F-B3FA-07324090A6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98dcb89d38cc74b9b582d21ba88a06d62ae3063d","datavalue":{"value":{"entity-type":"item","numeric-id":4273867,"id":"Q4273867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fbcb492507997b267bc14a34c53a9c6713f2b5f","datavalue":{"value":{"amount":"+0.9328678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$DF73D353-0E2B-4FA9-A29C-054FA8A6FFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cd25df5ec149c42e8bf9f6b1e2a7db0c9c50e7","datavalue":{"value":{"entity-type":"item","numeric-id":4452065,"id":"Q4452065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e53e6ab3369366d035500cc349ac37484a8e9b3c","datavalue":{"value":{"amount":"+0.9249598","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$9107063A-3359-40A2-922B-DD5F62B3CDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d53a4ae8851a3e3c503057692654d128f306d89","datavalue":{"value":{"entity-type":"item","numeric-id":1882913,"id":"Q1882913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc7d31af07042c0a08bdfed92339d812776f89c9","datavalue":{"value":{"amount":"+0.9136567","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$0F886BAE-3B2E-43FA-BD13-9DDE529E0FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"def65113e5ca1beb2fdf890eb88fc263d1c0cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":703570,"id":"Q703570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0c673bcded2dd2718519b3c48f27ebb95aad0fb","datavalue":{"value":{"amount":"+0.9029002","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$A8B4FBE7-29AE-47ED-AE91-4EB29DDA13C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72558690713edfe12160f7b6e71956288f2c490b","datavalue":{"value":{"entity-type":"item","numeric-id":2581271,"id":"Q2581271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aa8d1b8a3ee980ccf0b0b1bcf9e10c8d7d1818d","datavalue":{"value":{"amount":"+0.8935153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$FB0A419D-0E36-4CFA-89EB-A40E05A10991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1219b8cbcf6c99585644fde14bb750367242b55c","datavalue":{"value":{"entity-type":"item","numeric-id":5466521,"id":"Q5466521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aa8d1b8a3ee980ccf0b0b1bcf9e10c8d7d1818d","datavalue":{"value":{"amount":"+0.8935153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$76BFE355-811F-4E94-A733-9C8CD92E39A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba097bf580cc7b27edadc276aab081a24c5a3340","datavalue":{"value":{"entity-type":"item","numeric-id":1209622,"id":"Q1209622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5e8b6782bdcf112a2824f388bb489683a8e840","datavalue":{"value":{"amount":"+0.88467","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1898732$693D0548-F0A9-4992-829C-43C6F7DB4628","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Well quasi ordering finite posets and formal languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Well_quasi_ordering_finite_posets_and_formal_languages"}}}}}