{"entities":{"Q800102":{"pageid":801950,"ns":120,"title":"Item:Q800102","lastrevid":64432071,"modified":"2026-04-11T19:50:08Z","type":"item","id":"Q800102","labels":{"en":{"language":"en","value":"On a family of L languages resulting from systolic tree automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3876635"}},"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":"Q800102$5857D83B-8592-4626-B73E-EF86DF6829B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ebe4e49c90307db211c7526f4be07e8c3800ce9","datavalue":{"value":{"text":"On a family of L languages resulting from systolic tree automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800102$3F28551C-415C-4548-9452-3E7B45CD44F5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9365e4a79448a2d3c3d7877760b1b133e1f7135f","datavalue":{"value":"0549.68081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800102$AA247178-3449-4E43-8E97-C9AFC692D23F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e3dbd8d9202ccec4d133c9b93405b01a79fdd87e","datavalue":{"value":"10.1016/0304-3975(83)90032-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800102$E5A3A7D9-BD1D-48AF-8EFA-50F57C46957A","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":"Q800102$2EA798C5-C0DA-4E99-B92D-0903E7B7BD3E","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":"Q800102$1602B971-0E6A-4B63-ACFE-870F0AB23E4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eadecb3dd4c0ade391ca3458b377f536b3b7073a","datavalue":{"value":"The class of BT-VLSI languages accepted by binary systolic tree automata contains all rational languages, is closed under Boolean operations, and the equivalence problem is decidable. This paper shows that every BT-VLSI language is an EOL language. In order to describe the relationship between these two classes the notion of a semibinary EOL language is introduced. Every EOL language is the coding of a semibinary EOL language, and an EOL language belongs to BT-VLSI if it is a coding of a semibinary suffix EOL language. On the other hand, the emptiness problem for the class of T-VLSI languages, i.e. the languages accepted by general systolic tree automata, can be reduced to two well-known open problems about \\({\\mathbb{Z}}\\)-rational formal power series. In particular it remains open whether an arbitrary T-VLSI language is an EOL language.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$60F15D47-0910-483B-A0D9-109B245E9DF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800102$E946F945-4CA7-434D-9232-5048C689AC3E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0f5777e64c1401b25e9037432d7273dc7e2edfb","datavalue":{"value":"3876635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800102$41103F17-48A0-4948-97BF-486112A2B42C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40c783dc39fea7d1eeb1801d6569ab809080c65a","datavalue":{"value":"BT-VLSI languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$C33D94D9-D662-4B1E-A99F-4D8DFD4AA91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebc269af3e3d8db8ca2acde27bd08e82547951a9","datavalue":{"value":"systolic tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$B2D3F998-7F78-4033-9197-333B1AEF3CB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb9fbf64869c0dc144158a704b9ea809e41e41c","datavalue":{"value":"EOL language","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$EABC55A0-3833-4077-9708-481A5282ADBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9159d4f959d21ef7c3c5f2d36ede4144c26f9c","datavalue":{"value":"emptiness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$118110BD-95DD-4B3F-B472-4EBB458E5349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3590eb8b47f26c41d61639b5166afe44752133e","datavalue":{"value":"formal power series","type":"string"},"datatype":"string"},"type":"statement","id":"Q800102$61ADBCC8-4FAF-4742-A82C-D9DC223B8411","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"87b50d9d925c1d915b90d3836e3c8221c58fe283","datavalue":{"value":{"entity-type":"item","numeric-id":582130,"id":"Q582130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$771BCB51-B95E-4466-AD37-CF72A37175BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1387b7bf165216c9c9eccef78be3e60fd288932","datavalue":{"value":{"entity-type":"item","numeric-id":391187,"id":"Q391187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$D95EE5A8-543B-4C3B-BBD9-F5F4F307DBBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f58f3719f2f81c417cf620530e45b407dd1c4f1c","datavalue":{"value":{"entity-type":"item","numeric-id":235701,"id":"Q235701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$6390553D-A164-4554-BC02-85D107193D8B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ca416a4f32a5ebb514841c06408c038c8e3d1d2","datavalue":{"value":{"entity-type":"item","numeric-id":587388,"id":"Q587388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$9611F50C-FC38-4EF6-9321-58BCCFFD5D0D","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":"Q800102$E426575B-7E9B-4336-9F82-6F29CE1E3B85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"111e345d5ffcb3c6b89a3bfb64acc0acc2a80e8c","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90032-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q800102$62D889EC-AE69-46C4-B7DB-CDABE91D2F31","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3fa9b0e3ec2a2f7319b31d84cc6d3a1647c05b5e","datavalue":{"value":"W2081564114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800102$CD04E585-79F4-4CD3-91FB-933982D7FCE6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c34fcea28c03347d3a8fb669640a66d8a159df49","datavalue":{"value":{"entity-type":"item","numeric-id":4047115,"id":"Q4047115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$6E9A43DD-4DE8-4B9C-B001-25B34B822741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8001a5615e3f4fe974a4d5d59e09f623287067","datavalue":{"value":{"entity-type":"item","numeric-id":3687723,"id":"Q3687723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$B070FA5A-02E3-4CF2-AC85-0A9A3AD911C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f174e5eb3103f889bc208312e4071066863a13","datavalue":{"value":{"entity-type":"item","numeric-id":1168737,"id":"Q1168737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$12C605EB-6EAB-40CA-AA15-2E85657FFD13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c98831f9b7250294c09452bd79ac875a9272414","datavalue":{"value":{"entity-type":"item","numeric-id":4068111,"id":"Q4068111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$2A3C2857-950F-4562-A3EE-7367CD9EDD40","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":"Q800102$F0F5AB3B-95E0-474E-A15B-7BFBD8703FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb6290412741acf231ec58be371ffd9c5ecc534","datavalue":{"value":{"entity-type":"item","numeric-id":4155837,"id":"Q4155837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800102$A273A93B-798E-4239-B7BE-AA12C189BF1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0d51a5e2a996d93ffab3a5b7d6dc7993947a5fc","datavalue":{"value":{"entity-type":"item","numeric-id":3687724,"id":"Q3687724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da58cc670cfd596f7bbd925792a8b753e3186719","datavalue":{"value":{"amount":"+0.7784824371337891","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":"Q800102$8824D2D2-1DBA-4AD3-B226-FA34AE45628B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"517610768adf731d843235df920090cf4af292db","datavalue":{"value":{"entity-type":"item","numeric-id":1102750,"id":"Q1102750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f3a5929304eecb566d909f1c28a18ebf476ce76","datavalue":{"value":{"amount":"+0.7717307806015015","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":"Q800102$9764A8B5-8356-45C8-8882-87A7BD50780F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b611ba642443e9306c9345f41ea8c6ebe7f0efc","datavalue":{"value":{"entity-type":"item","numeric-id":3792261,"id":"Q3792261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b40c9b8c371e755cbfd78f5149e44949c816b1","datavalue":{"value":{"amount":"+0.770445704460144","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":"Q800102$B8712923-19C0-4E3A-A9C5-230EEB25C350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646ec14c566394f5f586a4492c0e49832a401527","datavalue":{"value":{"entity-type":"item","numeric-id":2277854,"id":"Q2277854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9686092f530c4668eff017b9170e7aeb230169c8","datavalue":{"value":{"amount":"+0.7700802683830261","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":"Q800102$13FC9E25-7935-402D-B6B2-D55757D5C29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5578f51d7b948ed4ace859038fe7467118f8bcf8","datavalue":{"value":{"entity-type":"item","numeric-id":4596616,"id":"Q4596616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6622fa2a49b15d03eabe563f8731808032800339","datavalue":{"value":{"amount":"+0.7694556713104248","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":"Q800102$C4B18120-A7AC-4AAA-87B2-94A98FB99C74","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a family of L languages resulting from systolic tree automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_family_of_L_languages_resulting_from_systolic_tree_automata"}}}}}