{"entities":{"Q799387":{"pageid":801235,"ns":120,"title":"Item:Q799387","lastrevid":42700166,"modified":"2025-07-08T14:59:11Z","type":"item","id":"Q799387","labels":{"en":{"language":"en","value":"Some remarks on subclass containment problems for several classes of dpda's"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874647"}},"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":"Q799387$759C9CC4-2054-420F-97BD-67CD4B9526EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ddeec850bf3ee9516afb62eddaccb123832bcec","datavalue":{"value":{"text":"Some remarks on subclass containment problems for several classes of dpda's","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799387$FECF14B0-9AB4-40C8-95FC-C6DE334A56A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b0fff3b82e37567df276f76be4ff52b11c019aa","datavalue":{"value":"0548.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$782AEFA9-5041-46E7-9355-315EDA437CC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d4d6293e68a5c34b91b1267364d7a548b4a61c0","datavalue":{"value":"10.1016/0020-0190(84)90120-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$1512499E-4D24-4C26-8337-BFD3623D43A7","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":"Q799387$61F9239A-DDE1-4ED2-B57E-29C482D8B2F6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799387$7E7D1EE6-FCF2-493F-943D-96F512AB0CC5","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":"Q799387$440AC70F-8529-471D-A470-77392896EB6A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6d16990ff6ab0db1af1a6d4d92ae18ee4c40b61","datavalue":{"value":"The containment problem relative to a subclass \\({\\mathcal C}\\) of deterministic pushdown automata (dpda's), written as containment(dpda,\\({\\mathcal C})\\), is the problem of deciding for a dpda M whether there exists a machine in the class \\({\\mathcal C}\\) accepting the same language as M. This paper shows that containment(dpda,\\({\\mathcal C})\\) is undecidable for any class \\({\\mathcal C}\\in\\{{\\mathfrak N}_ 0,{\\mathfrak P},{\\mathfrak NM},{\\mathfrak NQ},{\\mathfrak NSD}\\}\\) where \\({\\mathfrak N}_ 0\\), \\({\\mathfrak P}\\), \\({\\mathfrak NM}\\), \\({\\mathfrak NQ}\\) and \\({\\mathfrak NSD}\\) are respectively the classes of nonsingular dpda's, proper dpda's, dpda's with necessary modes, dpda's with only necessary quintets and dpda's with necessary stacking derivation. The machine containment problem for \\({\\mathcal C}\\in\\{{\\mathfrak P},{\\mathfrak NM},{\\mathfrak NQ},{\\mathfrak NSD}\\}\\), i.e., whether or not a dpda belongs to \\({\\mathcal C}\\), is also shown to be undecidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799387$08261D36-D77A-4A64-BFCC-704A0F8DC38E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$8BEDC70F-B39C-4517-AE4F-1813F1AD743E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$188CFDED-CDB7-4940-BAC8-7D18C939AEAB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"87d7fbcf19e7830e58d1d1bc5c6490a2454f37fa","datavalue":{"value":"3874647","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$D6BA7362-8459-4005-B96C-F5701152EEE9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78324486961df960ef646ca2bbf8b39bcdcdc7ed","datavalue":{"value":"subclass containment","type":"string"},"datatype":"string"},"type":"statement","id":"Q799387$2FD70E0A-C44F-4328-BDB7-A7E182271F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d868b454618c55ed01d5823e2fa6ebe9fbe2f5bc","datavalue":{"value":"deterministic pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q799387$EFDF7F83-B199-4080-B022-07D68E47234C","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":"Q799387$D735E404-68A6-49DE-A0C1-88F39C6398C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0fcdea1dfef6f96d0919077e6d94c234ce181777","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90120-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q799387$53AC68C3-2AFD-4605-934C-AD982AF7F36F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"189b8bc844f3809b33b8655d78237ee20aa73496","datavalue":{"value":"W2093170711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799387$64E6B619-19E5-423A-A714-561C1F7FB48B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e63fd747508b23b55d1d45b8a132082cc1d0cc3","datavalue":{"value":{"entity-type":"item","numeric-id":1058306,"id":"Q1058306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799387$BC33220C-9DB9-484C-92A2-88972F602699","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":"Q799387$F79DE481-4682-4944-851A-B4593B60796B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e8a90a94b7251cf8196ef59ec10eed758eca6c4","datavalue":{"value":{"entity-type":"item","numeric-id":799385,"id":"Q799385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799387$A7BF2C39-01A2-400C-BA47-8996D149D991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c6d9879d3b7d98710e798a54af0143d352f7e27","datavalue":{"value":{"entity-type":"item","numeric-id":1060563,"id":"Q1060563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799387$2DDC9216-A388-49D7-A78B-7500D7B397C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88bf75d5fa4365193506074c05cd6ee2b649a0d9","datavalue":{"value":{"entity-type":"item","numeric-id":3951577,"id":"Q3951577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799387$1AED1473-8B35-4DAB-8A7B-7B511C85BE08","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83472b24202296424ee393ebe4c7e2e7b989496c","datavalue":{"value":{"entity-type":"item","numeric-id":1060563,"id":"Q1060563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6af700d56f84fb0a1af50268536af05cf8a14dbd","datavalue":{"value":{"amount":"+0.9356835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$A9B92ECC-82BF-4CC8-A3E2-700AC6F132C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc3f074d90a1550a9aaf55e0f454efbc45318b12","datavalue":{"value":{"entity-type":"item","numeric-id":3540139,"id":"Q3540139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d0ec6f0363112c682f0395cb5c286844b4b489b","datavalue":{"value":{"amount":"+0.8631629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$B4A3E614-DA57-450A-BAE4-CC2FE1048BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eafa4edc646cb4df647e99df811f9a8ad8f7f70d","datavalue":{"value":{"entity-type":"item","numeric-id":5206684,"id":"Q5206684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7e3f2cc3f1d005bee4b14a71814f157bdcc3fe","datavalue":{"value":{"amount":"+0.8397971","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$6C321804-7850-43B9-A3F3-400916197303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81ef32d9ec08165ee9ffbc529bed0fc3bf01b85b","datavalue":{"value":{"entity-type":"item","numeric-id":1040379,"id":"Q1040379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe1a8328905adac4cc71226b687afbbf65a4e8de","datavalue":{"value":{"amount":"+0.8260089","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$E5ADE72F-695A-4FF4-AB23-B22BFAB3DCF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8a617aaf7ed4596b6f5018c727531b146cb7a2e","datavalue":{"value":{"entity-type":"item","numeric-id":1115858,"id":"Q1115858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d6875f96352db801eb4061312bf511e681c5a90","datavalue":{"value":{"amount":"+0.81754166","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$68C2C99C-2EF4-4D0A-BEAE-91CFC6A6AB1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7474deaf010284a6123f19247aeda7fdc6a5ede","datavalue":{"value":{"entity-type":"item","numeric-id":4529994,"id":"Q4529994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fc823591160b10829a41d6f8b94a05097458b34","datavalue":{"value":{"amount":"+0.8141761","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$6EB79E32-EF62-40D7-9F3B-DBBD42B3DBA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d91df6876d18efe8160d4b788d4be02a841cfc6","datavalue":{"value":{"entity-type":"item","numeric-id":1275620,"id":"Q1275620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"000ff925deaffbef8f84743c09d1cda8c75b2dfe","datavalue":{"value":{"amount":"+0.81177557","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$2BC808DA-CCBC-432D-A10B-164B66A81FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d55cc9bbf51b480bd72eafb5c091773bf183c60","datavalue":{"value":{"entity-type":"item","numeric-id":1064779,"id":"Q1064779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a16bc6f47e5f9220785fbbd69c477d89afb8c304","datavalue":{"value":{"amount":"+0.81165445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$74328DEB-5218-4E89-94D3-C907488CA57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e5a3b772940a8ecfa89872bb9d4e7e8b18a3d5","datavalue":{"value":{"entity-type":"item","numeric-id":2093572,"id":"Q2093572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65fe0502d2c6f6eb0a98a701af92207d197082dd","datavalue":{"value":{"amount":"+0.8113957","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$FC26DD58-6764-440F-AFD3-B8AFE58D4708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0304ee7858804ebe0efd8bde2f5946494538e6d0","datavalue":{"value":{"entity-type":"item","numeric-id":2285669,"id":"Q2285669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e529240bad413feec67186fe00c9223380512432","datavalue":{"value":{"amount":"+0.810654","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799387$001C737C-66A9-4F3D-B996-903E9F0CE25F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:799387","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:799387"}}}}}