{"entities":{"Q1736808":{"pageid":1747549,"ns":120,"title":"Item:Q1736808","lastrevid":56702109,"modified":"2026-03-19T00:32:50Z","type":"item","id":"Q1736808","labels":{"en":{"language":"en","value":"A gentle introduction to applications of algorithmic metatheorems for space and circuit classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042353"}},"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":"Q1736808$25A90071-60D7-4196-83AC-307C78F61B86","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"03f4b6d040057cedd0d83e572613f6b5325b711f","datavalue":{"value":{"text":"A gentle introduction to applications of algorithmic metatheorems for space and circuit classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736808$342EAF0C-E813-44C7-A338-597943E8ED02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"08f5332aa42b226a3dbc37f90547a9ecae24a65d","datavalue":{"value":"1461.68249","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$303CC220-105E-4D94-851D-A86A73A6A91E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2b224aab66ffb4af458805268689af05df667de","datavalue":{"value":{"entity-type":"item","numeric-id":418169,"id":"Q418169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$E8774577-8869-42F3-BE76-EE4A303EFC06","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$9988CD20-1094-4F0D-B785-0BEEADEBA75C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736808$E75399DD-48FD-4804-B266-DE664107642E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c3d9748d7ae9abddc9b4d78317d3f932eb9a357","datavalue":{"value":"Summary: Algorithmic metatheorems state that if a problem can be described in a certain \\textit{logic} and the inputs are \\textit{structured} in a certain way, then the problem can be solved with a certain \\textit{amount of resources.} As an example, by Courcelle's Theorem, all monadic second-order (``in a certain logic'') properties of graphs of bounded tree width (``structured in a certain way'') can be solved in linear time (``with a certain amount of resources''). Such theorems have become valuable tools in algorithmics: if a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. This paper is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space and circuit classes, and tries to give a flavor of the range of their applications.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$BFD49567-5EAA-42D4-979E-44CA1DE81FCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1bcdc2a107fd2414d151e8610f3471a8784e75bf","datavalue":{"value":"68W01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$284DD940-295C-4797-BDE9-37FD8637F563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$A4369498-6409-4B1B-A28E-386AC0253EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c11e1636e28bd1a59d5342c1523bca4bf56a601","datavalue":{"value":"68Q06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$AFEDF3CE-8D10-4011-BA11-118430250BB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$E5FD192F-6358-4F83-A9CF-911B5BDBCFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$F0E68013-BFF0-4893-8049-AAFBFEC521EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a83749234b8223c3752bfd6e69a2574f848c8d5","datavalue":{"value":"7042353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$82BC2624-1484-4C56-9083-26823F18F38F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4dd8fcf4a59771b2d4e31f12530ee8411d96d79","datavalue":{"value":"algorithmic metatheorems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$5CC5068D-B9C8-4A8C-AAB4-D7A6538F10A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7fe54176508cb6b1b6c307058a5e4029fde3455","datavalue":{"value":"Courcelle's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$D90E50E3-7922-489C-9BBC-C829360945D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$68FE3620-C91C-419A-A83E-639F7E29671C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56dbab920052fb03991fb8196df76a9cb514a720","datavalue":{"value":"tree depth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$31BE1A96-4968-4E14-8635-40F308EA03CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$15007EC4-B7FE-4AE6-A965-C301F9A72C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f18bc21d823222e01f5a88a6fb3d1663d7daa25","datavalue":{"value":"logarithmic space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$39931336-403B-45F9-848F-32D72BB3E34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e67d275c7bb3311c1f61dcabb6777bb4cb0763f6","datavalue":{"value":"circuit classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736808$2D5055A5-9398-470B-8029-A6C20D52EA54","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":"Q1736808$C38EB3B0-E64E-4924-99A4-F863EEEF9F78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"388fbda93cd180a443edcf8521ed6cc8e2b1bfc9","datavalue":{"value":"https://doi.org/10.3390/a9030044","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736808$AEB39689-9CBD-40BB-88AD-AE8FE61B698D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f2686ceaa13c353a0d85923b84055b023152f7c","datavalue":{"value":"W2475093016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$595E6780-2360-412A-8651-2B616742B972","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3057af5a1af0350171fd6b2b79a79b332e0f350b","datavalue":{"value":{"entity-type":"item","numeric-id":4385531,"id":"Q4385531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$AB8C8E86-5963-442A-B252-7B2608EE1084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fea79ffe3a076af8b924158860accd261638c485","datavalue":{"value":{"entity-type":"item","numeric-id":3196630,"id":"Q3196630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$3C72FA30-2742-4571-A064-C0B4845AC754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fe56184955dbba620e4cb94dc309dfe37fcc19","datavalue":{"value":{"entity-type":"item","numeric-id":1974445,"id":"Q1974445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$093F5E2F-BD6B-4510-8AC0-04137621A5C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ea99545d688c2cf5ee66cf79d9217d7659688c3","datavalue":{"value":{"entity-type":"item","numeric-id":3812269,"id":"Q3812269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$7B543A7D-ACD6-4A01-AECE-B66931C68A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71217208be2b526c81d03cb506bbd73893189d5c","datavalue":{"value":{"entity-type":"item","numeric-id":3086928,"id":"Q3086928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$006A02C3-11A3-447D-BB31-154879432863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c5fb187cc80eb3e2747b5856073186fefa4c6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3118384,"id":"Q3118384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$730E9963-4F6B-4256-B8CA-2A7BE4E0E7D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e28f967fe1a78b6763b8821453d654cdd54f21c","datavalue":{"value":{"entity-type":"item","numeric-id":3172385,"id":"Q3172385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$BDC1322B-2AFE-40D3-9122-AFA9162944EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df698818c0dd57be3b2281fd72be32288a321373","datavalue":{"value":{"entity-type":"item","numeric-id":4227581,"id":"Q4227581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$C30E0DBA-1B82-447D-B4D2-B3D14DA066FB","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":"Q1736808$47F7BED5-CC16-4657-A6B6-FC55A73F8590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$EF2A0714-9AF6-4649-A8DE-BC2CE5812355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37582b4c778c46bf24fc41a8cb06c175f07e6d17","datavalue":{"value":{"entity-type":"item","numeric-id":1886318,"id":"Q1886318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$48CC5DDF-E313-4010-AA9D-A7BBEEECAC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"873424cc8d4e93946989cd39def93178ca9012e8","datavalue":{"value":{"entity-type":"item","numeric-id":3604402,"id":"Q3604402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$8B170137-29A0-45AD-96AE-9A19AC57DD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3c2f4eb9d2f79432cf2d0e594b401466caed137","datavalue":{"value":{"entity-type":"item","numeric-id":4601884,"id":"Q4601884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$F42D17D9-5CD0-40E5-B835-C4A80727099B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e970f70d236890859efcac5100bd90f20ec03563","datavalue":{"value":{"entity-type":"item","numeric-id":3113750,"id":"Q3113750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$9EC61565-4F13-49BF-9B3E-F94866ECAD47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c03bdde2160e97b05b3878523710001cdac260e8","datavalue":{"value":{"entity-type":"item","numeric-id":5501192,"id":"Q5501192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$34B57971-4F7F-446E-83B3-BAB012C9D3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb8c4ee63f9f703bd483aea72db19b5173ddf05b","datavalue":{"value":{"entity-type":"item","numeric-id":2955035,"id":"Q2955035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$180D1429-C724-4631-8419-5E30E58C7126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a828b43779c3f40de248eb0e5024ad5540b0819f","datavalue":{"value":{"entity-type":"item","numeric-id":2904750,"id":"Q2904750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$F6C0B959-0AD7-48CC-86C9-55A0E8BDD8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcbe163d4dd66ea81aad08eef749475dc55fd596","datavalue":{"value":{"entity-type":"item","numeric-id":3578301,"id":"Q3578301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$D396C894-3F56-49E9-BE78-DEFD910CE087","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":"Q1736808$3D6F4FE8-6514-4015-AFE2-37D6984974D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b25f9d90cbcc28e3f73f79a5515d30dc34194913","datavalue":{"value":{"entity-type":"item","numeric-id":2875160,"id":"Q2875160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$B22F4557-03F3-4BA3-B4D3-15B542E6E776","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1eb2c6caae486e438546417fadae0b5acc6af4ef","datavalue":{"value":"10.3390/A9030044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736808$CD436107-DDC4-4466-A6AC-B1011B38DF90","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ebb6798c08dcc6f5d1fe6a681f07c801ff88386","datavalue":{"value":{"entity-type":"item","numeric-id":3086928,"id":"Q3086928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d601e439bb92522c8ccd51ccd5de4e376541b352","datavalue":{"value":{"amount":"+0.8786901235580444","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":"Q1736808$075F4FC7-2E84-434B-978A-25E984A6C900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c58a61dec834f4b7f9c3b95a266a25aad8b2d03","datavalue":{"value":{"entity-type":"item","numeric-id":4981144,"id":"Q4981144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccf46f55cb1630c60df8841d2291c6609baca4df","datavalue":{"value":{"amount":"+0.863381564617157","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":"Q1736808$3722C418-FB70-4883-A43F-8927562B45CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc8ff447e5c797531ed141f38d2e6bcba09f8283","datavalue":{"value":{"entity-type":"item","numeric-id":3172385,"id":"Q3172385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01634bbb67a33a3db43df42af120ca27ca391214","datavalue":{"value":{"amount":"+0.8417312502861023","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":"Q1736808$7CB5FD3A-BC61-4551-B9D2-BEE955788B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc5435931d86571d4360d36b2e13206d8d9bf866","datavalue":{"value":{"entity-type":"item","numeric-id":3118384,"id":"Q3118384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44d7eb31bc35627b5df0cc4d9e78adf7ea40e5f3","datavalue":{"value":{"amount":"+0.8366010785102844","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":"Q1736808$FB422DFB-2D5A-4266-8B05-D7361E0A7C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b0f878a29090825086a1995561456ace90d05df","datavalue":{"value":{"entity-type":"item","numeric-id":2904750,"id":"Q2904750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c959d2021a6f1f641bbf9bdc935c0913a49776a","datavalue":{"value":{"amount":"+0.8339411616325378","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":"Q1736808$D188B498-7428-4C3F-A8B7-67607ECD3EE2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736808$CF51C8C0-A299-423B-BBCB-92840727F086","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736808","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736808"}}}}}