{"entities":{"Q3746906":{"pageid":5776812,"ns":120,"title":"Item:Q3746906","lastrevid":110583731,"modified":"2026-11-18T14:08:53Z","type":"item","id":"Q3746906","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3982545"}},"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":"Q3746906$F59606E5-67B7-47AC-B8D0-F9CD406C1AA1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6059486243d6b416d7f0548ef3fb99d85d7dd8ac","datavalue":{"value":"0607.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3746906$EC138C02-51BA-40C9-A511-08528FE6863A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"89e0704561b566de318a1500a02bd85085f03cc5","datavalue":{"value":{"entity-type":"item","numeric-id":1089800,"id":"Q1089800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3746906$60601DF7-D096-4488-81E2-9E983B153F6A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q3746906$64E33DAE-5381-4D80-8E14-6530A6097B2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3746906$65A667C3-FB2E-415A-B4CD-B379A0CB9D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3746906$D6DCD314-BDE0-4400-ACD0-B83B86742175","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e11c6ce3caffc50d2ab818806e4fb25f91816bbe","datavalue":{"value":"3982545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3746906$B1E31C1F-D6B2-469D-A734-FF6F721F6277","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0f692094f245d640e292a477a7b0b3716fb197a","datavalue":{"value":"Rational relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$93F9303F-5342-416C-86A7-B6E6EC9DC7B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f6546d0798bdb508c30d891ada6bce156daa409","datavalue":{"value":"finite transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$3D180851-D258-479B-A642-29FCF105F841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebec84e5761866fe252b573630f0adc3969b6623","datavalue":{"value":"containment hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$ADC055A6-4816-4E60-A098-919444D1B69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07cad24a6c815b59643cf5125a8834bb1ac2d3af","datavalue":{"value":"complexity of canonical function computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$510D5A59-9951-4215-98C8-FA40ECD2FCEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99a9c69f6518a51261b9a39ee4677bf840b73850","datavalue":{"value":"class membership decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$D0244266-230D-4CA6-987A-51AB0EFE6A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86a99a541253e6444c57d9140c6e8791db9df9c7","datavalue":{"value":"rational functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$35E54525-45F1-4295-A265-3C2ABFFF27B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73d767ca49c555611029aa0f2750695876f18787","datavalue":{"value":"subsequential functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$B8810157-E6B2-4F92-A39E-7578AC7A6C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af7ac195094d91d6d8a53720002113cc7316fe5f","datavalue":{"value":"Hasse diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$4B5F7203-ADF7-4514-A37D-4B284F1C6C94","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":"Q3746906$9B1B9D7B-B507-4FA5-B4F0-99EE5414EA4E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7c5b41bdba30ca8541b2142b19a4d704f7f58a9","datavalue":{"value":{"entity-type":"item","numeric-id":1089801,"id":"Q1089801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4cdea7829672ecc4155dc4706325b60b5acf2c6","datavalue":{"value":{"amount":"+0.9994937777519226","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":"Q3746906$359809F3-1F43-4C4E-966D-8F6736F95602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c8d1f7e4ef5ca37cc3ed1c18fadaf684155a8b8","datavalue":{"value":{"entity-type":"item","numeric-id":3687745,"id":"Q3687745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f70657f1f0def3a6808e9aff8f443c18239382d","datavalue":{"value":{"amount":"+0.8236278891563416","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":"Q3746906$16CA1A24-A36F-481B-B88E-6AC8A4366618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da717d4be4dd30c378acd3eb55913c3a864d1ffd","datavalue":{"value":{"entity-type":"item","numeric-id":1679989,"id":"Q1679989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b4fbc4d573e7cbc82ad29f7d452d53baa3daa64","datavalue":{"value":{"amount":"+0.7980107069015503","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":"Q3746906$AB62AA92-C376-45E5-BC4D-1A18F9213024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcd6d9a9d64817a7b0edd88dd6e7f145fd04ebd5","datavalue":{"value":{"entity-type":"item","numeric-id":5377226,"id":"Q5377226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90ce2da450d5ea3d00b11f5d71ddc1f9947538f4","datavalue":{"value":{"amount":"+0.7980105876922607","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":"Q3746906$8DCA29E3-E338-4A82-A138-57A915FF574D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1736917c1d0d28db342fd7b8c7fe5c267a124ced","datavalue":{"value":{"entity-type":"item","numeric-id":1390853,"id":"Q1390853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bd1b9bc1d972beecc4ef4304fa1ead25bca8723","datavalue":{"value":{"amount":"+0.7961345314979553","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":"Q3746906$447A0DB1-27E6-41A5-BC97-A4AB2DF20169","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a6fbb2bcbdf4a624c2e40f85090b0b2c01554bf7","datavalue":{"value":"[For the entire collection see Zbl 0587.00019.] Rational relations (finite transductions) which are equivalence relations are discussed. After establishing a containment hierarchy, the complexity of canonical function computation and a number of class membership decision problems are studied. The following classes are considered: (1) Rational equivalence relations, (2) Equivalence kernels of rational functions, (3) Deterministic rational equivalence relations, (4) Equivalence kernels of subsequential functions, (5) Recognizable equivalence relations, (6) Length-bounded rational equivalence relations, and (7) Finite equivalence relations. Except for one open case \\(((1)=(2)?)\\), Hasse diagrams are given to show the relative containments in the general and one-letter-alphabet cases. Canonical function application for an input of length n is shown to be \\(O(n^ 2)\\) time and space for (1), O(n) time and space for (2), (3), and (6), and O(n) time and constant space for the others. It is shown that transitivity, symmetry, reflexivity, and membership in any of (1) through (5) are undecidable properties for rational relations whereas membership in (6) or (7) is decidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3746906$0BC0F199-B4F3-4B51-8A0B-D20C18FFAC5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3746906","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3746906"}}}}}