{"entities":{"Q807021":{"pageid":808869,"ns":120,"title":"Item:Q807021","lastrevid":64480788,"modified":"2026-04-11T20:10:15Z","type":"item","id":"Q807021","labels":{"en":{"language":"en","value":"Minimal strings in a regular language with respect to a partial order on the alphabet"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4205993"}},"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":"Q807021$8FA76415-2DA1-4FC2-B7F2-665EDF2C9EDB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b6873316bdd5421e5063181452f022fe1cbe8bd","datavalue":{"value":{"text":"Minimal strings in a regular language with respect to a partial order on the alphabet","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807021$692E14C0-6A6F-4749-9B1F-3E760675E04D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81994cda4366456b349767bce387616ff8e3c672","datavalue":{"value":"0729.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$404874CE-7B79-4EEF-A6A7-CA027644D1FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cedd26fd077849c988ef8fb659f548e853b46f53","datavalue":{"value":"10.1016/0304-3975(91)90280-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$81C07E1F-8FEE-4A07-8878-433039B9B470","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"860df85bb63cea1c0a54d4f1bac276a25a5ec905","datavalue":{"value":{"entity-type":"item","numeric-id":294771,"id":"Q294771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807021$62D71F0D-55AC-4D44-9444-A6D58DC74867","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":"Q807021$4E2A9FF9-2D48-42CC-9F16-F4E370F5B225","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q807021$14D9CAF4-FE25-4D44-BC6E-EAD3980CE38F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e925cc96d939e8b794feb167927f2a19335b9daf","datavalue":{"value":"Let L be a regular language over an alphabet \\(\\Sigma\\) with partial order ``\\(\\leq ''\\). It is proved that the language of minimal strings in L, with respect to ``\\(\\leq ''\\), is a regular language. The marked finite state machine is introduced which is a finite automaton with one or more marked transitions. The language \\(L_ m(M)\\) accepted by the marked machine M is the set of strings which leads M from its start state to one of the final states by passing at least through one marked transition. It is proved that \\(L_ m(M)\\) is regular for a deterministic or nondeterministic marked finite state-machine. For proving the main theorem: ``\u1e3a\\(=\\{x:\\) x is minimal in \\(L\\}\\) is regular if L is regular'', a marked finite-state machine \\(M''\\) such that \\(L_ m(M'')=L''\\), where \\(L''=\\{y:\\) \\(y>x\\) for some \\(x\\in L\\}\\), is constructed. Then, from \u1e3a\\(=L-L''\\), it follows that \u1e3a is regular if \\(L''\\) is regular.    Some problems concerning with the number of states in the minimum deterministic marked machine are solved. Finally, two open problems are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$9AA92219-24EF-4CB6-B17F-31A0F325856D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$06A0207E-E031-452B-9E73-723EFA9832E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0512371dc1aab2a65a2c06b7a18b2dc3671596b2","datavalue":{"value":"4205993","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$6506F382-25A3-4030-9164-F8883941E1BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a09057b51d241ccab4cd7643a40768f8cad40806","datavalue":{"value":"minimal string problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$B6B0CB89-9756-4936-A4A5-F268BC6D407C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f656e1df2e480b6e02a97564ddebac4bbaba970b","datavalue":{"value":"minimum-state machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$5745E1B0-B2A0-4BA7-90BD-7220B0769390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126bc261b4ce15426bca501a6725c284417e2bf6","datavalue":{"value":"partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$D46096AC-8F5B-4B4F-9708-45BF338C782F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea9b35a533d874f0a32d77e584c8b61e0e7c2fe","datavalue":{"value":"regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$0274A428-507D-46E1-9075-573830E8BB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"654d82cffaf48aee34c8d66a865b227f1d39e13d","datavalue":{"value":"finite state machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q807021$C3D9BAEE-263C-4158-B2E2-C439DF46EF55","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c03730668db67f2f0525cd022cd794bdf73f905","datavalue":{"value":{"entity-type":"item","numeric-id":916649,"id":"Q916649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807021$C319B63F-4AE7-4B93-BCA1-942340332C7E","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":"Q807021$245B2912-6401-47A4-ADFB-B600DC8143B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807021$1CFD744A-801A-498F-A811-1DEF143EA8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807021$D7799EC6-2204-4D2C-8FF1-C50439FA96DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f28db7f96068e5ce3938c306e6d15e9aefa614","datavalue":{"value":{"entity-type":"item","numeric-id":3915990,"id":"Q3915990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807021$0B49AACE-81C9-4B36-88AB-341F24433E6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"32685829f783fe501260b1e360186b854c6627ff","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90280-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q807021$C155C797-CC17-4F3F-8754-8EB42D090533","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7d2dc764accf7d424170c593a64e25009967e71","datavalue":{"value":"W2037957156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$70C515B2-8C35-4CCE-8622-0FADFE9734C9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fe4cd7424a6be7bb1ddb8de81118e80d4b1a801d","datavalue":{"value":"Q127190792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807021$668DFD29-3F67-43B7-9786-2027873C2ADA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6233b644feafb39b0a384ab0fc463018374f565","datavalue":{"value":{"entity-type":"item","numeric-id":688156,"id":"Q688156"},"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":"Q807021$0AC26F48-6ADE-41C4-8464-674B9ACAF3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"749dcce3371fa7fa73b4a94c6beeca37647b219e","datavalue":{"value":{"entity-type":"item","numeric-id":3323299,"id":"Q3323299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d141e94a6c92fffb6978dc88b06acbf62c535ee","datavalue":{"value":{"amount":"+0.8584128618240356","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":"Q807021$F8529D3E-C443-4324-A841-DC7E9995F051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62cb324a2e4de66fa83b3f29941c4ed17c35698c","datavalue":{"value":{"entity-type":"item","numeric-id":1384533,"id":"Q1384533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e742e19a2db53506b3c34fe5e6b1165f472396f9","datavalue":{"value":{"amount":"+0.7232488989830017","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":"Q807021$5156A88F-9D75-4973-B0B9-505EE3C6390D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25d03857bc6c09e268f13b3fd61d47b573b0ca6","datavalue":{"value":{"entity-type":"item","numeric-id":4602380,"id":"Q4602380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4b5d5fddb841be2be802a10f683c67b2554b752","datavalue":{"value":{"amount":"+0.719103991985321","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":"Q807021$CD0C3634-65B7-4B58-A646-E622361597CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5447458d20110e241bb654d2d14ae974124785b","datavalue":{"value":{"entity-type":"item","numeric-id":1606988,"id":"Q1606988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dee4313314b2d4f949be62cea5b45fac4cfe127","datavalue":{"value":{"amount":"+0.7152321338653564","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":"Q807021$9B4C3E31-AEC9-4965-8F91-D5DAE47E5F6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimal strings in a regular language with respect to a partial order on the alphabet","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimal_strings_in_a_regular_language_with_respect_to_a_partial_order_on_the_alphabet"}}}}}