{"entities":{"Q1208437":{"pageid":1219186,"ns":120,"title":"Item:Q1208437","lastrevid":67060395,"modified":"2026-04-12T14:42:04Z","type":"item","id":"Q1208437","labels":{"en":{"language":"en","value":"The pre-NTS property is undecidable for context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166442"}},"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":"Q1208437$CB970632-195F-4EE5-870E-EFB678C0FB27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e30b8be6b0a3b3cf9499fa7e7d74a0d9ba7545c","datavalue":{"value":{"text":"The pre-NTS property is undecidable for context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208437$65342F5A-930D-4B05-A9A0-E8434025F48E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b84bbef96facb37e5246022f8ce135013352eb62","datavalue":{"value":"0779.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$DB395B9B-419D-4293-81F1-A8B3A4B4B5ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef86b9f5486c0a39186144ec27ceb0c5be874cbe","datavalue":{"value":"10.1016/0020-0190(92)90082-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$B60979DB-25B3-45F0-BDF5-9435D2D7AA33","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"25848f77e014c64df3589ed571f746ccf67f4837","datavalue":{"value":{"entity-type":"item","numeric-id":491207,"id":"Q491207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$D21806AE-F657-4B15-8AC2-2732CE9747B2","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":"Q1208437$8C9D5211-896F-4C65-AC94-A8B9D4C653FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208437$8FEBC35F-2A50-4C11-B0A4-866237514F8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b57f8475cafba4d2e993b5add115c79098156987","datavalue":{"value":"A grammar \\(G\\) is called non-terminal separable (NTS) (respectively, pre- NTS) if the set of sentential forms (respectively, the language) it generates is unchanged when the rules in \\(G\\) are used both ways. Such grammars were introduced by \\textit{L. Boasson} and \\textit{G. Senizergues} in [J. Comput. Syst. Sci., 31, 332-342 (1985; Zbl 0604.68087)]. The NTS property is decidable [\\textit{F. Otto}, J. Comput. Syst. Sci. 35, 285-310 (1987; Zbl 0645.03033) and \\textit{G. Senizergues}, J. Comput. Syst. Sci., 31, 303-331 (1985; Zbl 0604.68086)] in polynomial time [\\textit{K. Madlener}, \\textit{P. Narandran}, \\textit{F. Otto} and \\textit{L. Zhang}, Theoret. Comput. Sci. (1993)]. In the present note one proves that the pre-NTS property is undecidable. The use technique is the simulation of a Turing machine through a finite monadic string-rewriting system.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208437$2F329BB8-EF9E-4DD0-8604-5D879FB45FA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$DA135E2A-941A-4AF9-86F1-698DCD7AAB8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$09B77EFB-D97C-4B5A-ABC2-32FC4B611A09","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46f6362133a8fb824de6854209d71aeed753155a","datavalue":{"value":"166442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$661D5EE5-8F14-4CB0-A447-89335362776A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"42210bafdd52b4cbc4a62733feb51d89cc3d12b1","datavalue":{"value":{"entity-type":"item","numeric-id":224640,"id":"Q224640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$E4E13F81-7FEC-49D7-BFE8-3B7FEC41E007","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":"Q1208437$708509F9-A022-4077-B4F0-700874B43D58","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ac78dc5e8101d202ed1fefbd275f4238853ee9d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90082-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1208437$48BB44FB-7CFE-4A3E-BC07-DD5494C035DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"903a53af9c6da78e46463b971d2609c081806e5f","datavalue":{"value":"W2093306186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208437$0667F699-F729-4575-8648-E60016806684","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d70625d03e68e9bedd523a99832313f46c4f29eb","datavalue":{"value":{"entity-type":"item","numeric-id":3992022,"id":"Q3992022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$2C7AD541-D07C-43EF-A56A-CDA1A79410EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef5f103221b565b7727757563d1a2277e9877e25","datavalue":{"value":{"entity-type":"item","numeric-id":1083220,"id":"Q1083220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$F5D4270D-1458-4E24-82D4-77124BFC7F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e004ad7c53d1b6136d8c12b096d8cc2682099b5","datavalue":{"value":{"entity-type":"item","numeric-id":1099642,"id":"Q1099642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$54889B85-BF0F-4E2F-93BF-9600ACC5F4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6db44461333ef5e5aae7abb248658a05e60ef41","datavalue":{"value":{"entity-type":"item","numeric-id":3247126,"id":"Q3247126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$7FFF7CEF-41BC-4843-BAF2-EF1D28702294","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":"Q1208437$2612A548-44C6-4861-BDBA-7274E3442770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3954ee6021d340af94dc9949d1af4ae5484cf91d","datavalue":{"value":{"entity-type":"item","numeric-id":685433,"id":"Q685433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$BDE4D2B2-A8AC-4896-8A0D-3710EE201AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"838963065bf2cb01121d1af54e4aed38f9851f93","datavalue":{"value":{"entity-type":"item","numeric-id":1102946,"id":"Q1102946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$6BD464C9-28D4-432B-A493-5A8814908029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86254ee3c9b6e0d2075cc38ddd7166cbd33df22d","datavalue":{"value":{"entity-type":"item","numeric-id":1083219,"id":"Q1083219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208437$DD31D00B-DD9F-4D38-81D5-B023094F9A72","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3d3db6558f96c45fdbed45e528703684ba23014","datavalue":{"value":{"entity-type":"item","numeric-id":3992022,"id":"Q3992022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d2ba3b8c4d47706994cd3bc44540bb6924f9bcc","datavalue":{"value":{"amount":"+0.7938376665115356","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":"Q1208437$BE56236D-5EC3-41B4-89D3-C03A14775750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"713b678e7059af02808f5598eb3f985cff90cc45","datavalue":{"value":{"entity-type":"item","numeric-id":1083219,"id":"Q1083219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fde97309e89cf12202b791313a585226be6509ec","datavalue":{"value":{"amount":"+0.7918457984924316","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":"Q1208437$8CB50BB8-425E-422B-BF2C-0405482FE8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8b75edfcc155c840ffa69a3361254d623768be0","datavalue":{"value":{"entity-type":"item","numeric-id":5485995,"id":"Q5485995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c35cff138e884409fb74f578e60176ed2d3ef43d","datavalue":{"value":{"amount":"+0.7886302471160889","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":"Q1208437$23CC2A46-1381-4B7E-AA14-BCCC8B62B7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced98fa849948734f36a114df80a977f56481508","datavalue":{"value":{"entity-type":"item","numeric-id":1083220,"id":"Q1083220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da0a445fa6c764435466e989ed6b0a9d9958be8","datavalue":{"value":{"amount":"+0.7630125284194946","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":"Q1208437$D637F996-4CB8-4231-9D27-63A438608404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ebd89fbd3122a1ee3520e5ac2ce6eeec547e73c","datavalue":{"value":{"entity-type":"item","numeric-id":3779771,"id":"Q3779771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34cd130d0617b167fa25eb999e8806fcd043bcef","datavalue":{"value":{"amount":"+0.7456666827201843","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":"Q1208437$3843EAA6-D2F0-429A-B194-F6BAA9829A78","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The pre-NTS property is undecidable for context-free grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_pre-NTS_property_is_undecidable_for_context-free_grammars"}}}}}