{"entities":{"Q557813":{"pageid":559580,"ns":120,"title":"Item:Q557813","lastrevid":62730306,"modified":"2026-04-11T08:04:39Z","type":"item","id":"Q557813","labels":{"en":{"language":"en","value":"The generative capacity of block-synchronized context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184049"}},"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":"Q557813$B5FD86DD-F93E-4A79-AA4A-1254FCC11C11","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c4b4710be07a64779382edb896c935fb74b7b66","datavalue":{"value":{"text":"The generative capacity of block-synchronized context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557813$D6C071A2-CD4B-4D5B-B448-C74071145BAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"202846b6692cac2d2bff065d175b16a8de0de050","datavalue":{"value":"1078.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$EC29C69C-CCDB-49B9-AA59-9054E56E3962","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eaf226bed97fcfbb2e029b3cce0c0d7a70c7768b","datavalue":{"value":{"entity-type":"item","numeric-id":265079,"id":"Q265079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$4342B51A-990B-4AEC-B245-0A940E895317","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":"Q557813$AAA8BD05-471D-4E77-9C46-857D2E8B8073","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q557813$22571E5C-21A5-490A-82D8-CCA554EA92CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6af20112ab407c88a3712c892d2986befc454c03","datavalue":{"value":"The author gives an alternate characterization for the family of ET0L languages. So it is proved that the family of ET0L languages coincides with the family of the synchronized context-free languages and with the family of Block-Synchronized Context-Free (BSCF) languages, where the nesting or recursion depth is bounded above by any constant. For this purpose a normal form for BSCF grammars is provide. This result is useful for the study of the ET0L languages as it is often easier to describe a language using a BSCF grammar. By examination of the BSCF grammar it is shown that when the recursion of BSCF grammars can get arbitrarily deep, then the generated language family using two defined types of synchronization is equal to the family of indexed languages. It is proved that BSCF languages are more general than finite nesting depth BSCF using both types of synchronization.","type":"string"},"datatype":"string"},"type":"statement","id":"Q557813$8852FBFB-ABAA-4B64-BA4E-BC3D83AFA47D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"10ce3a5d9313b648d3b16631524f630b08f534db","datavalue":{"value":{"entity-type":"item","numeric-id":587297,"id":"Q587297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$316A8F46-3EBE-460C-B1E3-1A3B51758FC9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$B47411CC-A772-4894-82C0-7F22EE62BE8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$E0696E70-DE1B-4F1E-8214-3204E91721C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"138602d0ad2239e24a6c2e3c48f4b281535f9d55","datavalue":{"value":"2184049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$E0B2E3D0-9E4F-4236-8890-A86A4A2FFAAB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b35308bc75d87a1ef17adf840f6e769e748a711","datavalue":{"value":"ET0L languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q557813$A9BA667F-2165-4E69-891A-F8B925D42093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fa36130e82077da1500a611dfdd0f247e985b15","datavalue":{"value":"synchronization","type":"string"},"datatype":"string"},"type":"statement","id":"Q557813$96E47E15-BC1D-49D5-816F-54217B9DC6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06c8954512017c7bc687623ab7d878c0b6581738","datavalue":{"value":"rewriting systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q557813$2BB4AC9C-C877-468F-B883-88E7A50374DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61aee7617b415fb5aa78fc6567ad0a6d62bd59c4","datavalue":{"value":"indexed languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q557813$7E931C25-8FC2-4D23-B092-996CA06453BC","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":"Q557813$E24D3EFD-EE29-4C00-BC53-68C0370F8CD3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"244a008d44d1f694e7c9f027c1f984081fb3fef9","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.11.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q557813$7020BEC0-B4F7-47A3-93F5-B20F58A8D8F4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6d116adf6bd6d321b2b6d5234f1677bfdc68a11f","datavalue":{"value":"W1994084299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$003EF4D0-A87E-4CFE-8BEE-8F2D284CE06E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1de9637af9a8fedcf8ab07e9c2d71e01bf8c23d8","datavalue":{"value":{"entity-type":"item","numeric-id":5565119,"id":"Q5565119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$0FB05C7B-DDFF-44E4-BD44-8B7B42EC9392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f529da25feb1a9c0ea7a02d64eba2630ed5e397c","datavalue":{"value":{"entity-type":"item","numeric-id":5422229,"id":"Q5422229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$53582CB5-0449-4623-ABD0-595C7A8A1F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b26bd780094637c6ec47f210f792c943e66a6ba","datavalue":{"value":{"entity-type":"item","numeric-id":4819884,"id":"Q4819884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$408493B9-9CA4-4F85-99A8-C2FA84412865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59cc35935d6d1649e48a078b7b6590260d6c4599","datavalue":{"value":{"entity-type":"item","numeric-id":3865515,"id":"Q3865515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$779A9D15-01CC-41AE-AA9A-DFEC72068B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$DF3F2807-C2A9-489D-8218-4A92321FD0C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"390a4c55d81f60fc04de11c79b4bb75544936c5f","datavalue":{"value":{"entity-type":"item","numeric-id":811118,"id":"Q811118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$75615B2C-E7B1-45E7-872D-E88CE8F8DCF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe8eb22dbc43374d7e686376a87836015863f340","datavalue":{"value":{"entity-type":"item","numeric-id":1334670,"id":"Q1334670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$0BD74E5C-1C41-4537-B52E-E2188A7B2645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9bfc9652034dff2951a1622fbcbff94e0d954e5","datavalue":{"value":{"entity-type":"item","numeric-id":4336269,"id":"Q4336269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$476167D0-2EB2-477D-B9C3-718B6D60E6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9500e19069722efa256e9656f8110bdcd87d826","datavalue":{"value":{"entity-type":"item","numeric-id":4140407,"id":"Q4140407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$435A63D8-ED97-44E7-813D-828EAE8393C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fd76c09b405cbfab6abf78494c90379232d25c","datavalue":{"value":{"entity-type":"item","numeric-id":1325832,"id":"Q1325832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557813$241C7EB9-A75D-4BF2-A9C0-050E76CD1BE1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cde1859014b94b358ba73789d26759c3a2109758","datavalue":{"value":"10.1016/J.TCS.2004.11.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557813$FAE4BA6A-1343-478E-877B-E02B304D3B3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b43ea961526f18b88b30d2cc954b3d4a77c9a8c","datavalue":{"value":{"entity-type":"item","numeric-id":4336269,"id":"Q4336269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ca0cd56317f4333809a10b081f038831f29a5ad","datavalue":{"value":{"amount":"+0.834712028503418","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":"Q557813$25EE091E-CD8D-4CFA-B72C-A3D8F31B1E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c854addd66edc2d391ff0ebd9a476206e2a2b7fb","datavalue":{"value":{"entity-type":"item","numeric-id":5313796,"id":"Q5313796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0d27f775f6976ce83573e2950453af5af8f7f93","datavalue":{"value":{"amount":"+0.8166671991348267","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":"Q557813$FD59F84E-F104-41B1-B8B8-528FB1274406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d94bdd0f526aed0b0fbc9e820bb2cb6d282929e","datavalue":{"value":{"entity-type":"item","numeric-id":596320,"id":"Q596320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d17f32b072b130b783d451aba1740f3bab80841","datavalue":{"value":{"amount":"+0.7811225056648254","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":"Q557813$9564A5E5-185F-45E0-9163-ADF164B78E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9297213830bc8419529e5a233afae659e3eb51f","datavalue":{"value":{"entity-type":"item","numeric-id":2465043,"id":"Q2465043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1bd3519d14658ac2a2c751caf76b148c423e80c","datavalue":{"value":{"amount":"+0.778796911239624","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":"Q557813$9EB878D4-C5BA-42B1-A19B-267BA65910F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25eef29269e4c228603f73b29a8f32c76aa167e5","datavalue":{"value":{"entity-type":"item","numeric-id":5716613,"id":"Q5716613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3052adf4e1395753e14e6f16897513caa083501","datavalue":{"value":{"amount":"+0.7763023376464844","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":"Q557813$08B60528-5C2C-4FFC-A079-3884A0079D43","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The generative capacity of block-synchronized context-free grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_generative_capacity_of_block-synchronized_context-free_grammars"}}}}}