{"entities":{"Q582922":{"pageid":584689,"ns":120,"title":"Item:Q582922","lastrevid":49344820,"modified":"2026-01-07T00:13:28Z","type":"item","id":"Q582922","labels":{"en":{"language":"en","value":"Parallel algorithms for a class of graphs generated recursively"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4131695"}},"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":"Q582922$017D2312-E7E6-4D0F-B7E2-A41FFC738E55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9335e01eb4c78b4db68e71be5f147a564199aab0","datavalue":{"value":{"text":"Parallel algorithms for a class of graphs generated recursively","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582922$CB596F78-BDE0-4211-9427-65F463AEB60B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78ca72c61d79f5af4e50880c4518f6917ed99ce5","datavalue":{"value":"0691.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$1A06CC98-5CF6-4F11-8475-D3B89E4633D4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72c36890a5d5b1e3cb7fb69807dc2503a77e50be","datavalue":{"value":"10.1016/0020-0190(89)90199-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$1514D81B-9707-49BB-80E7-E0A7DBA70164","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"446a873621e510ca421dac98a0ecf4b1b1cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":313971,"id":"Q313971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$B6492647-A9F9-47E2-8E3A-FC8A9B3E2422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"36284a15fbe0fbe4878c182b99d1eb8daf9ed6ff","datavalue":{"value":{"entity-type":"item","numeric-id":582921,"id":"Q582921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$CA7839CA-ACF0-4D39-8CC6-336D67B5E1D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$5FF5B882-24C5-4A4F-9A67-47BA93B222E6","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":"Q582922$80E6933E-D995-4C32-BD4F-F375AC95422E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a5a3cec3386ec980fe5ba710faeda9413565553a","datavalue":{"value":"A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols.    A grammar is given by an axiom star graph \\(X_ 0\\) with no legs and a set of production \\(X\\to Y\\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \\(X_ 0\\) by using the productions.    Let \\(NC^ i\\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \\(NC^ 2\\), and several NP-complete problems are in \\(NC^ 1\\), if the parsing tree is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q582922$872DFAEA-5A48-4BB0-83A8-4E48F03F8ACF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$EC7E0386-E238-495E-AE93-8D7DC968FECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$636F0418-E655-4B63-9F15-0AAA642D698F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$B0A1F862-6D02-46A7-B927-CE7751024B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$D0588DC8-7222-40A3-BAC4-5326FABBE9B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"382665660680874f4be62f39ca35b3912607f21f","datavalue":{"value":"4131695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$A817646B-3B6F-4D43-AF00-12ACA562729F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b99b1e01954f36b2bc8e00e08ffdc2eacfdc6f6b","datavalue":{"value":"graph grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q582922$1FC4F142-3F34-40A0-9002-7F250B84660F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cad5bc9a485aa46ea3c3246e380097d0d8214c78","datavalue":{"value":"NC","type":"string"},"datatype":"string"},"type":"statement","id":"Q582922$AB520622-21CE-4A07-BDD8-5738736BA9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q582922$31B22465-E2C3-49CB-AE1E-56E19267FC23","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c666ac2d78f9f2d8ad99cfc32edd5f33e6fa3ff8","datavalue":{"value":{"entity-type":"item","numeric-id":287186,"id":"Q287186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$A8D9BC11-FDB9-4B65-B5EE-5448976B5828","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":"Q582922$98733017-9E01-47BE-A9E5-07BC13998A9E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d236654d948fffd1f694bb97255cc7b0b58562a6","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90199-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q582922$6D96BD42-46EC-456F-8F3D-52D349D8510C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba77e0d042431c207370a5cef34276b42d67ac40","datavalue":{"value":"W2070146374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582922$D3E575DD-3B8E-4583-BF6E-C2673AFD15B9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$67CC9B2B-EAF5-4D91-8E8A-8943D625010B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c04a6c63bff4f80cdf6d1fa23c76258296aa2d","datavalue":{"value":{"entity-type":"item","numeric-id":3992991,"id":"Q3992991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$FBE892CE-E4A4-4B5D-B37E-61A4B6019DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae03da84aed52700c2113739cb70ff975ba781e6","datavalue":{"value":{"entity-type":"item","numeric-id":1107328,"id":"Q1107328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$E3B86850-3674-49B6-9EE2-5BA9BB4E29F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20fac3816dcac843ddbcd4f56ba7cf1b3b95759f","datavalue":{"value":{"entity-type":"item","numeric-id":1082828,"id":"Q1082828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$1259E917-57A4-4F26-AA17-7A8047FBE7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1362fbdd5993fbcd78940ade8948766527ea4c7","datavalue":{"value":{"entity-type":"item","numeric-id":3759947,"id":"Q3759947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$4D669911-6348-4864-8347-0C3B049FAFFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39a2b77e64dbb3ecf2e5ef657d6c92508e375a38","datavalue":{"value":{"entity-type":"item","numeric-id":3700838,"id":"Q3700838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$ADDB6871-666C-4FBD-A469-5837D8BCFD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef08bbfc118fe0069ac150faa6d6d6c907e0e3e1","datavalue":{"value":{"entity-type":"item","numeric-id":5753770,"id":"Q5753770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$8D43B3D5-6C74-4057-8C9D-AEF675FF62EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17ebfd224e1d2749f9c66e883ca18e79806fa046","datavalue":{"value":{"entity-type":"item","numeric-id":1109691,"id":"Q1109691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$47D8813F-0375-4832-95C1-8C7B4F798682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10d5e2ace3947ff448261418ff398fe9453cb910","datavalue":{"value":{"entity-type":"item","numeric-id":1095675,"id":"Q1095675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$4CBAEB75-F901-414D-A394-5C03A824A15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3054803ad9ba5aea14f3e99ca3d5ce72c154a9b8","datavalue":{"value":{"entity-type":"item","numeric-id":1096400,"id":"Q1096400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$A9B147A7-619F-46C5-84C9-AFBE2DE117CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9b8bc51f4e0e0529723f91ae841a5320fce1a39","datavalue":{"value":{"entity-type":"item","numeric-id":1164998,"id":"Q1164998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582922$630486F5-0F63-4F54-97EE-40CD506AA6B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e25ef7fedf90d9fadf89c07f9454ea6bbab56df9","datavalue":{"value":{"entity-type":"item","numeric-id":3795250,"id":"Q3795250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d851ef382a1c7ab239a8f0ed0a68f47d6f5de21","datavalue":{"value":{"amount":"+0.816765308380127","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":"Q582922$687ED9A6-3ACD-4E40-8A4E-8998BB321793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62126b7f6f3d3d225a36ebf75df724e1d0dc3b39","datavalue":{"value":{"entity-type":"item","numeric-id":3339312,"id":"Q3339312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af1247be4ba1dfdb4cabb5abf27c259817fd27cd","datavalue":{"value":{"amount":"+0.7992717623710632","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":"Q582922$73C5165B-D2BD-4663-82E3-DDBAB05EF23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e23d192c1ac1ba0773c7261bec44e19f04ae2fed","datavalue":{"value":{"entity-type":"item","numeric-id":3219131,"id":"Q3219131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a96f59d84a2be5a4c4ed844fc2bd2e6350164e32","datavalue":{"value":{"amount":"+0.7992330193519592","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":"Q582922$3E67DE98-F8F9-4F60-86EF-A5F73F22A028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20084fad596255202e2ccbce37f4169923f16c50","datavalue":{"value":{"entity-type":"item","numeric-id":3787517,"id":"Q3787517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"482a02058047fdf6d172749170ca1a9d5e073621","datavalue":{"value":{"amount":"+0.776787519454956","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":"Q582922$3D58A281-ED8A-4A1D-9494-27C035C2A204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4922a9a5d884daa322d06e8aab7c719d78813aeb","datavalue":{"value":{"entity-type":"item","numeric-id":3058070,"id":"Q3058070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9b130cd48b5384ccb2d45b624bdd3d675bd3a52","datavalue":{"value":{"amount":"+0.7735799551010132","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":"Q582922$E5E639C7-4538-4435-9494-F0B575BF6F62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:582922","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:582922"}}}}}