{"entities":{"Q4598264":{"pageid":6627849,"ns":120,"title":"Item:Q4598264","lastrevid":52981187,"modified":"2026-01-23T23:16:31Z","type":"item","id":"Q4598264","labels":{"en":{"language":"en","value":"On the complexity of grammar-based compression over fixed alphabets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6820311"}},"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":"Q4598264$DDB1B41E-BEE2-4BEE-AEEC-2380D1D38275","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"297e7ed79c4e96e2c6362ba8c93cc5727a79b826","datavalue":{"value":"1388.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$AB9E7D86-3107-4C23-9B6F-D82CA70CCF8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"22306bcf9037bcfa74f463c9c6ef58ee88236c85","datavalue":{"value":{"entity-type":"item","numeric-id":722538,"id":"Q722538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4598264$FD85DC35-3D58-42F9-8212-F3E5913A4828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c96ef73c369ca8e5140b0078dcc58552f1cd31a8","datavalue":{"value":{"entity-type":"item","numeric-id":198229,"id":"Q198229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4598264$D16FB4FD-F343-4AD9-A6F7-737395C5FA79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d39d34d441301ee331df563118867001b2e50da","datavalue":{"value":{"entity-type":"item","numeric-id":247181,"id":"Q247181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4598264$4394F2E4-0B96-414E-B902-D2701E0ACA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b07b2dedfe5d6469e02ac615722a907f622643b0","datavalue":{"value":{"entity-type":"item","numeric-id":1979447,"id":"Q1979447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4598264$7C30162C-BD8D-480A-B89A-05AA8400FF84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08bd73b8f826c8dbdeb6470e2a97e95c375ab926","datavalue":{"value":{"entity-type":"item","numeric-id":315523,"id":"Q315523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4598264$F116ED8B-E45A-4DD0-A53F-D5B0DB304DB4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9fc61ce6e2abfbe9b4163dface0a2d1eb319125c","datavalue":{"value":{"time":"+2017-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4598264$37CF14AF-30A4-456D-A72B-BDAA53E2D410","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$904ED897-8A4A-494D-B250-49F29D8C574A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$84D409DF-2405-4D2A-8205-C5213FF6C69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$DB0C4963-3D30-4661-A07D-F00077894C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$6E28C9CA-078B-4952-8120-E9BD354C1153","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7878bcbbc4c8f3e45c20a1d0f3517e2e39671ba9","datavalue":{"value":"6820311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$61CA193C-8B4C-4B6D-82EA-5B1DEAF58251","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f09b5231d1500a63c98fde88b36502be9956a155","datavalue":{"value":"grammar-based compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q4598264$817C6777-7AF1-4D3F-9854-D6158B47C346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8acef8c5412877d7ff45210ae9d119deab5ead4b","datavalue":{"value":"straight-line programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4598264$9124DBC8-8A6C-4A01-9B26-D800366C166C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4598264$329E0A09-8147-4328-BCA3-9F920A4914E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48c59b36744d1a1aa635bb6b8c026af71b31bafd","datavalue":{"value":"exact exponential time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4598264$AF8F8212-9A67-4513-AEE4-378D2646B61D","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":"Q4598264$D1127AA5-C7E8-4289-81A6-D57BCC535248","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8fd5b984087d5e8596d01dd74e51b1b6daa23262","datavalue":{"value":"https://doi.org/10.4230/LIPIcs.ICALP.2016.122","type":"string"},"datatype":"url"},"type":"statement","id":"Q4598264$67DC0666-D92C-4A52-A1CB-A2AC34779685","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1a9010b1ed2ed605c68597cf403f499d59949d33","datavalue":{"value":"W2538584224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$D0FF2277-D679-4CF7-B993-4B2614BBBEF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2afde8c09be285fe136fbf094e7705c299bf5f03","datavalue":{"value":{"text":"On the Complexity of Grammar-Based Compression over Fixed Alphabets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4598264$95827FC3-2353-4180-971A-66DEE5735C0A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"803c3903e3055d0535bbd3fc6a6b319a3b712928","datavalue":{"value":"10.4230/LIPICS.ICALP.2016.122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4598264$FAFADA63-DD6B-4F06-B8B8-DBCD7365AA25","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38f66834e0d815d0c04c2cae986775359302216a","datavalue":{"value":{"entity-type":"item","numeric-id":2035481,"id":"Q2035481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc3806fb5227afe8c2748beb5805ab7c447573fe","datavalue":{"value":{"amount":"+0.9028430581092834","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":"Q4598264$CAE217E7-AF90-4872-BA47-E0664A31F4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e7bab5503195384aa77abbb8581ba285def1a9d","datavalue":{"value":{"entity-type":"item","numeric-id":3546682,"id":"Q3546682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"856a109a8c23bd31ec7cabf99396622e7ecf57f9","datavalue":{"value":{"amount":"+0.8149738311767578","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":"Q4598264$71400C5C-6697-4B85-8CA6-B889CE1B5DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58dcd38238148a1554b1eeb16fb31465ab636fcf","datavalue":{"value":{"entity-type":"item","numeric-id":4828933,"id":"Q4828933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bb0547becf3f4f830718fa4e9cc48cddf99c403","datavalue":{"value":{"amount":"+0.8062867522239685","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":"Q4598264$5CBF7FC3-11D8-4446-81D6-FD19141E9F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a46d1ab80192cd269001e813631804fc11a5c14","datavalue":{"value":{"entity-type":"item","numeric-id":1796825,"id":"Q1796825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a22193cc822d3e21ce1d0536a5786aa970cf3f6","datavalue":{"value":{"amount":"+0.7926161885261536","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":"Q4598264$5CD8B05A-88F8-4AC0-B63E-F65E87C06100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e9123c92b0f90ddd31d5e9dd2ce48e606269c72","datavalue":{"value":{"entity-type":"item","numeric-id":5393963,"id":"Q5393963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58f86d432a4022662c731506ee69ab864055b021","datavalue":{"value":{"amount":"+0.7811205983161926","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":"Q4598264$469025D4-F817-4982-9ABE-5D852D02FB08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4598264","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4598264"}}}}}