{"entities":{"Q1333263":{"pageid":1344002,"ns":120,"title":"Item:Q1333263","lastrevid":46279791,"modified":"2025-12-24T11:38:12Z","type":"item","id":"Q1333263","labels":{"en":{"language":"en","value":"Deciding emptiness for stack automata on infinite trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 638556"}},"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":"Q1333263$B9E95A92-451D-4D93-AEC4-81D80938C8F2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ae2f09d25d2e06f76795b2aff93f6b97f413f7c","datavalue":{"value":{"text":"Deciding emptiness for stack automata on infinite trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1333263$F243FC2E-2F52-4EE5-86EC-E85ED9A4CBF5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad95e44dbfa141c6103afb10b72303cdd53dbdcd","datavalue":{"value":"0820.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$BA5EFF6C-3440-470F-8736-B349C6ECBB08","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d86d555bd6cd1001c3d6ecad72fc1ab67c5fdce1","datavalue":{"value":{"entity-type":"item","numeric-id":209473,"id":"Q209473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1333263$CABB5F90-5124-4176-A6AA-FC6103C36955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bd2d2d049053aed2d8cff9396f23cbc7b0543d3","datavalue":{"value":{"entity-type":"item","numeric-id":207395,"id":"Q207395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1333263$E499CA17-D050-4BCB-A5EA-5FBD79B67AA9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1333263$19100BE3-273C-4657-9E6A-55BEEA2A1A04","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a511c8ef0b44d10360e4b2f51c22be5a4c1a9ced","datavalue":{"value":{"time":"+1994-09-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1333263$BDA4B442-EC09-417D-BD42-42740FF5FBC8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"26cf4af9b8bcf9d4caf064735d947bd34bef60a0","datavalue":{"value":"It is shown that the emptiness problem is decidable on stack automata on infinite trees. The authors give first an elementary proof for the corresponding problem on pushdown automata, and then they reduce the emptiness problem for stack automata to this special case. A computation of a stack automaton accepts an infinite tree if there are infinitely many accepting states on every path.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333263$53AC494D-54EF-4243-B284-AE13B745DF5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$292DEE9E-7E47-4E00-BDE3-4E57BBDFA0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$F3596A1B-4AAB-4EC5-9CB7-EE74862D403C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$E9E26B68-D97B-4908-90F4-4D7E81F1D404","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"397d9adb9cdfad630817e70a2963b3d6d44bb780","datavalue":{"value":"638556","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$2DF6CEA8-04C5-40EB-B5C5-8EB71ADF6158","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9159d4f959d21ef7c3c5f2d36ede4144c26f9c","datavalue":{"value":"emptiness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333263$56109AB4-E195-41E8-886E-8D79C3AF89B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67665b6417e603cde38f9817cb7ba85f606474fd","datavalue":{"value":"stack automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333263$6946C5E1-50D9-42E2-9316-01828F34D760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b4e53e5468cf9acbc0da6af2b3e9ef761de9d7f","datavalue":{"value":"infinite trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333263$647C35B6-A34F-4E20-9E59-8EAC35F132B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"456c672ca15cab74651e643baa7549046be81ae8","datavalue":{"value":"pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1333263$4597CAE5-9762-4C7D-8B01-C6589F393BB2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e0db3e87cf0564d4c180dc3531c145e91e81ccd","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1333263$9B87040F-CC6E-4C9A-ABA9-6B46E2AA353C","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":"Q1333263$99ED8508-BC93-49D3-94F7-CC363489E552","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"521a7a7d72dbb337d4cd8e16394d4174d3d1342a","datavalue":{"value":"https://doi.org/10.1006/inco.1994.1073","type":"string"},"datatype":"url"},"type":"statement","id":"Q1333263$39141863-B7BB-458B-ACB4-EC6461C9437B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6cf757948138589f17bc8c944aca0f16e1364134","datavalue":{"value":"W2024395666","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$3CFAEF2C-31AD-4E54-863F-6735CA424E6B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79c34da76069d261dee475689b08e72c75666440","datavalue":{"value":"10.1006/INCO.1994.1073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1333263$F7D1C2E5-3B00-42B1-A357-3F5AA9DD388B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07ce0f71dfe718fecdc5f1f528d6af24510bfeb4","datavalue":{"value":{"entity-type":"item","numeric-id":4853336,"id":"Q4853336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4548c407f58063fea2ee6c3fde5449ef3e4e5dc","datavalue":{"value":{"amount":"+0.789409875869751","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":"Q1333263$6BB0B12C-4A3C-4F23-80D8-187FA7785041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbacb60a492d4dbeeae1a1b279e9882990d0083c","datavalue":{"value":{"entity-type":"item","numeric-id":4020278,"id":"Q4020278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cf429c90026524f6809a235b702c3f47105c58f","datavalue":{"value":{"amount":"+0.77445387840271","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":"Q1333263$9D0BE2F1-4B3B-4265-86CD-E7757CC3BF20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"594a79b9a6e530bd6a24ad15218c5cbb623ef176","datavalue":{"value":{"entity-type":"item","numeric-id":4879207,"id":"Q4879207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a9cf654e770a9226597b01ff96a56d41a3860d6","datavalue":{"value":{"amount":"+0.7743175625801086","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":"Q1333263$13E78ACA-D855-42F3-B62E-155811CF370C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f416d20c69b3f86bf37a507d6f30a51e34052efd","datavalue":{"value":{"entity-type":"item","numeric-id":5216326,"id":"Q5216326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e1bb7456185996eaf455aa52f878ede5c7d7b77","datavalue":{"value":{"amount":"+0.7730894088745117","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":"Q1333263$4F4731C8-0B18-43C3-AD26-D73BF4A938FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1333263","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1333263"}}}}}