{"entities":{"Q5958329":{"pageid":8135131,"ns":120,"title":"Item:Q5958329","lastrevid":47755099,"modified":"2026-01-02T14:52:29Z","type":"item","id":"Q5958329","labels":{"en":{"language":"en","value":"Computing LOGCFL certificates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715330"}},"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":"Q5958329$85DA5599-D7B6-4725-A79D-E1FAD5AD0E2A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e98b005d2d07c573dcd28c3b6ba72114bf3a231","datavalue":{"value":{"text":"Computing LOGCFL certificates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958329$61D00AC0-3889-4B18-8697-09074BCA9B30","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a1545a5f0d45255fcf15ac237285ca28ae9f6b1e","datavalue":{"value":"0992.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$C3207FBF-5DBD-41D0-9F5C-EC5C478B984F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77c27440f611f390f1b3cccac525db7f86adc8fa","datavalue":{"value":"10.1016/S0304-3975(01)00108-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$BC830C7F-94B4-4699-B9B0-76E3EC644524","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ea9f01e952d7c8681ab3cdbdd2dab7be8167564","datavalue":{"value":{"entity-type":"item","numeric-id":202112,"id":"Q202112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$94BCC432-A685-49A4-B56B-1F8FE7A3F0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cd7123f74d155fe14856de0656eddfe851c66cd","datavalue":{"value":{"entity-type":"item","numeric-id":202113,"id":"Q202113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$DFB285B9-9EF2-4B9F-9871-9976026C433E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc4d4b989f90c820cd25ada1b68dde36e393eb05","datavalue":{"value":{"entity-type":"item","numeric-id":235708,"id":"Q235708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$78DAB69A-AFB0-4683-BB8D-0552F9671A1A","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":"Q5958329$AF697A8D-57A3-4A63-BD50-D290E1A2579F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958329$C4877AA6-B242-4396-A180-F79E4FEE1732","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c807ffa4cd61ed027b50a77cf476af843ed5ff1","datavalue":{"value":"The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in \\(AC^{1}\\), the problems in LOGCFL are highly parallelizable. By results of \\textit{W. L. Ruzzo} [J. Comput. Syst. Sci. 21, 218-235 (1980; Zbl 0445.68034)], the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM \\(M\\) recognizing a language \\(A\\) in LOGCFL, it is possible to construct an \\(L^{LOGCFL}\\) transducer \\(T_{M}\\) such that \\(T_{M}\\) on input \\(w \\in A\\) outputs an accepting tree for \\(M\\) on \\(w.\\) It follows that computing single LOGCFL certificates is feasible in functional \\(AC^{1}\\) and is thus highly parallelizable. \\textit{E. Wanke} [J. Algorithms 16, No. 3, 470-491 (1994; Zbl 0804.68048)] has recently shown that for any fixed \\(k,\\) deciding whether the treewidth of a graph is at most \\(k\\) is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in \\(AC^{1}.\\) We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an \\(m\\)-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$85A99868-B2AC-44E3-8462-B4290624E2E9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$2A72BC10-6167-4309-9DBB-344ACF4A9370","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8bd04fda6638e107046160d364b3f506720ee9b","datavalue":{"value":"1715330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$035917D9-F90F-4091-93B3-6516CABF27B4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$83BD7FBD-995A-4BBE-BC5D-7C7D7F7C3A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbb67bdc2fab0aa4aa89319e3e45f26f77058037","datavalue":{"value":"LOGCFL","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$968B3F8E-BA50-4F4A-8FD4-3F2079FF2812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$E6AB597A-2DCF-4EC9-A941-40F0F37F4BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$8A5C8114-DE42-4D99-A42A-1BA1E993819A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$500F759B-62BB-4EDC-A9D3-13D7E178940B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00fab533cd38d922e3a2c54a153ccdfb1b56ca89","datavalue":{"value":"constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958329$1D90FDF6-CAE6-426E-9E69-9CAD4E6021BB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a627c32634f1d828ffc5b35cb7e868afa3b8ee67","datavalue":{"value":"Q59259713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$2F284262-F614-4032-AF42-9C0DF8659E3A","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":"Q5958329$3D7B84DB-81FF-4E8B-BB9D-62770264012F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e824f81766b643e08cbe8282ed8ef2f4c0b919","datavalue":{"value":{"entity-type":"item","numeric-id":5248521,"id":"Q5248521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$11372BD6-6F80-4374-9244-9B80BB44F515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a10a48192397756c56e8d239a6da6afe78ad78","datavalue":{"value":{"entity-type":"item","numeric-id":1274913,"id":"Q1274913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$6ECFE3F4-C3DA-4999-ABBC-97819E97E19D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d92b7073011bb1b4985d7d526f565ba0b3fbd9f1","datavalue":{"value":{"entity-type":"item","numeric-id":4699283,"id":"Q4699283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$EEADD138-37C7-40F0-9662-F4926F908994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae867168c941791a545c80d9051c23a76351caec","datavalue":{"value":{"entity-type":"item","numeric-id":4210129,"id":"Q4210129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$F64E3D77-132B-4054-903E-B39B72791309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23708f3ee0b536410829c31900335701f20e86cc","datavalue":{"value":{"entity-type":"item","numeric-id":3835019,"id":"Q3835019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$6438F020-6DA6-4C99-805A-48796F910C27","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":"Q5958329$511044E6-3F1F-4F11-AC17-F1BF29022122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$22274591-00DB-4711-855C-D592DAF7873A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1134f2341d7e5000fd707505605e06ca29388803","datavalue":{"value":{"entity-type":"item","numeric-id":2641288,"id":"Q2641288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$58E55B73-D6C1-4AD0-A0C9-148664F948CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf3e133365d57dfbd2c07919f3093669a42c66e","datavalue":{"value":{"entity-type":"item","numeric-id":5928867,"id":"Q5928867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$A425ED64-BF58-4127-8134-E9194597B4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$7DCB2DFA-FE60-47DA-B9C7-53B0B4DD37AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53b3edc10849b5250c2bbbd137d0fea8a9ee868a","datavalue":{"value":{"entity-type":"item","numeric-id":3196620,"id":"Q3196620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$B88821B2-096E-4B35-9941-6009288B24E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"280236dae81e64d1ede14823c2ba628084078301","datavalue":{"value":{"entity-type":"item","numeric-id":4358054,"id":"Q4358054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$4CB1E699-DBD9-4993-A888-E45448380D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$A157CEF4-00CA-4117-B71F-4093BD6571D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c568fbb12fc5452c9699a0a3e0159154b2a6454a","datavalue":{"value":{"entity-type":"item","numeric-id":4385525,"id":"Q4385525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$D5B30474-81BB-40AC-BABF-DE412CC10345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e758cd2bc5a480bf2f8770060c56468b024b166","datavalue":{"value":{"entity-type":"item","numeric-id":1337684,"id":"Q1337684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$3CC4D67B-F08D-4A52-8E01-7DD5B4029046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a411ed69f384bdf86cb18f337464d37b8a955ad","datavalue":{"value":{"entity-type":"item","numeric-id":4251062,"id":"Q4251062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$FDC2E0A1-2B52-4E2B-BDFB-71EA4EB20406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa6f96333dbc50fac48c699990e242711eb6e69b","datavalue":{"value":{"entity-type":"item","numeric-id":4197337,"id":"Q4197337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$ACAF563E-8713-4B5C-BD1D-2CADC20AC57A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$AA96C406-4D9D-409E-918F-506D00DDEB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e11de7132c10164732e9b26841e64c659613e5","datavalue":{"value":{"entity-type":"item","numeric-id":4142695,"id":"Q4142695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$94D2913F-15E5-4D88-9CD7-3613DE08D325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa2be2a790024977ffe2e7d19d01151d207a02d8","datavalue":{"value":{"entity-type":"item","numeric-id":1176109,"id":"Q1176109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$3E5CC1C5-B8BE-4897-B24D-F519081E7892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e717e851a207e7ca3825381bb2197443eb1740f","datavalue":{"value":{"entity-type":"item","numeric-id":4290918,"id":"Q4290918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958329$62E60D3B-F2AA-4B3F-859C-29ED9EFB1598","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"d611cfbbc9309dac2b35ad4866a7452da4d44a9e","datavalue":{"value":"journals/tcs/GottlobLS02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958329$A8698F3C-A7A9-4277-938C-BB1E0DEC18FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edefe33cce038e0abc6689d5fd84cfcf3e83a13c","datavalue":{"value":{"entity-type":"item","numeric-id":4290918,"id":"Q4290918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8640d61834f9ca448fdc42c976a95c39a5508ae6","datavalue":{"value":{"amount":"+0.8123130202293396","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":"Q5958329$736F085A-02F5-4271-8632-C74758EE4517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19cecd3603a6a648e0284a97edfeb22ea293b384","datavalue":{"value":{"entity-type":"item","numeric-id":1176109,"id":"Q1176109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffdc96aed8a81c7c244bda3e2a7152724ba970f6","datavalue":{"value":{"amount":"+0.757914125919342","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":"Q5958329$8859571A-539F-42A7-99E9-B60948E98340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d21df1c22cd151da072bd94da5399250b7ca432a","datavalue":{"value":{"entity-type":"item","numeric-id":4645184,"id":"Q4645184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9afa6de3661e203a55f64f30c0873621a0f88e44","datavalue":{"value":{"amount":"+0.7545313835144043","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":"Q5958329$0613E1C6-D285-4BE7-A720-B8A42B26891B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4988c8c3fcc8686751dd1179a13dcea06b4f1af6","datavalue":{"value":{"entity-type":"item","numeric-id":4864433,"id":"Q4864433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b3d3b7c4de874a7e67d195fedb5947eccf4b3d","datavalue":{"value":{"amount":"+0.73292076587677","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":"Q5958329$B84C0EC7-5843-49E6-9109-80726533419F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54971bdb5f6072c500ce009e99e3a0ab2928a080","datavalue":{"value":{"entity-type":"item","numeric-id":3196620,"id":"Q3196620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68fa35fc425160c4de9e24aa7c345c66731c73cc","datavalue":{"value":{"amount":"+0.7298768758773804","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":"Q5958329$4F37C8A4-6956-4CD6-BAF8-540A840A68DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958329","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958329"}}}}}