{"entities":{"Q805253":{"pageid":807101,"ns":120,"title":"Item:Q805253","lastrevid":42705471,"modified":"2025-07-08T16:40:14Z","type":"item","id":"Q805253","labels":{"en":{"language":"en","value":"Hierarchies of weak automata and weak monadic formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4203740"}},"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":"Q805253$939BC6D4-46DD-4684-8F31-970FD9031A3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3fdb72fbbb92edb2292efad49e09d87c05c5e7ae","datavalue":{"value":{"text":"Hierarchies of weak automata and weak monadic formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805253$E6ABA2CA-5974-4C19-B766-BDF039F614C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"737a45dd68343f1ec8dd22bb631147c30fc681e7","datavalue":{"value":"0728.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805253$EC40E814-D189-4D06-ABC2-68E7BAB9EECB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e052a0a8faa0045f602dc2945ac83ed042c4c938","datavalue":{"value":"10.1016/0304-3975(91)90283-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805253$E38C61A0-1CF3-4205-BD12-EEA4B07DB9ED","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":"Q805253$FE5B367E-C041-475C-9EEA-E2A723480023","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q805253$97CCA227-D9B8-4E6B-BB0A-1D5D6064E576","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d31fef8a9715ba5f5bcb124ba372a84432abfdb6","datavalue":{"value":"Given a set of trees, define its Muller index (the Rabin index, respectively) as the minimal Muller (Rabin) index of the alternating finite automata (afa) representing this set. First, it is proved that the two indices - the Muller index and the Rabin index - coincide, both in weak and in strong conditions. The main result proves that for k successor monadic arithmetics, a weak formula with a bounded suffix has m unbounded quantifiers (m\\(\\geq 2)\\) in the prefix iff it is represented by a weak afa of index m. An infinite hierarchy of weak indices for afa is obtained in this way.    See defnitions in the related papers by \\textit{D. E. Muller}, \\textit{P. E. Schupp} [Theor. Comput. Sci. 54, 264-276 (1987; Zbl 0636.68108) and Lect. Notes Comput. Sci. 192, 100-107 (1985; Zbl 0608.03004)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q805253$DFA2DE09-C7B1-4A21-A6FE-7D263895B06E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805253$3995C46E-CCF1-4051-8562-B6EC41D8CB37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"edea9f229c6721c3cf9f149750e092bf28e91fbc","datavalue":{"value":"4203740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805253$C7490A2B-E34D-4E7D-A336-B20A5A3C9C2A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b900beda0f148dc5a9e2e31fc6932299b913bd7d","datavalue":{"value":"Muller index","type":"string"},"datatype":"string"},"type":"statement","id":"Q805253$29458704-D9D3-42F5-AA35-C4FF7494D069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29d5c11e0e4a3072d68da54a30dfd8b86cb9b2d3","datavalue":{"value":"alternating finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q805253$16DFDB46-47D5-4653-89C2-B3D9D09E8DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1b8b9d03aa0dbbeaabd9c9b87fcfff29b9ecd89","datavalue":{"value":"Rabin index","type":"string"},"datatype":"string"},"type":"statement","id":"Q805253$4A302554-EF14-48E4-A9FA-B1B62A823E37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4e8170104535c441d8e1d6bd57a388363c0f3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1068543,"id":"Q1068543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$29ACA0B4-1380-4E4E-B2EE-D73B4B055938","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"42210bafdd52b4cbc4a62733feb51d89cc3d12b1","datavalue":{"value":{"entity-type":"item","numeric-id":224640,"id":"Q224640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$DB9EE4F5-2660-4F70-B85E-452F2592EB62","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":"Q805253$71D03C75-0F94-437E-9373-141E47616CDC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f39d200afcd180f3ea14687613ef2e2516564d1a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90283-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q805253$3E914C90-DA25-4B42-9B97-13CC785772D9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d5ad0534013aae319da412eca7ab25feccde949f","datavalue":{"value":"W1992595180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805253$28C84CD9-1E20-4BF2-B754-B87FFC7C04CC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c82154e66a2e8fea69e3328eced4f67343c9f4c7","datavalue":{"value":{"entity-type":"item","numeric-id":1214411,"id":"Q1214411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$909038F1-F47C-4C50-80D5-2C78CBD7D56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f7d501eca45f4e70219630914fce9c6989711b2","datavalue":{"value":{"entity-type":"item","numeric-id":3753490,"id":"Q3753490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$4E4E1762-258E-43E2-97FD-67CEACC11EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e5ed9f8065971b45983589a846153065d9db76d","datavalue":{"value":{"entity-type":"item","numeric-id":3787992,"id":"Q3787992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$FAD00DDE-25AD-4A31-9B3B-BD68D3888CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7161985b274b14fb28a3ad2e286151fe52dcea0","datavalue":{"value":{"entity-type":"item","numeric-id":4726235,"id":"Q4726235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$ADB18BBA-C9D5-4AAB-97CF-DBEA1BB5DC2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc8538023ff8d40f43d3f0f24e047ecceb14e467","datavalue":{"value":{"entity-type":"item","numeric-id":1098325,"id":"Q1098325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$E998FCCF-A5CD-4C35-AA72-A89F0426D0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46cecdac5a8fc71dede3e166189f135ef510fd6a","datavalue":{"value":{"entity-type":"item","numeric-id":5632564,"id":"Q5632564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$0FD60062-02D1-4729-AB4A-64E961706F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"300e1e7990d1f1904b1034a2731e332147efe257","datavalue":{"value":{"entity-type":"item","numeric-id":5616162,"id":"Q5616162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$D0E8B012-EE50-4137-AF5F-F42C6AF9A0E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59293eeb5b02bf53fbf8f0878a16024c278a1bec","datavalue":{"value":{"entity-type":"item","numeric-id":5592253,"id":"Q5592253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$D7215D55-E793-4F8E-9092-7F8C3158A361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be575331d770a3844c9a53865201d97f80b083ec","datavalue":{"value":{"entity-type":"item","numeric-id":3967525,"id":"Q3967525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805253$4F982C50-3F2E-4874-ADA7-791B34E9192B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0db3fb5740a89705196f1a2adcf748e5eeeab33e","datavalue":{"value":{"entity-type":"item","numeric-id":3025320,"id":"Q3025320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c74a6cfa10cc01c00be2c03b9e61358cb47870ce","datavalue":{"value":{"amount":"+0.9224715","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":"Q805253$A0D0DC56-35B3-4AC0-AB8F-1FA018B352FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149d90017813494af3d1634ff54c1c7b68979182","datavalue":{"value":{"entity-type":"item","numeric-id":3787992,"id":"Q3787992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fd8dc3f1fb2f50cf1019ef84bc1a3b05d5ff605","datavalue":{"value":{"amount":"+0.90824276","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":"Q805253$BE37AA52-725D-4056-B1F3-E620792BD138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"126daa27030366c87542406e636c4586a70f5474","datavalue":{"value":{"entity-type":"item","numeric-id":5038191,"id":"Q5038191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a697c6c8c953497bda3f9f3938f5fcd5dde2600","datavalue":{"value":{"amount":"+0.8970023","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":"Q805253$E5E28CD6-1983-4F07-A415-24F711411854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dea71c9d43af92ca4c3e8697babdcf340821c73","datavalue":{"value":{"entity-type":"item","numeric-id":2449047,"id":"Q2449047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fac4061cf640cdc7b489625e48815a0fd940ef1","datavalue":{"value":{"amount":"+0.8952822","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":"Q805253$19BCCB78-BBBF-4EDB-A22B-3D91709617C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875ab71b75434c0405ffea4b9a49e18890f7287e","datavalue":{"value":{"entity-type":"item","numeric-id":1193871,"id":"Q1193871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d8fc9292b9baa331a5cd3aaaff0b0d2a8e9a945","datavalue":{"value":{"amount":"+0.8944417","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":"Q805253$CABBB388-F390-44C3-958C-29CB458BEBED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"789c66e93af945020ac63c9c5a14fa8e77c11897","datavalue":{"value":{"entity-type":"item","numeric-id":4726235,"id":"Q4726235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"124044c539086f1ac0679073f1b61efecbd8ac9f","datavalue":{"value":{"amount":"+0.8886314","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":"Q805253$DC2FC44B-FCB7-427C-90C8-0F7B45CAD5D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c1cb744e836204235a33b303d4115c8b81e3aa4","datavalue":{"value":{"entity-type":"item","numeric-id":2754058,"id":"Q2754058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25010ee2f51d2c49b1866ee14650fbc69f99aedb","datavalue":{"value":{"amount":"+0.88172555","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":"Q805253$B0E7589B-BB78-4C8D-818F-2855AEC4530D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27da853d8f91b9f797336b2a119d8e4e3b8b60c4","datavalue":{"value":{"entity-type":"item","numeric-id":3340164,"id":"Q3340164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bae69f548fc6dc7213f7bcce2ec0674bb4a3081","datavalue":{"value":{"amount":"+0.88004595","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":"Q805253$4F63B461-C0D4-4E94-8034-89E6335BC525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e607ef4588220f1123499a7b4925cd7c1475275","datavalue":{"value":{"entity-type":"item","numeric-id":4992511,"id":"Q4992511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e223f3612a8288b293aa20dabfb9f6092529480b","datavalue":{"value":{"amount":"+0.87806296","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":"Q805253$5CCF2B88-E851-45E7-8EDC-954A04792218","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:805253","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:805253"}}}}}