{"entities":{"Q688156":{"pageid":690005,"ns":120,"title":"Item:Q688156","lastrevid":63490071,"modified":"2026-04-11T13:30:43Z","type":"item","id":"Q688156","labels":{"en":{"language":"en","value":"Partial orders on words, minimal elements of regular languages, and state complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440332"}},"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":"Q688156$3733EE94-56B2-4DCC-B26C-5771ABCB8CBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a0479ffb2b80b8cdb3d849a92bbdf52ce4f525a","datavalue":{"value":{"text":"Partial orders on words, minimal elements of regular languages, and state complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688156$F5E03FAF-B760-4454-837D-6562EE50F4F8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04db4ce465b74cbafb7e8a89bc9ec4e91b25f4c7","datavalue":{"value":"0786.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$7ACA6E98-E8F9-4F9E-BFA8-784E5657CF70","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a5ba4e291ad27fa52326e6a9622c97e6ef56079","datavalue":{"value":"10.1016/0304-3975(93)90160-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$B41424EB-ED7D-48F2-9E05-9574EA966549","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$71025C90-5BC7-4E27-A6B8-816D253653AD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38c18755801a88dcd8669b172a905f586b29f555","datavalue":{"value":{"time":"+1994-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688156$47A35801-B78A-4845-9E19-D829806B8194","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c1e7e38ce6b0cff61fc12b195f28ddced5e260d","datavalue":{"value":"Having a paratial order (po) on strings, \\(MIN(L)\\) is the set of all minimal elements of the language \\(L\\) w.r.t. the po. The paper shows that if \\(L\\) is regular then so is \\(MIN(L)\\) for po's like the generalized prefix (suffix, subsegment, subsequence) order; ``generalized'' supposes a po on the alphabet -- the identity leads to the ``usual'' meaning. Note that a well-known result of Higman implies the finiteness of \\(MIN(L)\\) for the generalized subsequence order. Moreover, if \\(L\\) is recognized by a deterministic finite automaton (DFA) with \\(n\\) states then \\(MIN(L)\\) is recognizable by a DFA with roughly \\(2^ n\\) states. The author shows the upper bounds more precisely, thus extending and improving some results of Kundu.   Nevertheless, the main value of the paper lies in proving the \\textit{lower bounds}, by which the given upper bounds are shown to be tight, even if we consider nondeterministic FA's for \\(MIN(L)\\). An exponential lower bound is also shown for the case with a 4-letter alphabet.   The ideas are also used for a new proof of the theorem by Sakoda and Sipser showing the exponential growth of the number of states going from an NFA to an NFA recognizing the complementary language.   For completeness, the author also shows that regularity of \\(L\\) implies regularity of \\(MIN(L)\\) w.r.t. the generalized dictionary and lexical orders; in that case the relevant growth of states is nor \\(n^ 2\\), respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688156$C87CF817-0B4E-4183-AD27-9AF246AAFA6C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aa98ea30b6abca7b476f74745e2df6c0f45b70be","datavalue":{"value":{"entity-type":"item","numeric-id":672325,"id":"Q672325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$55C18A89-D592-4B4E-A403-D9C5DD299A30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$202762D1-8F37-41D7-8AE8-6368D2E6CFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$B61CBEDD-21C9-431E-A797-86E017EDCC36","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7f7100d1a3b009c8ac70a8d0ec438594c8019a26","datavalue":{"value":"440332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$A65ABAE0-8436-418F-A71A-9A04C1E7955A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q688156$866F7133-23B5-4256-A551-7C0FD8AF1765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q688156$54DE736E-8021-4A2E-874D-05FE4ECCDDF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b10ab4d2fc75823309415cc3027a505ded7b2f","datavalue":{"value":"state complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q688156$F8190877-717D-4DCF-8D93-80ED13E9279D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3b09a2009bb1057f03e376b98d8a8d1c4cbc96a4","datavalue":{"value":"Q57380781","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$70F1F8AD-FA30-46EE-95A6-172CFA9C3F53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1af85c7b2f6fd07526dd5f6ad7e9d1c876779e29","datavalue":{"value":{"entity-type":"item","numeric-id":766115,"id":"Q766115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$808DD0C0-F30A-4825-BE96-9F8FBA3A782C","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":"Q688156$5EA7127A-9930-4B19-930D-077824115815","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a06e230e7b73eabdd63bab75c3b9a6a8ab5b6","datavalue":{"value":{"entity-type":"item","numeric-id":5289271,"id":"Q5289271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$B836FE2D-0304-4F99-BA7B-A50AA2F60FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$D30FD2E5-9D56-4AD4-8B8B-21BAF5016355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58709679cfff7718457ae5dbfaa34a4e9b17219c","datavalue":{"value":{"entity-type":"item","numeric-id":5812263,"id":"Q5812263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$BC77DA2F-5EDE-413B-94C4-3069312230BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$B9615058-7D5D-42E0-BA68-FB06D8C2D341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c57448c3511c30ed92e5fbbbe68c6f2b95237a20","datavalue":{"value":{"entity-type":"item","numeric-id":2554710,"id":"Q2554710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$B691F674-8BF4-482A-AD66-3B23C358FC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6550549f6a6ae41859a83760194e81ec3591e36","datavalue":{"value":{"entity-type":"item","numeric-id":1151754,"id":"Q1151754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$221C3FA4-F890-4FBE-8491-E75B9520BBB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$60A96A21-504A-4F04-B3E0-B3842347A8A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb004b1be4350753257ab07ed1e083520f747b0","datavalue":{"value":{"entity-type":"item","numeric-id":807021,"id":"Q807021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$37F4B785-4273-4418-A41C-4F8E09674A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd7c6229f4b94d10acb3721769855cfef4d3336a","datavalue":{"value":{"entity-type":"item","numeric-id":5402568,"id":"Q5402568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688156$593F3561-FB69-411D-A40E-678A662FF6BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"73fd62c44250819be251b0d2361bcc53ebad6e4a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90160-u","type":"string"},"datatype":"url"},"type":"statement","id":"Q688156$B70564D9-6A73-48B5-A490-6ED85BE21336","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8cbe31a9d476e10851082713692abfb0f2dfb70","datavalue":{"value":"W1991409518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688156$EA7B7767-5878-4E07-A890-17006DA8357A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63bdce7ce0a8e888053bf8fcabb7b6e748533e5c","datavalue":{"value":{"entity-type":"item","numeric-id":807021,"id":"Q807021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"342b0ed96cf6ef5e23b1692a1b41d70fc931598a","datavalue":{"value":{"amount":"+0.859341025352478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q688156$64C1A5F6-90B0-4181-AB6F-8731DBBA73FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced4ca18a58c46210cfd0d4d36210a4a001f6b18","datavalue":{"value":{"entity-type":"item","numeric-id":1341751,"id":"Q1341751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9941ca979c79429140ebdd6afc017cd295840e60","datavalue":{"value":{"amount":"+0.807600736618042","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q688156$DEAF04AB-C2CD-4DF6-B378-BACCCE823B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9476b1031e32f8685163dafaf940e382f7005602","datavalue":{"value":{"entity-type":"item","numeric-id":5496192,"id":"Q5496192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca0842593bf5d29ccf3c646a76442b89db44be68","datavalue":{"value":{"amount":"+0.7753271460533142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q688156$8F005B83-189E-470B-80B2-25D3CC3ACA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b42b6bc4e2c20386b6667e5be9d821e1dabc2c9","datavalue":{"value":{"entity-type":"item","numeric-id":1943687,"id":"Q1943687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"540aef95ce5657f5c1e1a257fcf7acbde7efc29c","datavalue":{"value":{"amount":"+0.7704206109046936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q688156$B535A615-5D5C-4E75-AB88-09AB74CF95C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"284b5525a2f9b6dc01739b6a823cee5137564baa","datavalue":{"value":{"entity-type":"item","numeric-id":1199879,"id":"Q1199879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2e5ca1ffb9faad42fbd23ac55b89657ee3bf40e","datavalue":{"value":{"amount":"+0.7696757316589355","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q688156$1F8DF101-02D7-4943-882E-0D1BD811FE25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Partial orders on words, minimal elements of regular languages, and state complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Partial_orders_on_words,_minimal_elements_of_regular_languages,_and_state_complexity"}}}}}