{"entities":{"Q685232":{"pageid":687081,"ns":120,"title":"Item:Q685232","lastrevid":47188483,"modified":"2025-12-31T23:08:50Z","type":"item","id":"Q685232","labels":{"en":{"language":"en","value":"An NC algorithm for recognizing tree adjoining languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417143"}},"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":"Q685232$AD277756-9941-45C7-9C2D-23138CAC3BF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e11c85824483c2469cdda09f40ad900808fe9a98","datavalue":{"value":{"text":"An NC algorithm for recognizing tree adjoining languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685232$40F42E3C-6873-4654-BCCA-E7E66688848E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9fa63a19d550c8e088d67cd53c19addbadcb19ec","datavalue":{"value":"0777.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$22626ECC-01BA-4AFA-BB6A-E30EAC9109A4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0f4a83244444c8f93d03b94365428cec766406a","datavalue":{"value":"10.1007/BF01408291","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$A16F2F3C-ED1F-44D6-8212-E8DDCE9E8891","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7691c0b5037162d950224611d7e13014b76238ad","datavalue":{"value":{"entity-type":"item","numeric-id":685083,"id":"Q685083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$3CC34AAB-16D7-491B-BB6C-5DDB68E49189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"90205e3a774164fdfd13bf05bbed3369e69c1232","datavalue":{"value":{"entity-type":"item","numeric-id":293382,"id":"Q293382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$AEB31BBA-0D41-46A7-8FE7-94F5E29EF710","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a32831c4e3f60d79ea2f79afb884ef69e4c8191c","datavalue":{"value":{"entity-type":"item","numeric-id":199286,"id":"Q199286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$3F28AACA-B685-4D55-A32E-4370E38766F3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45eae072dc2fde41ae8741e47d8a8d06eb2b2f63","datavalue":{"value":{"time":"+1993-09-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":"Q685232$D1852445-FB9E-4DE9-8E3E-D4DDADF2ACB9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea4b2a14350c916d72216f2ff19ad6c00fac0428","datavalue":{"value":"The Tree Adjoining Grammar (TAG) is a tree rewriting system that uses the operation called adjunction to compose larger (derived) trees from a finite set of basic (elementary) trees. The authors (and D. S. L. Wei) have shown (1990) that TA languages (TALs) can be recognized by a parallel algorithm running in \\(0(n)\\) time using polynomially many processors. The present paper proves that the TAL recognition problem can be solved by a concurrent-read concurrent-write parallel random-access machine (CRCW PRAM) in \\(0(\\log n)\\) time and using \\(0(n^{12})\\) processors. This result places TALs in the class \\({\\mathcal A}{\\mathcal C}^ 1\\) of languages accepted by an alternating Turing machine in space \\(0(\\log n)\\) and alternation depth \\(0(\\log n)\\), and effectively extends the \\textit{W. L. Ruzzo}'s [Automata, languages and programming, 6th Collow., Graz 1979, Lect. Notes Comput. Sci. 71, 489-497 (1979; Zbl 0409.68024)] results according to which context-free languages belong to \\({\\mathcal A}{\\mathcal C}^ 1\\) too. Investigating the place of TALs within the \\textit{D. J. Weir}'s [Theoret. Comput. Sci. 104, No. 2, 235-261 (1992; Zbl 0754.68070)] Control Language Hierarchy is proposed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685232$D04F1C2D-5108-4254-A02D-06800AF471E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$F26A7CE2-96E8-4F09-AA62-8A5AB756E7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$87FD2726-9761-4BEC-97C6-D2EA2E73D9FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$F7AC439E-DA4F-4C51-870C-97F26E29DF6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$FB0E618E-7220-4796-8CCB-388FA84C6866","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01226c58976b1054d237b2555ed1502913ca2a56","datavalue":{"value":"417143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$A36D36FA-5C4C-40B1-AE77-2E72637FEDA0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b295319b1766732ef1081b934f7e1d8b11425a5","datavalue":{"value":"parallel recognition algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685232$624C95BB-E705-476A-A73E-E4CD5DA21E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee8b57110b3cb878b891083edebfebd2d9f94c6d","datavalue":{"value":"tree adjoining grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q685232$6BAA3391-0C98-46AB-925F-C8146168C45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d473e0855ff6f4b2a405e9d9373d1cb7bf7d7ab","datavalue":{"value":"CRCW","type":"string"},"datatype":"string"},"type":"statement","id":"Q685232$24CF03C9-5463-4BDF-B403-92C64E2471CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q685232$878E8D69-29C6-4B3D-8298-6CEEC387761C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ddfe26001cac27b44f73ee317c958b41c5d4e225","datavalue":{"value":{"entity-type":"item","numeric-id":585901,"id":"Q585901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$2ABDB17A-5151-44FE-9E45-4B0759B95209","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":"Q685232$833DD361-4AB4-422A-BF76-32DA8F8C0B57","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e34b733d5c968f4670211735e85d54b3608649","datavalue":{"value":{"entity-type":"item","numeric-id":1225947,"id":"Q1225947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$E599D31D-98BF-4251-8975-406CB09E05C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84d73eb6590c3d9cf4ea26ff9f4ca49196597a82","datavalue":{"value":{"entity-type":"item","numeric-id":4069798,"id":"Q4069798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$34B27CC8-47DA-467D-8DE9-56AC2F68A3FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afa303320d5a88343403f05f9405bb09143987a2","datavalue":{"value":{"entity-type":"item","numeric-id":3311705,"id":"Q3311705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$F7D159CF-A993-4E0C-B1D5-23486A1C1599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3840b8b27aa0dca47e74213273da44cdc4044bc0","datavalue":{"value":{"entity-type":"item","numeric-id":3773378,"id":"Q3773378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$81F3A3FE-5E84-4782-B981-232FBC031F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$3ADE6A13-D8CE-4182-9F63-A23AAC337B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f450486e6dd81b9bc183a0057d83ff04fd2d4632","datavalue":{"value":{"entity-type":"item","numeric-id":3316595,"id":"Q3316595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$B6371EEA-815D-430B-BC2C-441DB43AE0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$F83B91EB-11DF-45A1-BB4A-F47AE8B8B09F","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":"Q685232$F45618F6-31C1-4DD0-8639-30530BD176ED","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":"Q685232$D79E7C4A-6BDD-47EF-B480-57FBAF526725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e37d3cd89bf56058a2b19db5dd9a0a78bfe825f","datavalue":{"value":{"entity-type":"item","numeric-id":2561843,"id":"Q2561843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$F2CCD393-C6B8-4132-85E5-573FBF3A8A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25841e4569e97f57b92c2988238f132a58e25637","datavalue":{"value":{"entity-type":"item","numeric-id":3911430,"id":"Q3911430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$15A28A4D-299E-4644-BE40-EBEC0C12E99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584e32d8f070a9ec2d1501115d5107dcbb94f797","datavalue":{"value":{"entity-type":"item","numeric-id":3936224,"id":"Q3936224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$768F979C-4C92-4B8B-ADAA-4A5CABA3B474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de1c63dbf03233603e7845154abe241f44642262","datavalue":{"value":{"entity-type":"item","numeric-id":1121034,"id":"Q1121034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$37A55A54-EB5B-4607-BB5C-470D4C94BCC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c69169346621a9e851a15e9b864cb38cd20c8d70","datavalue":{"value":{"entity-type":"item","numeric-id":3474285,"id":"Q3474285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$322DF02C-02CF-4319-9CDE-7CC448979EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2eae652bdca4c7b3a87949ae9467896e54b464f","datavalue":{"value":{"entity-type":"item","numeric-id":1193884,"id":"Q1193884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685232$F51E28AB-FA45-46EC-8B92-EDDA9058B34D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43fbbb972d36ac261c519c40f7549182fe9ffe7f","datavalue":{"value":"https://doi.org/10.1007/bf01408291","type":"string"},"datatype":"url"},"type":"statement","id":"Q685232$AE2D6D36-BD92-4233-AD87-58FEB44657EC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"618a6579a1608112750fd00abfac73b8fdc60072","datavalue":{"value":"W1990102452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685232$EA8869C1-E339-413C-82E0-EC99448BB884","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"043974d7831b0f0f31ec015efc790f2d02032028","datavalue":{"value":{"entity-type":"item","numeric-id":4895833,"id":"Q4895833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60a4d3d4693b80e7f4771b49272f36f80baff1c9","datavalue":{"value":{"amount":"+0.8733327388763428","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":"Q685232$5E6B44A3-3FB2-4E3E-9511-5C5768F0058C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d638056840b55b28b1c7f62f6254b1df784a57f","datavalue":{"value":{"entity-type":"item","numeric-id":1587367,"id":"Q1587367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63b15eca210a302512c78cfc75761ba824ea8849","datavalue":{"value":{"amount":"+0.8728154301643372","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":"Q685232$7044D484-AEE0-4E62-8E90-18009DE0E4E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e0fbbde9b94640fb789f70b0473a9527a6a79ba","datavalue":{"value":{"entity-type":"item","numeric-id":3474285,"id":"Q3474285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2afc22a6b3047c6ab63171041292a2048f0598a","datavalue":{"value":{"amount":"+0.8522158861160278","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":"Q685232$1CD6B6A5-F2D1-40EE-8E08-172F374E6E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d435bbb926063e4963ad853f0ae94ef1d453546d","datavalue":{"value":{"entity-type":"item","numeric-id":685085,"id":"Q685085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8240986684f50050192471d0c2422c36169eb46f","datavalue":{"value":{"amount":"+0.8353726267814636","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":"Q685232$6F3A6E09-6520-43E3-9A70-2C5C731988A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b868ab674c2e58c5a747986cd7c2bb062769d0d","datavalue":{"value":{"entity-type":"item","numeric-id":5897671,"id":"Q5897671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4505c85c2169776bd27deba7cc1e3d6b4e890946","datavalue":{"value":{"amount":"+0.8349807262420654","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":"Q685232$700D944D-3DFE-4C2C-9D42-2D620EE4902B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685232","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685232"}}}}}