{"entities":{"Q1177178":{"pageid":1187927,"ns":120,"title":"Item:Q1177178","lastrevid":66769047,"modified":"2026-04-12T12:43:42Z","type":"item","id":"Q1177178","labels":{"en":{"language":"en","value":"A graph-based regularity test for deterministic context-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20027"}},"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":"Q1177178$E87D5968-0CF2-43BC-BBA1-9CA4C0E251B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8bfdfb53a07004967fe6bfa52f2b283f006bcf03","datavalue":{"value":{"text":"A graph-based regularity test for deterministic context-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177178$835023F3-A7E5-458F-AEAA-561022B19922","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"747761d9ce4a8b20929f4e7b0168299dcd0580e4","datavalue":{"value":"0753.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177178$EEB5FBAB-DFB1-4226-94D1-5922E2291F83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e4f5ac17f6aeb1970e88af151df4ebd53a559a52","datavalue":{"value":"10.1016/0304-3975(91)90076-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177178$CDE78366-11CF-4653-BA86-3C5C8451809E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d969f9e1a5cacd9ef75f50727d5aa0d66664593","datavalue":{"value":{"entity-type":"item","numeric-id":671524,"id":"Q671524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$85C4042F-5B3B-4D79-9689-307DCAD93A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5900a861e06a95a33d44d096aff135bf1edfd1fe","datavalue":{"value":{"entity-type":"item","numeric-id":1177177,"id":"Q1177177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$F1201B22-34DB-4CBE-A5C3-E4673F34F9E9","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":"Q1177178$0049421B-B5E6-4869-A64A-9BA7067F5EEB","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":"Q1177178$52BB9B64-AD36-410A-AF5A-8C641BE45010","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e30bd5e54f0df56980fefc1eae5a5a5b1b614d35","datavalue":{"value":"It is shown that there exists a test of complexity \\(O((qt)^ 2 t^{qt})\\) for testing the regularity of a deterministic context-free language, where \\(q\\) is the number of states and \\(t\\) is the stack alphabet size of the pushdown automaton derived from an \\(LR(1)\\) grammar for the languages. The previously established upper bound for the test was \\(t^{q^ q}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177178$D4247C9C-5896-4A6A-892C-A2AB7E96C632","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f329847dc59046f25f46c05e506dbf25dd11dab8","datavalue":{"value":{"entity-type":"item","numeric-id":808684,"id":"Q808684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$A2354DC2-3551-4479-9F91-38D2E79AA85E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177178$9135662F-BC53-47A9-B24C-BE92D429F396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177178$F14B03DD-B8C6-4F7F-94F3-F98D3F038F8D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17cd7435a9c15962593bc43ad402b937363bcb64","datavalue":{"value":"20027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177178$2F71AB40-9249-4911-A440-38BD3C32CB3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177178$D3B999C8-86A9-4C71-80A9-317B9C2EAF50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"456c672ca15cab74651e643baa7549046be81ae8","datavalue":{"value":"pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177178$C0B28665-8A54-4938-98C7-7FFDE278F062","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":"Q1177178$549E3925-8C2D-4CF8-AD97-941F7D1FE5F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ea110060cedbbfaa741f84f1becea84054eecaa","datavalue":{"value":{"entity-type":"item","numeric-id":5753522,"id":"Q5753522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$4ECAB362-F8AA-46BC-8BAE-5F92A35FCA93","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":"Q1177178$4E4B5FA8-3908-4EFA-8F8D-427DAAF2087E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"597cab6a01e7e515c86bb670e6c1b95d0011eb31","datavalue":{"value":{"entity-type":"item","numeric-id":5537615,"id":"Q5537615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$1945FDA5-7012-4F9D-87CF-11BECFCC4FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b6e6ab585a855fab7a27153f29da3cfb8f1e7c9","datavalue":{"value":{"entity-type":"item","numeric-id":4045649,"id":"Q4045649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177178$5BF1C7DD-210E-4DE7-B017-94B3992A6649","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1bab57a16badfe8b5ef723f46cbd0bb8b45456","datavalue":{"value":{"entity-type":"item","numeric-id":1892201,"id":"Q1892201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c395aef56f346455da5fd0a78bb92591744cc782","datavalue":{"value":{"amount":"+0.7910188436508179","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":"Q1177178$083CEE47-D193-43B8-B908-6B18B93B527C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f252a39b7775b11274fe52b9c18237fd561735d6","datavalue":{"value":{"entity-type":"item","numeric-id":5204306,"id":"Q5204306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d191631f0261ea38a08a816d8ee5814c7846015","datavalue":{"value":{"amount":"+0.7864599227905273","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":"Q1177178$249028B7-46A4-435D-90D2-FA58D423A81E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05bcf2fff7900cd0e47ab6e1b06d536f78d4aebf","datavalue":{"value":{"entity-type":"item","numeric-id":685373,"id":"Q685373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff7db39093bbdbaf60aa0e29e75192557417618","datavalue":{"value":{"amount":"+0.781216025352478","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":"Q1177178$EB213CDF-74C6-4B3D-A5EF-A01596E417C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A graph-based regularity test for deterministic context-free languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_graph-based_regularity_test_for_deterministic_context-free_languages"}}}}}