{"entities":{"Q1123637":{"pageid":1134386,"ns":120,"title":"Item:Q1123637","lastrevid":67051467,"modified":"2026-04-12T14:36:28Z","type":"item","id":"Q1123637","labels":{"en":{"language":"en","value":"A grammatical characterization of alternating pushdown automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110147"}},"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":"Q1123637$FE5F2E0C-A14C-45A5-A1E8-58B3B0B600CC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"464c5750067efddad1be7877e64165a365935831","datavalue":{"value":{"text":"A grammatical characterization of alternating pushdown automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123637$2379DC30-1250-467C-97E7-8D1DC3AEFCD2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b36db9ffbd9cacdd62b30243ccd4290982b36acf","datavalue":{"value":"0677.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123637$A43F4600-2243-412E-8F46-E4EB4E85490C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"faec2d1191fd3f488a16bede989463a426f4a066","datavalue":{"value":"10.1016/0304-3975(89)90023-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123637$5E468710-CCC3-4E9D-9077-B788A2310B39","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf44b91f73584e67838dcd7b9766693a96abac90","datavalue":{"value":{"entity-type":"item","numeric-id":557820,"id":"Q557820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$0C7817F9-EA5A-4E53-83E8-F74F31E02ED3","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":"Q1123637$D7000A13-B5C7-43B4-8B79-2E214AA45FEF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1123637$EEE430EE-A18F-4D82-8749-5B1AF0EC57E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8af8d42fed08320ef7ae3e6e67f087251f6ef65b","datavalue":{"value":"An alternating context-free grammar (ACFG for short) is a quintuple \\(G=(N,U,\\Sigma,P,S)\\) where \\((N,\\Sigma,P,S)\\) is a context-free grammar (CFG), called the underlying CFG of \\(G\\), and \\(U\\) is a subset of \\(N\\). A convenient concept of acceptable derivation is introduced and then the language generated by \\(G\\) is defined to be the set \\(L(G)=\\{\\text{value}(T)\\mid T \\text{is an acceptable derivation in } G\\}\\), where value \\((T)\\) denotes the value of the derivation \\(T\\), a parameter related to the root of \\(T\\). The concept of an ACFG is used in order to characterize grammatically the alternating pushdown automata, which are proved to be equivalent to ACFG. The importance of this result can be understood in connection with the general concept of alternation as a generalization of the notion of nondeterminism. The author recalls that the notion of alternation has contributed a considerable development to computational complexity theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123637$06A8EB47-0D38-453B-B78D-55D638EF5382","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123637$2B866A4A-98FA-4127-B229-DEED7973D2D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a55433009ae4f9c790c3194f1b52ede89947d197","datavalue":{"value":"4110147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123637$89EC893C-1E73-4E3F-880C-DD508A8C015E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01174e2bb474430787f1cc88bb14709dd4f43059","datavalue":{"value":"alternating pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123637$E78C90B8-298B-4E21-876E-C3175C95F5E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23a2cc8183c45ee629c7fd91e2bc8902eded180f","datavalue":{"value":"alternating context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123637$C8838EFB-6E85-46E9-9DE3-F61FE0E98C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec56b43a88f89c66f098287efe37416ab894948f","datavalue":{"value":"acceptable derivation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123637$4B9117F0-82DF-4BC9-BA74-3E44AD726134","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":"Q1123637$CE891173-5EFD-480C-9308-398BE49C8E87","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4e7e327323d8e6f9d8f516e466ae0ac03611657d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90023-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123637$B4C732A9-3C2A-429E-8234-B0CCA37110A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f73ac14d46eeaa47c15cab6a968720848aee4314","datavalue":{"value":"W1983957380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123637$921B7494-85A4-4AB3-AF21-095220DE8C87","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$70CF92DF-D1A7-4C80-831E-F6779BE5F42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$9DFE7A44-FEC6-4B38-9335-35BD0DC18BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9991d12c610af612098995f36bb9f37d525e6bf2","datavalue":{"value":{"entity-type":"item","numeric-id":5557460,"id":"Q5557460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$4022CF59-C68B-4FD7-8E3B-699CEE8E6037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efaa00c8a5f012e81078b9151d9eb7bc76ac3ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3959454,"id":"Q3959454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$0E366A51-4281-4588-836A-8AE9342579C5","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":"Q1123637$EAD30E0C-2AA7-4E40-82E7-81F318DA38EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2125d23285b42025489c119f78f60c43fe39833e","datavalue":{"value":{"entity-type":"item","numeric-id":1068537,"id":"Q1068537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$F5496282-188F-466F-B638-CC80474BE6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c2e166c21268174f22435e129942ae345904e6","datavalue":{"value":{"entity-type":"item","numeric-id":3325044,"id":"Q3325044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$E68AB058-D7EB-407D-BA96-2E7FA6CBB8BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1cc1ec1d229ad034a80912afb90ab01c9093f2","datavalue":{"value":{"entity-type":"item","numeric-id":3718176,"id":"Q3718176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$E6637EFD-6683-4EE0-853C-33D0FD0ACAC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$EE630EF9-BDE5-4AC0-8187-62D616CAE504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961718bec1ff5775006cd097ddc5e24540c59cee","datavalue":{"value":{"entity-type":"item","numeric-id":1077932,"id":"Q1077932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123637$E8A34C39-30AD-40D4-B122-71BFF3425C03","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ecfbb61d51330c52c9aea737d148a66704cacdd","datavalue":{"value":{"entity-type":"item","numeric-id":2377302,"id":"Q2377302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e247ab903a38cc55ae8972e839d6ae36cdeb40f4","datavalue":{"value":{"amount":"+0.9339095","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":"Q1123637$6C7A05A7-87E6-4357-9ECA-0A17A30F3536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ff7a1218abd0c5b4a53fcb6372802a10aca655f","datavalue":{"value":{"entity-type":"item","numeric-id":3511447,"id":"Q3511447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69367ebeb5cc444826baeec62f8fdfd1ed128c5f","datavalue":{"value":{"amount":"+0.92178524","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":"Q1123637$8EEAD254-E36E-43B3-BE95-283B9130F56D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7302c2dac8975d7dbee44fa416928af3a5e96db","datavalue":{"value":{"entity-type":"item","numeric-id":3325044,"id":"Q3325044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c86aead6f8061186e895224137e869123f418ed9","datavalue":{"value":{"amount":"+0.89934677","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":"Q1123637$BD7DD786-9886-44CF-A9A5-48AE5884C334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0562f737c75d8f8326adf7238cdf8e0fafdb15d","datavalue":{"value":{"entity-type":"item","numeric-id":3813317,"id":"Q3813317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"523545078e4235a5a34e3aae471cfcde906b6107","datavalue":{"value":{"amount":"+0.89582527","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":"Q1123637$B0D44C9F-F831-4E3B-BFAE-B870BE108CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc28261af46334a1534fcd27c2361e3301619aee","datavalue":{"value":{"entity-type":"item","numeric-id":3718176,"id":"Q3718176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"196799d74f0f53ee51858fe3fce6680471cb6184","datavalue":{"value":{"amount":"+0.89018345","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":"Q1123637$CA6E5BD7-CC0F-4505-8139-9FAF0DD80832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad11c7710d37f81a71338de363c1ed382dd5305d","datavalue":{"value":{"entity-type":"item","numeric-id":2941092,"id":"Q2941092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2abea13f93a8308c88c37804a09712b9d77cceb","datavalue":{"value":{"amount":"+0.8792244","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":"Q1123637$96ED1FA3-E21D-4E87-89D1-EE2B968DF1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9695a88a6a0bb1d3858998a72f3148ae78bd0425","datavalue":{"value":{"entity-type":"item","numeric-id":2999249,"id":"Q2999249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcf1c066f21e4bbe26a9c04aec007861a5cd8d27","datavalue":{"value":{"amount":"+0.87922424","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":"Q1123637$1533963B-1823-4B75-88A0-F1FD1BB7F118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6a16b3c286f3c0a6ea33bfc8a99fdb2a091334f","datavalue":{"value":{"entity-type":"item","numeric-id":3787475,"id":"Q3787475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f9f892fba9ad89d14fd33870b142c0a2779a521","datavalue":{"value":{"amount":"+0.876109","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":"Q1123637$AF4C9D59-CD53-410B-8191-9551DF312172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e8ce021f33ad9c7e990a309f724a819b83835de","datavalue":{"value":{"entity-type":"item","numeric-id":3816981,"id":"Q3816981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f9f892fba9ad89d14fd33870b142c0a2779a521","datavalue":{"value":{"amount":"+0.876109","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":"Q1123637$867C25F6-D5AA-4943-8499-A133BBD95146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70c7777a24c74df2523a2b2ff7977551f2a60ed6","datavalue":{"value":{"entity-type":"item","numeric-id":3525656,"id":"Q3525656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"703a990764f41cc155489a7f683e8f42c64b3e6b","datavalue":{"value":{"amount":"+0.8747839","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":"Q1123637$F3C7A9EF-D216-4A05-90C6-0B2BD82E6FA1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A grammatical characterization of alternating pushdown automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_grammatical_characterization_of_alternating_pushdown_automata"}}}}}