{"entities":{"Q656372":{"pageid":658221,"ns":120,"title":"Item:Q656372","lastrevid":63370815,"modified":"2026-04-11T12:24:54Z","type":"item","id":"Q656372","labels":{"en":{"language":"en","value":"A criterion for the decidability of the \\(A\\)-completeness problem for definite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5998433"}},"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":"Q656372$564558BC-0C72-431C-8998-B83A86AEE8C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5cfb3f3ece490433dfcf5b7fe550b3a6ceaf107","datavalue":{"value":{"text":"A criterion for the decidability of the \\(A\\)-completeness problem for definite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q656372$E6AB4A1C-60AA-48D4-9B6E-496CD69920EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"04018ecd066c6b8b6da5194cd2700ba9ef77b138","datavalue":{"value":"1244.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q656372$CBF0EFDB-DBE4-433A-AE0B-0825B5126D84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cf50b0b1f45dee0aa79cce95c895dd54a3260250","datavalue":{"value":"10.1134/S1064562411040065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q656372$0778116C-CD76-491E-812F-5A00A1A3FF2C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2bbc31fcaa3dcf49d82403ba391044fdfb104e43","datavalue":{"value":{"entity-type":"item","numeric-id":161529,"id":"Q161529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q656372$65942146-E3A5-4ECC-8799-DA8422A5A01C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e8f47db6d3162742e0091c274a854f76c796b77","datavalue":{"value":{"time":"+2012-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q656372$62A923EF-477B-4866-AFEB-95CE4CC8CF6F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b34b41bdefb959d4a84de4153189decc1c8fc82e","datavalue":{"value":"A function \\(T: (E_{2}^{n})^{\\infty}\\to E_{2}^{\\infty}\\) with an input sequence \\((\\mathbf{x}(1),\\mathbf{x}(2),\\dots) \\in (E_{2}^{n})^{\\infty}\\) and an output sequence \\((y(1),y(2),\\dots)\\in E_{2}^{\\infty}\\) is called a definite automaton with \\(n\\) inputs of height \\(h\\) if there are functions \\(f_{j}: (E_{2}^{n})^j \\to E_{2}\\), \\(j=1,2,\\dots ,h\\), such that \\(y(i) = f_{i}(\\mathbf{x}(1), \\mathbf{x}(2),\\dots, \\mathbf{x}(i))\\) if \\(i\\leq h\\), and \\(y(i) = f_{h}(\\mathbf{x}(i-h+1),\\mathbf{x}(i-h+2),\\dots,\\mathbf{x}(i))\\) if \\(i>h\\). Let \\(\\mathcal{P}_{a}\\) be the set of all definite automata. Any definite automaton can be obtained by superposition operations from Boolean functions and delays. Each Boolean function is associated with a definite automaton of height 1. Let \\(t\\in\\mathbb{N}=\\{1,2,3,\\dots\\}\\). Two automata \\(T_{1}\\) and \\(T_{2}\\) with \\(n\\) inputs are \\(t\\)-equal if they coincide for words of length \\(t\\). Let \\([M]_{t}\\) be the set of all definite automata that are \\(t\\)-equal to those obtained from \\(M\\) by superposition operations. A set \\(M\\) is \\(A\\)-complete if \\([M]_{t}=\\mathcal{P}_{a}\\) for any \\(t\\). Let \\(F\\) be a clone of Boolean functions. The \\(A\\)-completeness(\\(F\\)) problem is as follows: given a finite system \\(V\\) of definite automata, determine whether or not the system \\(F\\bigcup V\\) is \\(A\\)-complete. For \\(m\\geq 2\\), let \\(f_{m}(x_{1},x_{2},\\dots, x_{m+1}) = \\bigvee_{i=1}^{m+1}x_{1}\\dots x_{i-1}x_{i+1}\\dots x_{m+1}\\) and \\((h_{m})^{*}\\) be the dual of the function \\(h\\).  Theorem. The \\(A\\)-completeness(\\(F\\)) problem is algorithmically decidable if and only if, for a certain \\(f\\in\\{h_{2}, x+y+z, h_{3}, (h_{3})^{*}\\}\\), it is true that \\(f\\in F\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$CD6D4F49-7698-4A8C-94BC-6BFF96556F6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q656372$635158BC-E846-48E2-B644-5CC3ED3EB0E0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee9d361e108e7f25c207653e61ef77ca1d74cc38","datavalue":{"value":"5998433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q656372$139B5C26-B66C-47C3-92F0-1BA00A19D8BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19e419a080e1b91a0e2f0b7dc77128409d04d46d","datavalue":{"value":"definite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$D654AD64-9EA1-44C1-A89B-F22D91D92CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2157b73def31f37a018efe23ba33e9eaf88ddaca","datavalue":{"value":"algorithmic decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$03153B66-EB88-44F1-9CF9-8CA2463D061C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b226e64c0738203fffceed5b5470b8eb3733af30","datavalue":{"value":"A-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$FF57CC88-531B-4B92-94DA-79A823885B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$626644A5-FB49-4546-B40D-68ED9F6F0754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b2f3ab8ec237c3f05afd995c2c137f62c66c8b5","datavalue":{"value":"automatic structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$0022F75C-B96A-49B8-8CCA-C045E7442FB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$0A87B2D3-D300-41BD-BD83-68CF4C672418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95eb206bd97e47281890ac4b8d31a5dc4e9ff7d3","datavalue":{"value":"push-down machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q656372$1A1F8B5E-63D1-4FE3-8CC6-73BED91910DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"351693e9525940268c4116160b96b589f752def1","datavalue":{"value":{"entity-type":"item","numeric-id":522227,"id":"Q522227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q656372$048BE374-ACC0-419F-BFB9-6DEA0DFE831D","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":"Q656372$428C6950-7A9A-49A3-8607-176AC1F5B13E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae41416b3c63fb62fa987b6d8dfe2556eabf311","datavalue":{"value":{"entity-type":"item","numeric-id":5845380,"id":"Q5845380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q656372$CA87231C-9139-4001-9B47-8AA94E4329AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9f699fce5b24c85b45352d3eb5f5bdb04772726","datavalue":{"value":{"entity-type":"item","numeric-id":3585192,"id":"Q3585192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f3d331279bfe8111f798fd390c8f0bf0504d8d3","datavalue":{"value":{"amount":"+0.89678377","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":"Q656372$6F2AD428-DBB3-4E7F-A980-3ABBB5051FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15ecd38b4738a65781eb49d32c3b30a767564241","datavalue":{"value":{"entity-type":"item","numeric-id":3125966,"id":"Q3125966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"593b87204c9d25d15bbce60b433ab7bb5ecbb826","datavalue":{"value":{"amount":"+0.8943259","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":"Q656372$5AF19E4F-7702-4470-A0C4-88E37FB8B9FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e341bcaec1b4dbc5c26ea38ced04c4dd59ec17c","datavalue":{"value":{"entity-type":"item","numeric-id":4857009,"id":"Q4857009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"912d89fbf09a8df2a8c396fd79f4d93331fe4a34","datavalue":{"value":{"amount":"+0.89036405","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":"Q656372$2C20042E-5559-4DB3-AD22-28E8F391C28E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce9c93e34ad3bf7680b08bcfa32c411a370da1e","datavalue":{"value":{"entity-type":"item","numeric-id":4712653,"id":"Q4712653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76bc83cd357295e63d886934ddbd262a69458156","datavalue":{"value":{"amount":"+0.8825643","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":"Q656372$25C90E69-1BFC-42EE-8498-0C2A3FA1BDD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b58d2bf5593372d4201064a516c4e726cbbe6c4c","datavalue":{"value":{"entity-type":"item","numeric-id":1816326,"id":"Q1816326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0ff849574cb78d7a7c35b6f6607ba34a2707573","datavalue":{"value":{"amount":"+0.88104326","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":"Q656372$4D8C6DB7-F62C-44FC-9C17-D8ADFD37182C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c2bddbdf2bf75c3c8f21d7d0458f024a40abb38","datavalue":{"value":{"entity-type":"item","numeric-id":4263836,"id":"Q4263836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89275fdecbe00000e14f2a4505685bc6565749c1","datavalue":{"value":{"amount":"+0.8788483","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":"Q656372$7F2B11BF-CD58-4F99-8E4C-E09D25A8D4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2505c3fd5c2bec5df5910d5b200a6c9841192c1","datavalue":{"value":{"entity-type":"item","numeric-id":1594479,"id":"Q1594479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e7833dd9859629e1142787c4624d1e97163d8f","datavalue":{"value":{"amount":"+0.87883306","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":"Q656372$92D951F3-7B18-4708-B72A-191AF5A720A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62d28157797ae1b2a786032bfe85ea08c5fd0ed5","datavalue":{"value":{"entity-type":"item","numeric-id":1622956,"id":"Q1622956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8834b16bab34c95daf9d42f42084e22839fe7cb","datavalue":{"value":{"amount":"+0.8787444","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":"Q656372$10AD7DCC-7546-4A65-9A57-CA6D809AE4D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa71b7040165ea11e1734ab110f605dff93ebd1d","datavalue":{"value":{"entity-type":"item","numeric-id":1897831,"id":"Q1897831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec3682462955aca65bbe9fa9ecacc44b472b1c2b","datavalue":{"value":{"amount":"+0.8730965","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":"Q656372$DD891B92-9026-45A6-A25F-F3826451118A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A criterion for the decidability of the \\(A\\)-completeness problem for definite automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_criterion_for_the_decidability_of_the_%5C(A%5C)-completeness_problem_for_definite_automata"}}}}}