{"entities":{"Q1060563":{"pageid":1071315,"ns":120,"title":"Item:Q1060563","lastrevid":69537084,"modified":"2026-04-13T07:40:36Z","type":"item","id":"Q1060563","labels":{"en":{"language":"en","value":"Some results on subclass containment problems for special classes of dpda's related to nonsingular machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3907804"}},"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":"Q1060563$07669BB3-7A8D-4F2B-BD9F-99D89476E3B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c01646a6b8ceb2d541b2ea2cffc2078b31afc55","datavalue":{"value":{"text":"Some results on subclass containment problems for special classes of dpda's related to nonsingular machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060563$A005EBF7-08FF-41CB-AB0E-B66628B73858","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f1aa4811fb915489ea23b129194f1910751e8c2","datavalue":{"value":"0568.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$83B610A5-B660-4741-A0C5-B92D169AFAD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"20ea681e053d0bd682d6d7d7bee58659abd5a7a8","datavalue":{"value":"10.1016/0304-3975(84)90039-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$13C8ACB2-0B1A-4436-8D0D-B00658C68FC9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b75e3dc8ae1008724e44cf427d976ff916bfae1a","datavalue":{"value":{"entity-type":"item","numeric-id":799386,"id":"Q799386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$A9DB2EDE-FD25-4B8E-812D-3F2E86821430","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":"Q1060563$B74453D2-C5A5-47F5-9421-E3B7EBEB46C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q1060563$66FC2FF8-FE80-495C-B184-CC29A697DF98","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"248d9ecea7adf6b9425fd23aa12de4b13d74729e","datavalue":{"value":"The results of this paper are concerned with the equivalence problem and the subclass containment problem for deterministic pushdown automata (dpda). The class of weakly nonsingular dpda's which includes the class of nonsingular dpda's is defined. It is shown that it is undecidable whether a dpda is weakly nonsingular and whether a dpda accepts a weakly nonsingular language. As a corollary, the negative solution of the problem to decide whether a dpda is nonsingular is given. Next, the class of super-nonsingular dpda is introduced, a subclass of weakly nonsingular dpda's, and it is shown that it is decidable whether a dpda is super- nonsingular and whether a dpda accepts a super-nonsingular language. Finally is is observed that the (open) problem of deciding whether a dpda accepts an LL(k) language reduces to the problem of deciding whether a super-nonsingular dpda accepts an LL(k) language.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060563$406F83E6-3EFA-4268-851F-D1C860096BD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$99DBD431-7503-4FEA-B40A-BD2EC36C76F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$CEFC7984-5D36-4551-A55E-16C6DCDD26B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$347B83FF-875D-46C2-B8CB-19FF32DB5ABB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8da185d407c4d7beaa56e614827f809acff8b971","datavalue":{"value":"3907804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$2C4C1F17-CCA0-4087-8609-EB6560F4F4B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25e7602aba7c4f1dd1bc70590e121bd6fea71e8f","datavalue":{"value":"context free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060563$6E4BBEC2-4A93-48C2-997B-E10097637726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bf0a69ff86a1d56569a9610bc144fdfce86ab79","datavalue":{"value":"equivalence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060563$8E61F5F7-F628-446C-9D0E-44C3C11B8D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d868b454618c55ed01d5823e2fa6ebe9fbe2f5bc","datavalue":{"value":"deterministic pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060563$3E9FB371-3EAD-43A1-BAD2-D7DE5D62691B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"741dfa27f0aefbaba5557fd13dcb2e3fcc839c04","datavalue":{"value":"LL(k) language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060563$9CC8CB75-60C4-48D2-85AF-D037DAC008C1","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":"Q1060563$CEF0A058-CD66-4566-B3EB-E1D7B341BDD8","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":"Q1060563$FC9937C2-2D47-4CC8-A1D4-D40D89F70566","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a54774e0e63cd7d0fd209c6303658e95d4ce948","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90039-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1060563$73E85A80-E5B9-4334-98ED-92D764547DC8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b2df469a36dda2407d74a5994847c13263646826","datavalue":{"value":"W2090865410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060563$520E72F5-6D4A-4156-9503-3663724730A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfc94892434143ca76461e4c7d3f378a2a29e97f","datavalue":{"value":{"entity-type":"item","numeric-id":4141220,"id":"Q4141220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$E4DDB485-14B0-4B44-B827-8330BD4FF3BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2acbd1d334be1160848aed690fa9b51cad64ef0","datavalue":{"value":{"entity-type":"item","numeric-id":1252037,"id":"Q1252037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$01240B56-F9F6-47DE-9A47-08DC72A3413B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de35764df1385515e897afb65a533a0d4d563fb","datavalue":{"value":{"entity-type":"item","numeric-id":1251906,"id":"Q1251906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$9F2AEC89-8761-4441-94C0-AFE8D7FF32E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0711f0bf590c2207dac6faa5788ef613584cd7d","datavalue":{"value":{"entity-type":"item","numeric-id":1132642,"id":"Q1132642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$7B92F3C5-0E27-459A-9133-A3620CFCC1E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b76e065585c6fa2e8fb50190ce6a06cebcc9bc8","datavalue":{"value":{"entity-type":"item","numeric-id":3048299,"id":"Q3048299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$90DB1CA4-5BE1-48AB-9AC7-40952ACDBE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bff8b19dadebd5e3dfb4db8cb0e80dde8d233cf7","datavalue":{"value":{"entity-type":"item","numeric-id":5684249,"id":"Q5684249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$04CEDDD6-BF6E-466C-838E-E774CE6666AA","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":"Q1060563$C7F72CE2-194B-4557-9AF0-713117917411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422f13e0987f12a34d425454745bbbb66a566dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4072875,"id":"Q4072875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$A8179884-82FE-477E-961B-5F00308CFFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d123ce3c6592eaecceee504819584bb2976aea7","datavalue":{"value":{"entity-type":"item","numeric-id":3888532,"id":"Q3888532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$80D7FEEF-16E8-4662-AAFF-C2BD485C25E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7c303ddbf6a6d3cdfdfc57aa889b80b87656bfb","datavalue":{"value":{"entity-type":"item","numeric-id":3886866,"id":"Q3886866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$743B1079-A564-4AAC-9F1E-CE83E05C4EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2cabff82ef2f18b4b91c8578a0d81ca520f2e9a","datavalue":{"value":{"entity-type":"item","numeric-id":3949982,"id":"Q3949982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$469C7AA6-3463-4F79-BACD-44ACD25CADA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62b799f25bc9c2c738602afdd0aabb341d0d41f4","datavalue":{"value":{"entity-type":"item","numeric-id":3908478,"id":"Q3908478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$2E8F7D58-754C-41D8-AC8B-84D9B4C33ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f655404f5019528c0ff6f0cb07a94b157182d6db","datavalue":{"value":{"entity-type":"item","numeric-id":1158757,"id":"Q1158757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$83239757-F8EC-475F-B7B3-DF5E98879D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b9d693ee9f84d5128fc7c86fda922f6bfcc20f5","datavalue":{"value":{"entity-type":"item","numeric-id":5609393,"id":"Q5609393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$2ED904A9-31F1-4317-A9E9-7451F641CF0B","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":"Q1060563$7BAB6612-29A8-49CB-B6AF-7EEAA0BF2478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61cb8280fa36fe466f451510204017197a7e8db6","datavalue":{"value":{"entity-type":"item","numeric-id":1230509,"id":"Q1230509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$C350F1AC-DAB8-4B6D-9497-9577471BD040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef3dea0e266f78319fee7cbf7f7f4b7c1769f54","datavalue":{"value":{"entity-type":"item","numeric-id":3682403,"id":"Q3682403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$0E0A56EE-0AD4-4157-9EE7-4B9BF7C83681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6c9ad1af6635d001f4350001772960e0e5560f","datavalue":{"value":{"entity-type":"item","numeric-id":4772713,"id":"Q4772713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$B931DFE7-DA28-4200-9877-A2A9B7829AEB","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":"Q1060563$6AC8B4F5-B8B5-4A24-B4A1-B53648341C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e0b8f61d70bb48c00c21d61a4a73263d682547e","datavalue":{"value":{"entity-type":"item","numeric-id":1152220,"id":"Q1152220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$19DBF6E8-EED6-4C3A-BE07-395E17B7B4FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2dd8b739cacaef27ebd748b3d0d83c5cbbc73a","datavalue":{"value":{"entity-type":"item","numeric-id":3327736,"id":"Q3327736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060563$8E34636B-639F-4397-ABD7-A9AEE6D8FD39","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1a176c20071b83164a332342eeb3d707e38af65","datavalue":{"value":{"entity-type":"item","numeric-id":799387,"id":"Q799387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"048d2a6a6567904e6ce9a569319f089dbe95ff55","datavalue":{"value":{"amount":"+0.908470332622528","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":"Q1060563$9933A72C-25E0-4118-B907-BED9C144E04D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6142c7a56d701342d7fe761ce534d32ce8275fcb","datavalue":{"value":{"entity-type":"item","numeric-id":1062450,"id":"Q1062450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"887000bcb0f1069d278ea141172ac1233cdf996d","datavalue":{"value":{"amount":"+0.8070231676101685","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":"Q1060563$8256118D-9B1E-46B8-82DD-EEEFF9CA1AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7214d015b169f2b2aa6efcb057b8e5600478033d","datavalue":{"value":{"entity-type":"item","numeric-id":3326867,"id":"Q3326867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"724424122c9b228e45e9b27dcecf34093492ddcb","datavalue":{"value":{"amount":"+0.7983452677726746","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":"Q1060563$D8B91C7A-79A3-48F7-B290-38C35C2F0AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47acd2c4ea5f82beaedb5e1e409a0818067d8758","datavalue":{"value":{"entity-type":"item","numeric-id":5327495,"id":"Q5327495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74e4d2f63e915771553c5b4cf27efe930873b877","datavalue":{"value":{"amount":"+0.7829713225364685","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":"Q1060563$83C3BECF-E41B-4A05-A5B8-038A1BCA4792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f93994764c5550e37a603465d2e209a11d145bf","datavalue":{"value":{"entity-type":"item","numeric-id":1894681,"id":"Q1894681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0738b7885e215088c2ecc688066de35bbc2dba7a","datavalue":{"value":{"amount":"+0.782737672328949","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":"Q1060563$EEC7CF5B-0186-4CCE-BDA9-EABB89DAE808","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some results on subclass containment problems for special classes of dpda's related to nonsingular machines","badges":[]}}}}}