{"entities":{"Q796994":{"pageid":798842,"ns":120,"title":"Item:Q796994","lastrevid":48728305,"modified":"2026-01-05T17:43:23Z","type":"item","id":"Q796994","labels":{"en":{"language":"en","value":"Insertion languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3866596"}},"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":"Q796994$F0EC5B77-4AFF-4705-9D94-F165C7886DC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65c98b454a7ee22845f9525123239d92f6fd3672","datavalue":{"value":{"text":"Insertion languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q796994$ECF69196-9C1A-441E-B9CC-6F61EAA8F7BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"234699f6903d7ce5b48d32c08a6df7a34167535f","datavalue":{"value":"0544.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$673124EF-EB43-489D-B5DC-2BF8E7C10C2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"636ae0968cd6241a8dc7a94ac51ae207eb328915","datavalue":{"value":"10.1016/0020-0255(83)90023-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$B5C1D657-A9FF-45F0-BE53-69416AEECBBC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd2d3ae090b22c3a641be4fedb72aeccd09f0d74","datavalue":{"value":{"entity-type":"item","numeric-id":676241,"id":"Q676241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$04442282-BC35-477A-91B0-46C46DD61D7B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$DF1EF4DA-2E19-438A-B3E8-121E6B68C1FC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q796994$F9B53123-B198-4E24-8EA6-A5AD3B743529","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01e290f2168ea1f0d18285270f803dd26558d3b6","datavalue":{"value":"The operations of insertion (\\(\\leftarrow)\\) and iterated insertion (\\(\\leftarrow *)\\) are variants of Kleene's operations \\(\\cdot\\) and *. For languages S and T, \\(S\\leftarrow T=\\{xzy:xy\\in S\\quad and\\quad z\\in T\\}\\) and \\(S\\leftarrow *=\\{\\lambda \\}\\cup S\\cup S\\leftarrow S\\cup...\\) (where \\(\\lambda\\) is the empty word). The class of languages of the form \\(S\\leftarrow *\\) for finite S forms a class of generalized Dyck languages. The problems of equivalence, ambiguity and determinism are investigated for this class and all are shown to be decidable. On the other hand, it is shown that the problem \\(''S\\leftarrow *T\\leftarrow *=\\{\\lambda \\}?''\\) is undecidable for finite unambiguous S and T. By extending the regular expressions to include the operations \\(\\leftarrow\\) and \\(\\leftarrow *\\), the class of insertion languages is obtained, which includes both the regular languages and the Dyck languages, but is properly contained in the class of context-free languages. It is shown that the problem \\(''L=\\Sigma *?''\\) is undecidable for the class of insertion languages. From this it follows that the equivalence problem and the problem ''Is L regular?'' are also undecidable for this class.","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$768BB766-5375-43FD-B3E4-F072E23F32DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$7473B9B2-1682-4206-9372-88113935940A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$F0B0675C-24A7-478A-A1EA-63273E08E229","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a31445a31902d2ea7a27be290b156f3166027c4e","datavalue":{"value":"3866596","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$1C975275-23F7-4DC2-9094-53474875FA00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6dbf42bc269958acea2d313f6db5c034566a53b","datavalue":{"value":"Church-Rosser systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$5AC01A95-D0D8-4FC6-94B8-DEA1267F36BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba259c5c06af63100955fccf8bc8b370e89eaee","datavalue":{"value":"word problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$B166555A-5B71-4C38-9C57-F5B8A343BB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d61e3ecf85b1ea88b5f1269e3eeef6d011374858","datavalue":{"value":"generalized Dyck languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$A4D68104-5D75-4F82-AF1E-8BC46AB2F237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f080b22ac194cf7585a56b63883129b1a17549b","datavalue":{"value":"equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$8627A5AB-94D8-455F-8C72-35A594AC4808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dece2b67a16f221be015e3ceddb4de928543fdd9","datavalue":{"value":"ambiguity","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$0E8D3CF0-2C37-4E10-9756-A04895D01207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ba6d968a7617d9b56b80603a9b30974da2b918","datavalue":{"value":"determinism","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$74B70156-F154-4539-9FA1-B742ACCA758B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb8d04c869a7c957a2fb637bf61f6c6b39fe9a39","datavalue":{"value":"regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$61709DA5-2F4C-4643-9976-799F2FC32424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeab236f81910da0b085e9e81ab53b2b26e54103","datavalue":{"value":"insertion languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$3C066C57-7C03-4197-A2C1-F5B7A40E30F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q796994$9301F86D-1305-4BF0-8871-8CB161BAE0F8","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":"Q796994$3643AC22-A6D1-4AF2-AA13-3D4D0E1D7EE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c68a1901ba2072fdc21baadc144655b7a04aa3c","datavalue":{"value":"https://doi.org/10.1016/0020-0255(83)90023-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q796994$7215783E-5D57-439D-BAD8-AA4B1CEB61D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68fe79cb446393a94a9260379f7303ac6d37a452","datavalue":{"value":"W2914627413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q796994$A2A44B06-485B-464A-BBF6-D0CF3C4A546D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f8caa4d24218ecf63bb6d39ed1b79a4c2266ea","datavalue":{"value":{"entity-type":"item","numeric-id":3936184,"id":"Q3936184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$D31095FC-B7C7-4DC2-8BBB-3A0006DC53AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9266185c52f53bc308d9e6b943b26d08e91281f9","datavalue":{"value":{"entity-type":"item","numeric-id":5526125,"id":"Q5526125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$89D10432-AB24-4FC9-BDC5-5482DA6E33BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"331367f61f62dfbf3d5531c3feeaa5805c78d071","datavalue":{"value":{"entity-type":"item","numeric-id":4195154,"id":"Q4195154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$4C752831-A8D3-43D4-B769-2C1542B72134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f3bce65c153f53b67aafc08e73839b95059249d","datavalue":{"value":{"entity-type":"item","numeric-id":2545845,"id":"Q2545845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$61FC45E3-3953-4412-9C01-70022F940F8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5426167c36bf53d870bf29cf50b30925d1c9562","datavalue":{"value":{"entity-type":"item","numeric-id":759489,"id":"Q759489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$EC34813A-C5AA-449F-9022-E3EE379C7D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ac9e6b5b6cf386d5e282046ca2407a9abb9a6ff","datavalue":{"value":{"entity-type":"item","numeric-id":5538917,"id":"Q5538917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$EB78465B-CE89-4165-B027-EA841FFB9716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7611f414082b6c08ca61487dcf567f25a0b92b1e","datavalue":{"value":{"entity-type":"item","numeric-id":5581626,"id":"Q5581626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$07204177-8B38-457F-9623-477C60AC0711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca7c153530e221d0b95b7a9e34d31c9f29f2db23","datavalue":{"value":{"entity-type":"item","numeric-id":2549240,"id":"Q2549240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$DD354F0F-7266-485A-AA9E-6D86CE608AD7","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":"Q796994$737E480C-4F33-4A00-B6BE-833A6BB4866F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f256b121b5960183092d61923f4090ee7435150d","datavalue":{"value":{"entity-type":"item","numeric-id":1161057,"id":"Q1161057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$2F5BF1AB-F988-46B8-9A5A-49FED3F00E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd15a6dc8ba82abdfc9beba774819ed68b520dfb","datavalue":{"value":{"entity-type":"item","numeric-id":760799,"id":"Q760799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$2F7C2026-C61B-424E-8C3B-D01A0CE43338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7324b141ea5625401168b593bfa74d985d7e17fe","datavalue":{"value":{"entity-type":"item","numeric-id":5597529,"id":"Q5597529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$47DF690B-E123-4BC2-AA35-7E6FC769FF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"914ef8719678eb4ee59028ba65b4741c8aa1bc8e","datavalue":{"value":{"entity-type":"item","numeric-id":4124327,"id":"Q4124327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$01904310-3B9B-44B5-BAF4-4B19DF8AFED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224fe5205d72f8b7bf3d1117c14acd86046e588d","datavalue":{"value":{"entity-type":"item","numeric-id":2652528,"id":"Q2652528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$FB89A0E6-919F-4668-8B52-1819C2312CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e146e1a73572c015ee99d18dfefc4f34fddc2d1c","datavalue":{"value":{"entity-type":"item","numeric-id":1839248,"id":"Q1839248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$A1A69CD7-4659-4F3A-87CA-D2C7F10362A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29a8d14eae1fab181499f44d4720082adebedfb9","datavalue":{"value":{"entity-type":"item","numeric-id":5845383,"id":"Q5845383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$77B399B6-96D0-4905-ACBC-D5B54940DB87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"772f87ba3e7740ae6776edfd60ece7f44323e97f","datavalue":{"value":{"entity-type":"item","numeric-id":2529464,"id":"Q2529464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$872F90DB-D8AA-4610-9ECA-362DE6500BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3e79c1198a5adad0b28f20fcd66d4c98012ceb6","datavalue":{"value":{"entity-type":"item","numeric-id":4162475,"id":"Q4162475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q796994$98006E0C-57D8-41AE-BA09-DC88D208CF51","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26768db05db55bc3519b88582f945825574a5f7b","datavalue":{"value":{"entity-type":"item","numeric-id":3142559,"id":"Q3142559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"615da012597d718b13b8c7a89c9ec6e4c93d20e9","datavalue":{"value":{"amount":"+0.837517261505127","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":"Q796994$A6B35BFD-772D-4B1D-B39B-0EA0C2EA70AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cad953be7f6205a67fc361c9cd77bb10e6ecc4b3","datavalue":{"value":{"entity-type":"item","numeric-id":1275078,"id":"Q1275078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfd11cad52bee6ee9a518b8d8bd8df105d9eae5b","datavalue":{"value":{"amount":"+0.8318015933036804","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":"Q796994$0A1BB304-BC77-414A-8AB1-8AB65F792BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9b7ac172653e3fe6da6e03dfb9193f82ed67c8","datavalue":{"value":{"entity-type":"item","numeric-id":5901835,"id":"Q5901835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3a6046c5fcb6547c843bcc2af9fae205e6ca4e3","datavalue":{"value":{"amount":"+0.811786949634552","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":"Q796994$EC0C1EE4-EAAD-4D3A-8EBD-22B9F85F842E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39e9e78b150f6f38c20defd635f4d5d945fd3a7e","datavalue":{"value":{"entity-type":"item","numeric-id":1391134,"id":"Q1391134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f92aff432a3d50498f9e06cbcff1ec84c0b32bf5","datavalue":{"value":{"amount":"+0.7965906858444214","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":"Q796994$9FB846E7-E53A-4BF2-83E7-16A89D6E2CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ea331878c4231702a8a9e8a7fdf53e78e811adc","datavalue":{"value":{"entity-type":"item","numeric-id":4862850,"id":"Q4862850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"259704a560e01df9c1306c8d9228334015c9cf8b","datavalue":{"value":{"amount":"+0.7906326651573181","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":"Q796994$6653705B-3537-4034-A3BC-065B5992F72D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:796994","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:796994"}}}}}