{"entities":{"Q1087020":{"pageid":1097772,"ns":120,"title":"Item:Q1087020","lastrevid":69928812,"modified":"2026-04-13T11:16:47Z","type":"item","id":"Q1087020","labels":{"en":{"language":"en","value":"Syst\u00e8mes entiers d'\u00e9quations sur un alphabet fini et conjecture d'Ehrenfeucht"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3986660"}},"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":"Q1087020$2972F80A-C397-4BBB-9013-D0D1AF1DFC40","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12df1ad40b32361553f47f3b83f451e949afd2d5","datavalue":{"value":{"text":"Syst\u00e8mes entiers d'\u00e9quations sur un alphabet fini et conjecture d'Ehrenfeucht","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1087020$1AB6D12F-2A6B-4B40-B00C-C921CE26B331","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e4e51e122e6e331e0223c755ab5f7f053a2a994e","datavalue":{"value":"0609.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$7F22C1DC-26C8-4080-A79D-161DDB8CAD11","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ad85958fb9faba696c859284ad2d95a2a984341","datavalue":{"value":"10.1016/0304-3975(85)90137-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$CF1C8310-4784-48DC-BF68-B2BC1AF77905","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d7f3590118c34ae6ec473d05c445e2e90f9883b","datavalue":{"value":{"entity-type":"item","numeric-id":580993,"id":"Q580993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$44958AFF-9D3A-4D9C-B525-6321174225EC","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":"Q1087020$946459A7-912E-4055-84A5-6D798805CC47","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1087020$86C4E0C5-3313-4B2C-BBE8-9AB4526FDA65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1643a5948e6039e0492780e2af21a1de4d5b9d8c","datavalue":{"value":"A system S of equations over an alphabet \\(\\Sigma\\) is called entire if \\(S=\\alpha^{-1}\\circ \\alpha\\) for some morphism \\(\\alpha\\) of \\(\\Sigma^*\\) into a free monoid. For each morphism \\(\\alpha\\) as above with finite \\(\\Sigma\\) and \\(\\alpha^{-1}(1)=\\{1\\}^ a \\)''shuffle automaton'' \\({\\mathcal U}(\\alpha)\\) is introduced, which recognizes a rational language K(\\(\\alpha)\\) over some alphabet \\(\\Delta\\) such that \\(\\alpha^{-1}\\circ \\alpha =\\{(\\lambda (x),\\mu (x))|\\) \\(x\\in K(\\alpha)\\}\\) for certain morphisms \\(\\lambda\\), \\(\\mu\\) of \\(\\Delta^*\\) into \\(\\Sigma^*\\). From a theorem of Nivat (characterization of rational relations) it follows that all entire systems over a finite alphabet are rational. The relation of these notions withthe Ehrenfeucht conjecture (recently solved by \\textit{M. H. Albert} and \\textit{J. Lawrence} [ibid. 41, 121-123 (1985; Zbl 0602.68066)] is then discussed and optimal algorithms for determining \\({\\mathcal U}(\\alpha)\\) and the finite equivalent subsystem of \\(S=\\alpha^{- 1}\\circ \\alpha\\) are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087020$594B0223-466C-4062-A02A-1F947D9B514D","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":"Q1087020$86CA1E2E-A5B4-4F19-B6F7-0C5593396733","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$F27AD61F-15F6-422D-91A6-9CCD585916F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$1CCA8641-8D3B-421B-94F4-7DF384C30DA8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"62d14ceccfaab394fd01a26f30bf0e501d21f492","datavalue":{"value":"3986660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$B6729437-767D-482F-86BA-578935D0471E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc48b063a1f3fa1d3bde486c3255ff42e4453d1b","datavalue":{"value":"entire system of equations over an alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087020$05D61B90-C830-4DC4-8CB4-D6BC6E0BCA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66753183b0cb830ef1b09008d2da958f24127df4","datavalue":{"value":"shuffle automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087020$0CAD6C10-5A6B-485D-B6C9-7C2676774C81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01588185e6a0ea452aabe243e9d0ed340c301288","datavalue":{"value":"rational language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087020$B32E6C75-A6EB-4D64-9D97-9BBC1154897C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99d0ffba6115054586d6b15b93afa7ecd639390f","datavalue":{"value":"Ehrenfeucht conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087020$2C3501C6-1CD5-4372-A305-8F0E7DDE78F9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a66f886183b423c2fe345be4a846cb0ef9ec5525","datavalue":{"value":"Q122965896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$4233943B-4EDF-4873-9CFE-38DEDF86E4E9","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":"Q1087020$E9312D1B-0932-43F1-A250-BB5A8280804A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e207129e7cefba4558bc06fafb513ec91f1a4e86","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90137-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1087020$BFCA2B97-5CA0-4507-BC7D-1B59F0B0EA3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5111432093c14cb4da366353a93cda2e9329d4dc","datavalue":{"value":"W2091781319","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087020$4F2CF5FF-9C09-4C7A-8E06-10012C3A46B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb07ca89a63cc1d58eddbd66f8d974a65762099","datavalue":{"value":{"entity-type":"item","numeric-id":3673125,"id":"Q3673125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$05513B92-F835-4AE8-991A-168AB37047E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"316efa88cf77b4454ebf6bf615125603e4869ad0","datavalue":{"value":{"entity-type":"item","numeric-id":794778,"id":"Q794778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$9B029EE5-7A84-4C79-AA27-4478A430293E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20928c7f2c11f2ebfe3e39d3742f5d1cff313dfd","datavalue":{"value":{"entity-type":"item","numeric-id":786545,"id":"Q786545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$BAB9C606-23DF-4B9D-B8AA-563E5E5A9DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc01f3100301b38f61a7577d1472e11bbe79b2b","datavalue":{"value":{"entity-type":"item","numeric-id":1251076,"id":"Q1251076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$844836C9-42CA-4D96-988B-6E7F12DD7D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e6c6e76c534f7463056bc07257e9faa9fbf18e","datavalue":{"value":{"entity-type":"item","numeric-id":1148122,"id":"Q1148122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$2AF65479-4250-4D61-BCB0-C4C01FD99CD4","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":"Q1087020$A2417609-627E-44AD-99E6-025897DA91CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f3c4123c6f16f5598589a408c561cf8e1584d03","datavalue":{"value":{"entity-type":"item","numeric-id":1056551,"id":"Q1056551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$E86E39B8-3824-4C40-A4B5-ECAE1E2F9DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bee5a181d891b451d07326284c0a19b6b74acb2","datavalue":{"value":{"entity-type":"item","numeric-id":798007,"id":"Q798007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$AA1FD7B5-4A29-461F-B649-EFA8538F7C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe18fdfb882c799d34a7482b763d96a45625e71","datavalue":{"value":{"entity-type":"item","numeric-id":3853827,"id":"Q3853827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$50D8C05E-4959-4D8B-A9C8-A32BCAA01EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac741c89220cd47e5d20a295f809bee30ead632a","datavalue":{"value":{"entity-type":"item","numeric-id":5673640,"id":"Q5673640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$949BC26C-169A-490D-9FE4-DE9ECD43D4FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$A9D045E7-8889-44B6-86C6-F71153DB7187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f862e5982ef76da3452eb1c73e9cabb62764a09","datavalue":{"value":{"entity-type":"item","numeric-id":5610821,"id":"Q5610821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$E4434D9A-FF9D-4431-ABF4-C3E30234EC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6743832806513b495c15b8d3c3fae8c97120cdc","datavalue":{"value":{"entity-type":"item","numeric-id":797700,"id":"Q797700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$721ED92A-2D9A-4F0F-824E-53862361476C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eaff128f896886cb8af9c8871ea48a04148f039","datavalue":{"value":{"entity-type":"item","numeric-id":1214507,"id":"Q1214507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$550440AD-28FE-4B7A-9794-00F0273F45D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"346bf2f216cbeafb98b33f70296a4799c0531818","datavalue":{"value":{"entity-type":"item","numeric-id":4200394,"id":"Q4200394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$081B5B21-CCF0-4914-A8CF-278FE6653010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a38983994d370e8a720ddf6cc1f7b76354ca36d","datavalue":{"value":{"entity-type":"item","numeric-id":3921412,"id":"Q3921412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$86798075-D6DA-4D22-A228-ACB518505775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae8a07ad3f5742fc1e1ff57f56a60556ddb931e","datavalue":{"value":{"entity-type":"item","numeric-id":3722740,"id":"Q3722740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087020$EC8CA329-169E-40F6-B890-E7A7FB9DA3D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b424a5db640febc1255aaab93a72609cda70f502","datavalue":{"value":{"entity-type":"item","numeric-id":4345386,"id":"Q4345386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b24e245dd2dea5b00dcd768c96bc754c92cb5cf","datavalue":{"value":{"amount":"+0.8776726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$9F0EE089-0E93-480D-A5E3-E3DA8EAF2C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a360fe1517b4d88196c725681b4909de703aec0","datavalue":{"value":{"entity-type":"item","numeric-id":2646009,"id":"Q2646009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f201992a94688beed4ff8dc224039cbf54870c2d","datavalue":{"value":{"amount":"+0.8769415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$465A66BA-741F-485E-B978-29DC9457ACD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b338d592eaee3a977d7fbe6734f341634ef4c1d","datavalue":{"value":{"entity-type":"item","numeric-id":5510986,"id":"Q5510986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"390bd08aa39ab37fc3c82f96d4c64fe2d9fbab67","datavalue":{"value":{"amount":"+0.8741363","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$D4FED50B-3BD9-4D99-ADF6-C6B2C2CFB69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deda525cb1c673157b7f071fd51982ba778bbfa6","datavalue":{"value":{"entity-type":"item","numeric-id":4712796,"id":"Q4712796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2a4bd57c4ba777f779ffb24d360432c49552010","datavalue":{"value":{"amount":"+0.86801875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$E3C9198D-62D8-4F67-99C3-ACDCFC9D6758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2b7921f44d63145dd14959b26a98b384266173f","datavalue":{"value":{"entity-type":"item","numeric-id":4959094,"id":"Q4959094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"003d4c94cf6dbd1a4274bcda1cbfa4e64cf34918","datavalue":{"value":{"amount":"+0.8648282","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$8063D073-0C50-438F-AA96-FC6102DDA825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ab7116b78a568bfed28433eec87804436671548","datavalue":{"value":{"entity-type":"item","numeric-id":3813852,"id":"Q3813852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5217fb420b5ba2f247e2ca17e337f7ca1b8699d8","datavalue":{"value":{"amount":"+0.8642741","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$7E927C6C-313B-4B92-B9EA-FED29C9E4DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aaf412cf29f0622224bd412d1c230e84d87f2c8","datavalue":{"value":{"entity-type":"item","numeric-id":5184955,"id":"Q5184955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c372db59f603bdc42943deef5ea97a83398e666f","datavalue":{"value":{"amount":"+0.8634032","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1087020$A49C5669-A8CE-48A8-9A70-AA1CCF01C750","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Syst\u00e8mes entiers d'\u00e9quations sur un alphabet fini et conjecture d'Ehrenfeucht","badges":[]}}}}}