{"entities":{"Q6828981":{"pageid":15113824,"ns":120,"title":"Item:Q6828981","lastrevid":56014165,"modified":"2026-02-24T13:51:48Z","type":"item","id":"Q6828981","labels":{"en":{"language":"en","value":"On the finiteness problem for automaton (semi)groups."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109800"}},"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":"Q6828981$B0DFC30E-26EB-4079-BE53-0D3D5884C23E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"719485bba434f202ad2ed401789642e870f27b5e","datavalue":{"value":{"text":"On the finiteness problem for automaton (semi)groups.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6828981$C196A4F8-9565-4D1E-9803-34F9B09057CE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54304cbc7492722960d23fbc2d06af8622ab1850","datavalue":{"value":"1280.20038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$0AA0AB63-A8DE-46EE-B37C-B9D16AE05BAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eae00dfee258b0de3c9db4c835b996ecee09b8f8","datavalue":{"value":"10.1142/S021819671250052X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$B55E6D3E-6C1B-4AA7-8353-8BBFBDA0B10C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"edd540c0e63da98971b97d82c28b66fecf0a02d7","datavalue":{"value":{"entity-type":"item","numeric-id":1401287,"id":"Q1401287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$1A51D39B-A124-432E-9EE0-D496A12E0CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd43315ebaf760c2f7170a023fa78e8c4528eed1","datavalue":{"value":{"entity-type":"item","numeric-id":290909,"id":"Q290909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$AB0FC783-8BFB-4F00-AA6F-307776CCE09D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5630e4cc33e0b5ace5aedf722447568c8009b63b","datavalue":{"value":{"entity-type":"item","numeric-id":703496,"id":"Q703496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$6CC1C98E-9DB0-485F-8919-F1DBF006059B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dce1962c1d1bd73daa78cc2c873eecc90e519ff9","datavalue":{"value":{"entity-type":"item","numeric-id":235677,"id":"Q235677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$DBCDF0FD-6C70-4F59-8130-B02562ED0458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"39e579b512944c362c68ce71483db94c48c46c53","datavalue":{"value":{"entity-type":"item","numeric-id":236951,"id":"Q236951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$98A62FDF-6E2E-41D7-9F9E-04D45720C22D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7f4e75461d95037e69d585d3faf5530e0368f039","datavalue":{"value":{"entity-type":"item","numeric-id":2703070,"id":"Q2703070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6828981$7AE414E9-BEF0-488D-B016-8754699DB7EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6828981$6EFA893D-5180-490F-89BE-C34FA76E32C3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"da93548318fe4430034aa48fbb8e61f377a30e6a","datavalue":{"value":"By a Mealy automaton the authors mean a quadruple \\((A,\\Sigma,\\delta,\\rho)\\) where \\(A\\) and \\(\\Sigma\\) are finite non-empty states (called, respectively, the state set and the alphabet) and \\(\\delta\\colon A\\times\\Sigma\\to A\\) and \\(\\rho\\colon A\\times\\Sigma\\to\\Sigma\\) are totally defined functions. If \\(\\mathcal A=(A,\\Sigma,\\delta,\\rho)\\) is a Mealy automaton, then each state \\(x\\in A\\) defines the function \\(\\rho_x\\colon\\Sigma\\to\\Sigma\\) by \\(\\rho_x(i)=\\rho(x,i)\\) and each letter \\(i\\in\\Sigma\\) defines the function \\(\\delta_i\\colon A\\to A\\) by \\(\\delta_i(x)=\\delta(x,i)\\). The function \\(\\rho_x\\) extends to \\(\\Sigma^*\\) in a natural way: if \\(i\\in\\Sigma\\) and \\(u\\in\\Sigma^*\\), then \\(\\rho_x(iu)=\\rho_x(i)\\rho_{\\delta_i(x)}(u)\\). The semigroup of all mappings from \\(\\Sigma^*\\) to \\(\\Sigma^*\\) generated by all the functions \\(\\rho_x\\) with \\(x\\in A\\) is called the semigroup of \\(\\mathcal A\\) and is denoted by \\(\\langle\\mathcal A\\rangle_+\\). If all functions \\(\\rho_x\\colon\\Sigma\\to\\Sigma\\) happen to be bijective, the group of all mappings from \\(\\Sigma^*\\) to \\(\\Sigma^*\\) generated by the extensions of \\(\\rho_x\\)'s with \\(x\\in A\\) to \\(\\Sigma^*\\) is called the group of \\(\\mathcal A\\) and is denoted by \\(\\langle\\mathcal A\\rangle\\).\\N\\N The authors study the following finiteness problem: given a Mealy automaton, determine whether its (semi)group is finite.\\N\\N If \\(\\mathcal A=(A,\\Sigma,\\delta,\\rho)\\) is a Mealy automaton, its dual \\(\\mathfrak d(\\mathcal A)\\) is the Mealy automaton obtained by switching the roles of \\(A\\) and \\(\\Sigma\\). \\textit{D. Savchuk} and \\textit{Y. Vorobets} [J. Algebra 336, No. 1, 53-66 (2011; Zbl 1239.20032)] have shown that the semigroup \\(\\langle\\mathcal A\\rangle_+\\) is finite if and only if so is the semigroup \\(\\langle\\mathfrak d(\\mathcal A)\\rangle_+\\). The authors observe that the minimization of a Mealy automaton does not change its semigroup but the minimization of an automaton with a minimal dual can make the dual automaton non-minimal. Therefore they suggest alternatingly minimize and dualize a given automaton until both the resulting automaton and its dual become minimal. If this process leads to the automaton with one state over a one-letter alphabet, then the semigroup of the initial automaton is finite. This sufficient condition for finiteness is not necessary but its implementation has allowed the authors to establish finiteness for a number of automaton semigroups whose analysis was not possible with previously known finiteness conditions.\\N\\N The helix graph of a Mealy automaton \\(\\mathcal A=(A,\\Sigma,\\delta,\\rho)\\) is the directed graph with nodes \\(A\\times\\Sigma\\) and arcs \\((x,i)\\to(\\delta_i(x),\\rho_x(i))\\) for all \\((x,i)\\). The authors show that if all functions \\(\\rho_x\\) and \\(\\delta_i\\) are bijective and the group \\(\\langle\\mathcal A\\rangle\\) is finite, then the helix graph of \\(\\mathcal A\\) must be a union of disjoint cycles. This necessary condition for finiteness is not sufficient but again its implementation has proved to be superior over previously known finiteness conditions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$886E1BF4-1F26-484D-89D0-C3BBC999068E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$CAC8159B-B3C6-433B-8B03-FF092530248E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$E1EDDDDE-9E26-4514-9238-7888D55C776E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"513bb673382d4f095f636a36264a50a0e4d1769e","datavalue":{"value":"20E08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$646315B1-FCC2-48D1-98B5-0D8B9703330B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$50B659B9-7C97-42D1-BB73-C36335143A63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c897aeac0b441cd7b2e44f75215ba7b510dfa0d","datavalue":{"value":"6109800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6828981$0448DC2F-5A68-444E-8F74-E36F31504E17","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"336f9cc1f5ba0f2bec287498f43d766f7d2511c5","datavalue":{"value":"Mealy automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$1AFB544E-0EB8-43CA-B7BC-540F1E18A643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"084f3e1e9bb79a5880b30b6d316e2e9961813dee","datavalue":{"value":"automata groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$C22E9AD0-06C5-4F9F-9741-CED7161F948A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc9e645fc3b9dcbcde640d7c2460578df3b449ad","datavalue":{"value":"automata semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$4C080C01-8A78-4B09-8235-16EB2F11DF7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcd015ff20b79926648b417fbc962fb4bc3bc230","datavalue":{"value":"finiteness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$4BE6E06A-E95E-4039-86E7-4E72D0620CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86bb1713115867c6f5c810be4deb030b4da24553","datavalue":{"value":"helix graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$C1BA6D9E-76AC-49B9-9656-CC5CC2A1E86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78ca2857d2151bbf45c5ccdfc93616633758d7cf","datavalue":{"value":"dual automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$66F3FC5E-EB44-450D-9F33-5EAB221E6FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1279221fe7735b1b47afd1411b335eca7e3f0e","datavalue":{"value":"minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q6828981$B93E9A71-CC7A-4CBB-BA3F-2817883145F1","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":"Q6828981$66DF7206-DA89-4D44-80B3-C678E9B026BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the finiteness problem for automaton (semi)groups.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_finiteness_problem_for_automaton_(semi)groups."}}}}}