{"entities":{"Q2638772":{"pageid":2649515,"ns":120,"title":"Item:Q2638772","lastrevid":44545047,"modified":"2025-11-23T19:11:38Z","type":"item","id":"Q2638772","labels":{"en":{"language":"en","value":"An algebra and a logic for \\(NC^ 1\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4182811"}},"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":"Q2638772$FBF98EC9-ADF2-42EF-A815-F99C24C98C08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0fe66531ca68218c63812898a3449c70439a61dd","datavalue":{"value":{"text":"An algebra and a logic for \\(NC^ 1\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2638772$8390E88B-803B-4C69-9D30-FE7A26CD0B22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b935ae4a47d819aeac30b8053d8bd8567969b825","datavalue":{"value":"0717.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$DB8C8B4D-AF8D-4B2D-9F3E-E62B9B761E6D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e711262eaafbde914e64ffe8628540fa05125504","datavalue":{"value":"10.1016/0890-5401(90)90063-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$63971C24-BB75-4CAF-B7F8-413C40089531","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46e384ba9e92c2d1801e5e36038afcb91974b185","datavalue":{"value":{"entity-type":"item","numeric-id":917542,"id":"Q917542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$1F5DDF61-F49F-4633-B1FA-45E6BB47FB02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a017d0a1ed2f145b8997b1203f62d88984b25fa0","datavalue":{"value":{"entity-type":"item","numeric-id":400435,"id":"Q400435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$5473A70B-10EF-46E6-B739-65ABBF448159","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":"Q2638772$EBA322F4-D249-41A8-BE89-0008A822D27E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2638772$48D46E88-63DF-4F1B-9798-FB9FEBE65B7B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fdcc048a631bac8ced01931904337598d0cfe48c","datavalue":{"value":"This paper, which appeared in an earlier version \\textit{K. Compton} and \\textit{C. Laflamme} [A logic and an Algebra for \\(NC^ 1\\) in: Proc. 3rd Annual Conference on Logic in Computer Science, (1988; Washington (IEEE Computer Society Press)], presents an algebra and a logic characterizing the complexity class \\(NC^ 1\\). In the algebraic characterization a recursion scheme called upward tree recursion is applied to a class of simple functions. In the logical characterization, first-order logic is augmented by an operator for defining relations by primitive recursion provided that every structure has a relation giving the binary representations of integers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638772$89DCA0D0-0A49-4124-BB3F-6D8C492F89AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$D0199A7B-29B6-4298-98A6-02E641968038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$BBA6C97E-C8C0-4466-AC31-B3BEF1873EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e671cb9a7cd5542f21890d12b2e8ee004a8c8889","datavalue":{"value":"03C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$823CDA2A-6EF1-427E-8643-5F3F44901D83","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"677e9b9832dd5c5239f948afef94f05e857e1fb9","datavalue":{"value":"4182811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$3F607696-CFC7-41F6-BCD6-4DB2647A1104","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b92e80f7dd3eccbf54828ae5451e935efe00ed6e","datavalue":{"value":"complexity class \\(NC^ 1\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638772$A59B0883-5D57-4577-B134-783EB4B0476C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a201a8779f110985d707176577b688d9a6216e1","datavalue":{"value":{"entity-type":"item","numeric-id":649735,"id":"Q649735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$C3390723-CD72-46D7-B294-5D36201E7111","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":"Q2638772$7072A34E-AF38-429B-9C9E-CDBE77BCF186","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"59da2a1d5903b23f997f8d378342ceffb4fc5166","datavalue":{"value":{"entity-type":"item","numeric-id":1176198,"id":"Q1176198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$8F1901EE-F104-4F3D-AC3C-FD27ED276FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"371e60689fc418f92aaf6266f6bda684000bf60d","datavalue":{"value":{"entity-type":"item","numeric-id":4102958,"id":"Q4102958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$C5E3B667-12AC-489C-9120-74B146B02E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465c44674a94414cb55e7dc8cbdf974e7462af9b","datavalue":{"value":{"entity-type":"item","numeric-id":3287248,"id":"Q3287248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$77029453-D540-4A17-A714-3F74D698B3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a628cb64400cb3daffe7c8b3b6a4710e9daa6946","datavalue":{"value":{"entity-type":"item","numeric-id":3800030,"id":"Q3800030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$52B8E09C-9F43-413C-8CF1-379C97EE99B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0909c5baebe8e5f5a9e964f05c720f232deade69","datavalue":{"value":{"entity-type":"item","numeric-id":5586401,"id":"Q5586401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$699CB2BA-18E0-4C6A-A7EE-C8C0346EA67F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$857D6B88-E470-46A9-9A7B-781447703305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef6d200e493964b07f6f93eda4c1ae61358d7d05","datavalue":{"value":{"entity-type":"item","numeric-id":3848195,"id":"Q3848195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$7BA8A22D-2B8C-413F-8F27-6FCF2815FE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$8D283888-24A2-49C3-91FA-39EC0767339A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a675fab4321817783597d6a1b8160efcb24c4ec","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$03A889C7-3291-4087-A54A-C52EC4D3EF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$6202A9C8-5C76-47BE-B280-381D7474E9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3a5f8c38dc9aa69650033303ed3bcc47054a76a","datavalue":{"value":{"entity-type":"item","numeric-id":3942945,"id":"Q3942945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$BFCBDE22-C852-4ECE-BC7E-47549F338622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2146e12d70096585412fa50f364e0fbe43b7e82d","datavalue":{"value":{"entity-type":"item","numeric-id":3293402,"id":"Q3293402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$F0455BEE-20BF-4AD8-8E9D-13489FE88FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638772$F2370D0E-3547-4934-83D4-FD395684187A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d7ff378b983101809ee1c801ea22d6bd4060e58","datavalue":{"value":"https://doi.org/10.1016/0890-5401(90)90063-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q2638772$B949C288-728B-4085-B80F-3AACEF4F5365","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9a6a02dc8f32810a28846a3196d00a10ebcbd72c","datavalue":{"value":"W2132858301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638772$4B82C098-0F57-4E15-AD4A-06E9F13250C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61520f6ee560181119082d42a382f47106370c9","datavalue":{"value":{"entity-type":"item","numeric-id":5202993,"id":"Q5202993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77017fec512947cecc0223a5e1629d35d630cd5d","datavalue":{"value":{"amount":"+0.892575","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":"Q2638772$19FD1B6E-57E1-49B6-A4EC-5881E8A63B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9349563c94c08e53e0baa831964759d3985ad139","datavalue":{"value":{"entity-type":"item","numeric-id":4011715,"id":"Q4011715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30c93f6c6d88f1e8ff15df570408b3c91094dcfb","datavalue":{"value":{"amount":"+0.8921631","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":"Q2638772$72E01D8E-83D4-4888-9A0D-52B074439008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e119afc74ce3b88bf5ae6bb6bf53903f84cce7d","datavalue":{"value":{"entity-type":"item","numeric-id":5184904,"id":"Q5184904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e43afaa7ef9158306221a8df64654f216e09a80","datavalue":{"value":{"amount":"+0.88936293","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":"Q2638772$40A52CFC-AE5F-4F4E-BC31-C065DA10694C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"377e3502c73487a00dfadb057623b5d7ac84f225","datavalue":{"value":{"entity-type":"item","numeric-id":5190972,"id":"Q5190972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceb583d9da4f6f654eb22d588e1760f7824ae15d","datavalue":{"value":{"amount":"+0.8858545","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":"Q2638772$08F0C063-9DEB-418A-A776-908022EFE70F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c2d984f2ebe89f8b3f38de23404d52750dc6562","datavalue":{"value":{"entity-type":"item","numeric-id":3424133,"id":"Q3424133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf9b8b894c1bce7a31c96bf16526a27ec9e5ae44","datavalue":{"value":{"amount":"+0.8858396","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":"Q2638772$541ABCFC-7340-4BEC-BAC9-E01BD3238B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc507baeb1588be1e509cbc57161dd9d68888b37","datavalue":{"value":{"entity-type":"item","numeric-id":4291709,"id":"Q4291709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"172d9d9184edc1cbe1b1629ae841bce03d4bec91","datavalue":{"value":{"amount":"+0.8832567","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":"Q2638772$F40AD02F-A6F9-4566-8191-E22FEF94AE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcad3da10aa83e9b1f2de655fc4466ad33f66d9f","datavalue":{"value":{"entity-type":"item","numeric-id":5749292,"id":"Q5749292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"172d9d9184edc1cbe1b1629ae841bce03d4bec91","datavalue":{"value":{"amount":"+0.8832567","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":"Q2638772$85E884FC-382A-4650-9760-9311158860A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ec7c1133aa216690b3133bab1b08a0cb38f367","datavalue":{"value":{"entity-type":"item","numeric-id":1799291,"id":"Q1799291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f0626e42b37e5256aee3da2a1be0bcbb1530ad8","datavalue":{"value":{"amount":"+0.8811651","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":"Q2638772$D528C2AE-33F0-4744-9D36-420A636008D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49758ae7f0c24f36fed850c61c492dbbf6196fb8","datavalue":{"value":{"entity-type":"item","numeric-id":3815297,"id":"Q3815297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2aa8381c85261de73c5ff31f13f1290e0664cde","datavalue":{"value":{"amount":"+0.87866294","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":"Q2638772$6AE4C7EE-2C2C-41B6-AF13-83165688BDDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2638772","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2638772"}}}}}