{"entities":{"Q1123639":{"pageid":1134388,"ns":120,"title":"Item:Q1123639","lastrevid":67051485,"modified":"2026-04-12T14:36:28Z","type":"item","id":"Q1123639","labels":{"en":{"language":"en","value":"On the intersection of stacks and queues"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110152"}},"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":"Q1123639$917D3970-1D73-4092-8619-21AF7A20AA66","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c2e2cebe8bb84baf4d3449c02b3b3825ad0095ba","datavalue":{"value":{"text":"On the intersection of stacks and queues","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123639$302EC361-AF0B-4477-BB86-B36F1C8133C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"38ad20f26bf4c24cfe1c3f3533c27c91eeb50607","datavalue":{"value":"0677.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123639$C02CF36B-AF38-4B5F-B801-7EDE5198CD00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ecc5c7e4f5718cbf629bfe7bffeb000c35dd33c6","datavalue":{"value":"10.1016/0304-3975(88)90019-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123639$45087B0C-DAA6-4DC0-9160-1E0465CC5BD3","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":"Q1123639$9D58D892-540D-4F7F-8BBE-BB9758E2786A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1123639$B4870469-64DA-4130-AB2F-5DF5C5BC4E7D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f96f1b0479f014c5c8c166be6a82f918c7bc8ed","datavalue":{"value":"The author establishes numerous strict inclusions and incomparabilities between the families of one-reversal one-counter, restricted one-counter, one-counter, linear context-free, single-reset, context-free, and queue languages, and various intersections of them. In fact, fourteen families are involved in a lattice presented in the paper. We mention some of the results. By a clever choice of bounded languages it is shown that (1) \\({\\mathcal M}(PAL)\\cap {\\mathcal M}(COPY)\\) contains a language not in \\({\\mathcal M}(C)\\) where \\(C=(D_ 1c)^*\\); (2) \\({\\mathcal M}(PAL)\\cap {\\mathcal M}(D_ 1)\\) contains a language not in \\({\\mathcal M}(COPY)\\); (3) \\({\\mathcal M}(COPY)\\cap {\\mathcal M}(D_ 1)\\) contains a language not in \\({\\mathcal M}(PAL)\\); (4) \\({\\mathcal M}(S)\\) is strictly included in \\({\\mathcal M}(PAL)\\cap {\\mathcal M}(COPY)\\cap {\\mathcal M}(D_ 1)\\) where S consists of all words \\(a^ nb^ n\\). These results disprove conjectures presented by several authors about ten years ago.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$74746E39-C101-4C15-BC44-F3DE26D5C564","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123639$5D6ABE86-87D4-4072-8D1D-6497C1C03B4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d29d3142bfbc63a8a7a7fc7a125ebe84951592c2","datavalue":{"value":"4110152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123639$C8AC558F-8013-4058-B325-C445BEA21B7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"554b0900e884a95eac3b2b57073a827a6b3cd976","datavalue":{"value":"stack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$53300484-BF22-4CA5-A1EA-C4B5DDFE06C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25b1e70ae1fc70c62ecf8fa1ba16f6ba46bb9905","datavalue":{"value":"pushdown","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$1F707B57-055F-46D5-9603-365ACBC88F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a4c0b995eef7d1ec64bd1ff7fb3cee9f2b107b7","datavalue":{"value":"reset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$9EBD44E3-0B71-40D1-A062-9F15986CD9BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"590e678624bd4a875c1547343a5ffff1fcf2a1af","datavalue":{"value":"counter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$3C14CA6E-BD03-44EF-AA14-124B9947B869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d5a9e445983e65fa6e5ae8fb7de4044656bacd6","datavalue":{"value":"queue","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123639$83AFF9B4-1355-43EE-8F10-E50EB8728D76","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9b0f3e78bd23cae26c2cac0c14ee4587d20b190","datavalue":{"value":{"entity-type":"item","numeric-id":1838046,"id":"Q1838046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$2B70922E-BB8F-45D0-A2D0-9494BBBFA13D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b5825a72a857aefa8d65d6208cfbd36a98a782ee","datavalue":{"value":{"entity-type":"item","numeric-id":1163381,"id":"Q1163381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$34629891-47C2-4360-B1BE-C744B2D6F666","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":"Q1123639$0F45FAFC-7A3C-4CB9-AB1E-0A2B785F4DAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3fcb5751d2aa8323b02a0e4793a8f054e789fa4","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90019-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123639$FCEC7DB0-F72F-4BB8-B625-48C486CD4B6D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f2fe5c530e6ad015d3a07fe20cecc17fbfa3dfd8","datavalue":{"value":"W2059530928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123639$A6033D4E-ACF9-4AFF-BB01-1F00E9D7226F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f65b22160b54fc37d215a7690dbf6edf0b91db0b","datavalue":{"value":{"entity-type":"item","numeric-id":3873564,"id":"Q3873564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$597F7B31-1D9A-4FBC-8825-86F929677C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$0A7D17A1-7368-48BA-91A4-D867B791BCA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fc91a45dff56ce39a1a654386d46b5649a51921","datavalue":{"value":{"entity-type":"item","numeric-id":1136756,"id":"Q1136756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$982AD798-BEF0-433A-B70A-27108C1A0476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf81563187fd14f5b95daea36ad75a4f09c36ca9","datavalue":{"value":{"entity-type":"item","numeric-id":1148696,"id":"Q1148696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$AC9303B7-154A-4251-BCA4-6B02848B65BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce94a5f2163dd8371d322d54816f5f12860990f2","datavalue":{"value":{"entity-type":"item","numeric-id":3878760,"id":"Q3878760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$0E9A4E17-99D9-4414-9A81-007A10F7D9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a802a7b69f9db192f37ce57903d50ff7b4e60c54","datavalue":{"value":{"entity-type":"item","numeric-id":3912052,"id":"Q3912052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$F0B5B824-64EA-45A9-AC2C-445CF049BDCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"267a31a94e357db27aabd21979c8daabe0e2763f","datavalue":{"value":{"entity-type":"item","numeric-id":3730030,"id":"Q3730030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$EEC703E7-F384-4EFD-9887-BDFEE3C5971C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ac23ff0d4cd9001f838ae713deecaccdfe50ad","datavalue":{"value":{"entity-type":"item","numeric-id":4089754,"id":"Q4089754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$DEF01ABF-2FCE-40E5-BFED-2B683005E8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82635749d3c8d3788e4ac41d88df81b003953d38","datavalue":{"value":{"entity-type":"item","numeric-id":3883536,"id":"Q3883536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$09002882-A80E-4E05-A687-5B6EA117E280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6102aaf887f48a098c23ffa8d3821703596f0b8d","datavalue":{"value":{"entity-type":"item","numeric-id":3709914,"id":"Q3709914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$F31DDA6E-8D8C-4A6C-90ED-0EED780689AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca7dd55bba48d3c2587fba9ee9df9462af6cc768","datavalue":{"value":{"entity-type":"item","numeric-id":598819,"id":"Q598819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$A9562EA4-8174-4A6E-A7E8-D37335E6C667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0a2aa95a334404e19236b501d00c62faa5e3dbf","datavalue":{"value":{"entity-type":"item","numeric-id":2546302,"id":"Q2546302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$6F685036-A658-4F39-BB48-9949E3A0C199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bf9a2e825d64cf3e383698bdb734ae1efb34ab5","datavalue":{"value":{"entity-type":"item","numeric-id":1139945,"id":"Q1139945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$A0368666-0096-4253-AF66-40694C65D4A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca83d6f05996b87c5c4320f8e440ae1bb1e02698","datavalue":{"value":{"entity-type":"item","numeric-id":1094883,"id":"Q1094883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123639$F8A0DCFD-3697-4536-895F-A7197EDF978C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53f1a5037ab52b787cd1296c27e083cfc12aac69","datavalue":{"value":{"entity-type":"item","numeric-id":3730030,"id":"Q3730030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e525c6d208dd538ae4b660ceb6d205ca0d1a004e","datavalue":{"value":{"amount":"+0.8856493830680847","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":"Q1123639$3C1A4028-2754-4864-90BD-19235F99BD97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79545e5e66cde05d04761d58468da79428378edc","datavalue":{"value":{"entity-type":"item","numeric-id":1094883,"id":"Q1094883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a96681d25f4b9fa5b0475baa854f1ce191d533a3","datavalue":{"value":{"amount":"+0.830855667591095","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":"Q1123639$76F29BC9-21CD-4A5F-8FBC-9672A861D5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0da37db6bebb29a7d06637509e230a9cbd5ec50","datavalue":{"value":{"entity-type":"item","numeric-id":3210175,"id":"Q3210175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0701439eedb62ed23183328f3a7f5f2e4e338610","datavalue":{"value":{"amount":"+0.7686917185783386","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":"Q1123639$4BD8738E-6C28-4CDB-9C98-197F23F7F29D","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":"b23ff55418e7ef3d501bfba02b353fd31c8ed0a1","datavalue":{"value":{"amount":"+0.7646452784538269","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":"Q1123639$BDA45016-A28B-43A7-BB96-D789A922B81F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3dcd164e48b174f72034a3553f6340245b8d765","datavalue":{"value":{"entity-type":"item","numeric-id":714812,"id":"Q714812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b3663655f915eb10899bf505306f6541041639a","datavalue":{"value":{"amount":"+0.7508214116096497","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":"Q1123639$A0D3F4BC-E77A-4D9E-919A-EDB8E3BB1DAE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the intersection of stacks and queues","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_intersection_of_stacks_and_queues"}}}}}