{"entities":{"Q1089801":{"pageid":1100553,"ns":120,"title":"Item:Q1089801","lastrevid":69619155,"modified":"2026-04-13T08:14:40Z","type":"item","id":"Q1089801","labels":{"en":{"language":"en","value":"Rational equivalence relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4005623"}},"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":"Q1089801$A61C7A63-6FA1-4DEC-A691-EA4C7660FF15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ebbb268ea63981ba3888d9495fc28802131575f","datavalue":{"value":{"text":"Rational equivalence relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089801$F111C742-C169-4619-A053-5D6EC5E45736","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85640824ad70884e148c36f11d50adab3a0196c7","datavalue":{"value":"0619.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$48252F4E-69B2-4C11-AC44-05464EE726E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"714eed0cdce8ad38db7d22ae625ddb991ee2bc22","datavalue":{"value":"10.1016/0304-3975(86)90132-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$0E08232E-D2AE-4EFB-9A00-93F27D6C7727","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":"Q1089801$D53563A2-14C1-4CCC-8D84-DB7D469EC730","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":"Q1089801$F5D9039F-41BA-4806-9C12-C14286E97DA2","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":"Q1089801$BB8A2F13-A981-4FA5-98A0-97DFF09C6879","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"99bfa52798296a657f5d5ef31ca82606246f6ac6","datavalue":{"value":"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, reflexitivity, 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":"Q1089801$9757FCDE-FED3-4586-9E0A-FE51874C4849","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"02303c61036060136df3f7b7e22c52163746633f","datavalue":{"value":"68Q99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$5D833C0C-9946-4F62-840D-AB465B4505EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"85991e41d5921c9f733fe99d088c198a921df086","datavalue":{"value":"68T99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$1D4A621D-3FA2-4C4E-B763-A1264C230F69","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91b85725acbf150e3b617570ee12689daeb0b006","datavalue":{"value":"4005623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$B04C35DB-EC10-4F00-AD3E-FC948517C405","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f6546d0798bdb508c30d891ada6bce156daa409","datavalue":{"value":"finite transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$605C46DF-4EA4-488C-AB9F-2AE3FA6B5079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebec84e5761866fe252b573630f0adc3969b6623","datavalue":{"value":"containment hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$5B3D497E-2682-4F87-AB00-B18F9EA84A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07cad24a6c815b59643cf5125a8834bb1ac2d3af","datavalue":{"value":"complexity of canonical function computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$1422E859-CD44-49BA-B05A-17869DD79770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99a9c69f6518a51261b9a39ee4677bf840b73850","datavalue":{"value":"class membership decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$D17B8EE6-EAEF-4576-AF4F-A8F79D775A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6e78b557fb4894b45b662b6a24102803003477e","datavalue":{"value":"rational equivalence relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$19BA68F1-4367-45B8-A8CC-8EB0BBED5080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36717f2e071428869286b68cf0dbdfbe64b72820","datavalue":{"value":"equivalence kernels of rational functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$EBF3A710-79EA-43CB-A130-51AEA13E6600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dfdc0b649964d129fa659cd9872eb59f5776da9","datavalue":{"value":"equivalence kernels of subsequential functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$0F897968-08AF-46D6-A7C9-1C67A498EE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6017d8b8431891d25922cbe4dbf90db58fc660de","datavalue":{"value":"recognizable equivalence relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089801$2F415A99-6361-4A31-8C2F-9D69669D7562","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":"Q1089801$6CF34A74-80A7-41A4-9591-28E8874E7B62","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b90edc615bdcba0b5d46b4745dd87a6d5dbb4e7f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90132-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089801$94F7F6F5-4898-48D9-94DE-6639938A885B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6228f11ac0ea34e385fcf6b0660bb013cbc2a51e","datavalue":{"value":"W3102069426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089801$DCB83B07-0E87-42AB-8892-EAD348A2DDAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$D3BB4BD4-A641-4714-B0C0-818AF6DFE4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"869763a444140960d7ec6485edd04e604637d313","datavalue":{"value":{"entity-type":"item","numeric-id":758956,"id":"Q758956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$504480C9-F6C0-432E-87CF-61B000D6B65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"002cdf925f6811f591bec8bc5e91353e7e1aa8e8","datavalue":{"value":{"entity-type":"item","numeric-id":1242878,"id":"Q1242878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$35D7705E-B3CD-4D95-BAC0-20BC5D714ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e84779de69d52c3f3cda23b284ae2de761e42255","datavalue":{"value":{"entity-type":"item","numeric-id":1246508,"id":"Q1246508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$D023B265-8076-45E6-85FF-21EEAB0FFDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$CE5E3B3D-60B7-41B5-96A8-421D5002B2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf8323578f1bc3f7c7f8014c6f09aa7ff9af74a6","datavalue":{"value":{"entity-type":"item","numeric-id":5507511,"id":"Q5507511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$CD4BC00F-DCE8-4030-8118-CDFB749EF41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebc058f2aba4f91fd722c67a0e3cc0416913f43a","datavalue":{"value":{"entity-type":"item","numeric-id":5580840,"id":"Q5580840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$2F9582E4-4574-4CC7-AA9F-F80818CCAE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0006f9acf90b4b0284255798338710e2147e156","datavalue":{"value":{"entity-type":"item","numeric-id":2527943,"id":"Q2527943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$66084008-ACCA-4B12-840F-57D0AE7EE7F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fd1e28e0e6c158c9409c70c379bfcc7c9840573","datavalue":{"value":{"entity-type":"item","numeric-id":5576254,"id":"Q5576254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$CA86D25E-9FE6-44A6-AF78-926A74FA03E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02d4bbee259fe2aa7c072cb07062c3cf93033cd5","datavalue":{"value":{"entity-type":"item","numeric-id":3687745,"id":"Q3687745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$DD5F0CF5-77C2-4D84-9D78-64D8CCDAE870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$222D17BF-7812-438A-A21C-1FDFF9E9C9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc28553cbd079f414114c265d86a94b6ad484595","datavalue":{"value":{"entity-type":"item","numeric-id":1140994,"id":"Q1140994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$FDC3D570-67D6-405C-AF4E-82A23F4B9FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afbd0c5139cd54c5bc85147a9057c45e6c7edee7","datavalue":{"value":{"entity-type":"item","numeric-id":1220392,"id":"Q1220392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$DBAF77FB-925D-4B29-803D-CE0D4137ADC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"313d7fb964ff0b754397abc7f43149589ae35325","datavalue":{"value":{"entity-type":"item","numeric-id":5730513,"id":"Q5730513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$66412D2D-AF8C-40CF-9D69-1DC10EFB8640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8202d424f190fe1882e0fbb3e9c709efe99d7dff","datavalue":{"value":{"entity-type":"item","numeric-id":5527869,"id":"Q5527869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$DFB86421-F5A5-4844-8DE8-0B4E4284A4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e2fab5f38bd4e0e7f1b7e0daec7405d5466dcdd","datavalue":{"value":{"entity-type":"item","numeric-id":1163370,"id":"Q1163370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$6D49E0EC-836A-48EF-BF2C-6DFC70BF8E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b5e638b189d6c8d24c9a66594c224720eba497a","datavalue":{"value":{"entity-type":"item","numeric-id":3962496,"id":"Q3962496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089801$FC72D005-ED7C-4234-A943-54613C3BA782","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1379c514a6eabe6d11730a59779b5c9044b13e4f","datavalue":{"value":{"entity-type":"item","numeric-id":3746906,"id":"Q3746906"},"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":"Q1089801$0B0307B6-EEAD-4D21-A707-A2199A477D6E","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":"4d73b2f7d92ca823574f64b91a2c3e7832507b7d","datavalue":{"value":{"amount":"+0.824090838432312","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":"Q1089801$5F1E365A-CAF6-4848-A2F0-1B2D8E5455A0","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":"2bb46f26bcf593690999bd08360b374390c413b6","datavalue":{"value":{"amount":"+0.8012447357177734","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":"Q1089801$79EF7F15-01FB-4D31-B284-C57482862FFF","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":"c33da7467cffee58d270f1e6295f03d66c9e67a3","datavalue":{"value":{"amount":"+0.8012445569038391","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":"Q1089801$E662D25F-C68B-44BC-A4C5-5971CFF43766","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":"7bed66fe0b9409e1993d6542756368218ab1576b","datavalue":{"value":{"amount":"+0.797920286655426","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":"Q1089801$5DBD3F59-6BAF-4A63-88A0-053C6BF255ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rational equivalence relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rational_equivalence_relations"}}}}}