{"entities":{"Q1177168":{"pageid":1187917,"ns":120,"title":"Item:Q1177168","lastrevid":66768975,"modified":"2026-04-12T12:43:40Z","type":"item","id":"Q1177168","labels":{"en":{"language":"en","value":"On the degree of ambiguity of finite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20020"}},"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":"Q1177168$B7E098A7-2491-47E3-937A-259BAFE89F84","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6938482769f42b5c6afd426514214025ccf9951b","datavalue":{"value":{"text":"On the degree of ambiguity of finite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177168$362E5B21-3AF1-474A-A2B0-670EAC9F56E1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ceb7b9882842f2a50d7211363a11ea8e886c9884","datavalue":{"value":"0738.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$5BB84365-4102-4F6D-A95D-18D109A93DF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e92f5cddd6ee0d07a8fa4486080786ac181c925","datavalue":{"value":"10.1016/0304-3975(91)90381-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$D1C945B2-A9A7-47CA-8B86-35CB9AA9CD83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1777c159e4686d0f998427e5f6868fda745c904","datavalue":{"value":{"entity-type":"item","numeric-id":1177167,"id":"Q1177167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$69E2B796-9D92-4909-9378-B67A71B10187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d8846866e0f2e2874e781dfcefe3a000615efed","datavalue":{"value":{"entity-type":"item","numeric-id":435967,"id":"Q435967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$4CB47842-304C-49D2-A10E-09F08368F3D7","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":"Q1177168$4166E026-35BE-40DA-8C81-EB4496A44D94","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177168$D2A959E3-40ED-43BB-9C72-19FCA7D40E52","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b165eba30e444201b70b6c7fddb528a23ed23b5","datavalue":{"value":"Nondeterministic finite automata are subject of the paper. The degree of ambiguity for a nondeterministic automaton is defined as the supremum of the number of paths for the accepting input words. The main established results are: the degree of ambiguity of a finite nondeterministic automaton with \\(n\\) states is \\(5^{n/2}\\cdot n^ n\\); there exists a polynomial time criterion, characterizing automata. Polynomial time algorithms are proposed for computing the degree of growth (polynomial or exponential) of the ambiguity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177168$497320D3-E518-47D9-8795-F3DFA2DCC051","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cc5f7effc0f7b49385411bb7354d3da876c65ec","datavalue":{"value":{"entity-type":"item","numeric-id":1160486,"id":"Q1160486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$0E5052A7-F7A1-4EB4-A045-B4093A11AAAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$243EA0A2-EF38-4EEA-A72A-BF5ABF6ADCC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$FADAC486-7595-4219-82DE-AF7574F3D896","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8867e655d26a6e0c05fb5614dccce430005ab00a","datavalue":{"value":"20020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$BFF1E231-0031-4682-8393-9EAB70DCBD25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b48541c376a4f691e3a9309535760ea215d320d","datavalue":{"value":"behaviour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177168$506187C8-5C45-4D20-A7A9-BDC3F489D382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6abde220793268065a5dcbf29c614de31957d669","datavalue":{"value":"nondeterministic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177168$5C0F51B4-E389-4AA6-ABF9-4454324806E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8f035db257ec07867c74420573d647440e7e0c6","datavalue":{"value":"degree of ambiguity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177168$763E6B89-C53E-4C68-904F-12FF4D6B4BAD","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":"Q1177168$74D182A1-4DC2-4234-AA35-4F69592E6058","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$CC2CE325-84CB-4510-8D97-996AD5853145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f37cd6fe26dc3b82b0412bfebbe2e5c864edfb6","datavalue":{"value":{"entity-type":"item","numeric-id":1173410,"id":"Q1173410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$82B8E0EE-FE8B-4630-8E45-BBC0A6C2EF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$E5EBBD47-34D0-484C-A512-25CE5924206E","rank":"normal"},{"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":"Q1177168$91B501A7-E944-4583-A2DD-C56C0186EE30","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":"Q1177168$DE47B9C1-C7C2-409A-A023-029FD2FA7F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2631bdda72c0ec46e1523c6d35212267852671e","datavalue":{"value":{"entity-type":"item","numeric-id":3742754,"id":"Q3742754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$7C891919-D0D3-4331-9B5E-2EE4425F0474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69c79a2b2ef68f73f3af959896fa005d1d15c8ae","datavalue":{"value":{"entity-type":"item","numeric-id":3034835,"id":"Q3034835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$1AA54021-8700-48CD-9658-1CCCFD803042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b53547ba51b48effbf737f5edd59ffedad491a4","datavalue":{"value":{"entity-type":"item","numeric-id":1250142,"id":"Q1250142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$BE328079-328E-4855-88BE-3D013CD3C02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ea2e682b9c0dabf93e8bde92af2ec08d19a46be","datavalue":{"value":{"entity-type":"item","numeric-id":1134517,"id":"Q1134517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$71A64CCA-83FF-4056-BA20-AA864E79A519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96b9c9b10114190fdbd6c0337999a73e994a12e0","datavalue":{"value":{"entity-type":"item","numeric-id":5661809,"id":"Q5661809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$045EB9D0-9378-4BAC-9A77-5B1F3CEC00A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"037ad6c15518b7abe43b31e5bf65804e8d270cf7","datavalue":{"value":{"entity-type":"item","numeric-id":1243001,"id":"Q1243001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$ABB4FCE3-96F1-48B8-9226-CD3B36E18104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3e9c24fe22bdca74ebb07d689f0938437d89e25","datavalue":{"value":{"entity-type":"item","numeric-id":1215588,"id":"Q1215588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$914FABB8-403A-42A1-AA7B-C52283FDA58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d3b9e332dcc324492fbcea8e6109cb2f093bb9","datavalue":{"value":{"entity-type":"item","numeric-id":4160409,"id":"Q4160409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$5BD2EB5E-3A4F-4B2A-82C2-8BFC6052A1AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"deab30a9ec9482bc798e367d141440da99ae8123","datavalue":{"value":{"entity-type":"item","numeric-id":4168669,"id":"Q4168669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$9F48765F-A559-4929-BB12-467C8D811B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"068ff9bc22782d1999dd390113545d9fb239fc9c","datavalue":{"value":{"entity-type":"item","numeric-id":3477969,"id":"Q3477969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$71315C50-72B6-4AD1-94F3-F1081C15C6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0be4dd2ae12a720ae36eac84d798bf58f9d5aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1825038,"id":"Q1825038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$09BEDAA8-E1C9-4546-A522-60FC199415AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caa22c2a09da29028b32fbdec6997075843df5fa","datavalue":{"value":{"entity-type":"item","numeric-id":3698326,"id":"Q3698326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$D1D1BE91-0EAF-4CA7-ADE2-EFD77E9208B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b14874328e06322f55427a98ad1a9767d46fe80","datavalue":{"value":{"entity-type":"item","numeric-id":1120286,"id":"Q1120286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$3AB4E59C-31F7-4323-9EAE-D46F7CEB5839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01204e6a1d34c4bbcbc1a4c4cc2179591b5b21dc","datavalue":{"value":{"entity-type":"item","numeric-id":4727438,"id":"Q4727438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$3D218454-4C2F-4F8B-8706-677BA403FDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee8ff2d134ebb9b034364fa7a86d42c2c199aab3","datavalue":{"value":{"entity-type":"item","numeric-id":5752758,"id":"Q5752758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$D005BAA2-8A3E-4F2E-AB35-4FA3375000C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3257bf07d73d014d3ab2d14e8062a973d63ae121","datavalue":{"value":{"entity-type":"item","numeric-id":4154498,"id":"Q4154498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177168$7430CF53-75B2-4884-A5D9-5C8F51AD46D0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9b9cb72b27dc869f8e946a44c16cd8859813ff2b","datavalue":{"value":"Q126376694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177168$10DB3D8D-2123-474D-8F89-BD73478C6060","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e16842ea26054f1b8322c70685f565dab04eb03","datavalue":{"value":{"entity-type":"item","numeric-id":4727438,"id":"Q4727438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab803f348724a1644ed638622486ebfd4f01ccfc","datavalue":{"value":{"amount":"+0.9328646659851074","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":"Q1177168$79B41442-8D23-491A-8808-8D6CC225DBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd5934c8763641a35af6514138d183d362e5b8bb","datavalue":{"value":{"entity-type":"item","numeric-id":5350151,"id":"Q5350151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"559edbf2af3de3360b0ab49b61660b9fa6e10f55","datavalue":{"value":{"amount":"+0.9013357162475586","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":"Q1177168$64DD7AD6-4AD9-4B6F-9119-45574880CB36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51e72c7edcc30df95f747a5198b2dc749f809b07","datavalue":{"value":{"entity-type":"item","numeric-id":1825038,"id":"Q1825038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2407810452877e3988ba21a2eb8a42ba8c5a3a4d","datavalue":{"value":{"amount":"+0.8772989511489868","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":"Q1177168$D1EE6DD1-D871-4C0E-B8F0-5BDAC037F395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"028f2143f73c4f97ba35bdce7414daef40b99925","datavalue":{"value":{"entity-type":"item","numeric-id":1198953,"id":"Q1198953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1141c5a6d7d87dab783f1ad17ff9c72632fc584c","datavalue":{"value":{"amount":"+0.8764943480491638","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":"Q1177168$C9DDB769-2889-475E-AC6D-C692631EEE21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e0a25b7bd9a6bd1f148d21100e1a01d416ddeac","datavalue":{"value":{"entity-type":"item","numeric-id":3974881,"id":"Q3974881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d9be137539a9ddb60be3537d00098a4b0542d6b","datavalue":{"value":{"amount":"+0.8596894145011902","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":"Q1177168$0CB31E6D-44BF-466E-BFCF-A50319C33CD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the degree of ambiguity of finite automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_degree_of_ambiguity_of_finite_automata"}}}}}