{"entities":{"Q2480773":{"pageid":2491516,"ns":120,"title":"Item:Q2480773","lastrevid":78979925,"modified":"2026-05-06T12:52:27Z","type":"item","id":"Q2480773","labels":{"en":{"language":"en","value":"Two-letter group codes that preserve aperiodicity of inverse finite automata."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5258587"}},"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":"Q2480773$FBF5DB8C-F193-47B6-86EE-C9D89C5FBD25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2887f4934f10a46078e9a4474bb99eee12f43ed4","datavalue":{"value":{"text":"Two-letter group codes that preserve aperiodicity of inverse finite automata.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2480773$3921F51B-2633-4D19-A48F-AC2B9C14C454","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44d66c49b08c8cb3ee48a316658e0b283c48db89","datavalue":{"value":"1149.20051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$D5569721-762A-4E75-8801-49D50A975093","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1af85c7b2f6fd07526dd5f6ad7e9d1c876779e29","datavalue":{"value":{"entity-type":"item","numeric-id":766115,"id":"Q766115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$6A77F109-3631-47F5-99F0-3137DEF22D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49765b9386a0e4b33959826d4b969fa5873a565a","datavalue":{"value":{"entity-type":"item","numeric-id":700387,"id":"Q700387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$A1DA405A-10CF-4841-80F7-BA8D04809571","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$7B7FBA30-B2B9-447C-835B-191430A631C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"75beb6032318b2d8517c0143c6afc0207210466c","datavalue":{"value":{"time":"+2008-04-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2480773$F8E2B7D8-B78C-48DD-AE93-CBD1D07B547F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8909c6dcb81108159b75071500f40deca900e8b4","datavalue":{"value":"https://arxiv.org/abs/math/0701264","type":"string"},"datatype":"url"},"type":"statement","id":"Q2480773$A5DF3C51-13BE-477A-B5E0-B44E4E57AAC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9fe548ce37d2f42b8dbc481fe36b95bb7ff3405","datavalue":{"value":"The authors study free groups and bases of their subgroups, called group codes. They are particularly interested in group codes over an alphabet of size two that preserve aperiodicity of inverse finite automata. The main use of group codes is to translate large alphabets into smaller ones, in order to show that some problems that are hard over large alphabets are also hard over two-letter alphabets.   Group encodings, which are log-space computable reductions from large alphabets to small ones, allow the authors to show that some problems are \\textsc{PSpace}-complete over two-letter alphabets. Earlier work had shown them \\textsc{PSpace}-complete over all large enough finite alphabets.   The problems investigated are: -- the `radical-closure problem' for finitely generated subgroups of a free group, -- the `aperiodicity problem' and -- the `intersection-emptiness problem' for inverse finite automata, and -- the `membership problem' for finite inverse monoids, the latter remaining \\textsc{PSpace}-complete if the finite inverse monoids are three-generated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2480773$CE1DF4C1-6EFD-4C62-A5EC-5A7061AB9871","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$2F17750E-4B56-494C-A983-60041D28A270","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$0610DC98-70E2-48C8-906C-BD9815F2995E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$F0AA1D67-0924-4C7C-8563-7D69179C4336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$DF08C363-5CFE-4207-ABF5-34E36248C0F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e478659c80ac196196a2283c8b16b79c8d8cd8d5","datavalue":{"value":"20E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$3ABE8840-B4C4-446B-8E13-FB3E662C17BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$DA468639-D40C-4194-8004-3F6768B6BF3D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76bedfecbc617d42e83026e62df9acfa5753cf58","datavalue":{"value":"5258587","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$A2FB2E7C-EDD0-4268-9598-D4C24D52A44D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffb9b557bffdfa5cd70d593a7ec3f8594345072","datavalue":{"value":"free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2480773$87263F42-C1C5-4ECC-9128-9AC384B2364A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"094fe1e4d723ddc98de600ccad66b761ad85623d","datavalue":{"value":"inverse semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2480773$B5A67A44-2AAB-4134-A395-89D9622685FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49e571281c2f435a341bda12aa640a445b852f2b","datavalue":{"value":"inverse automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2480773$ACC52229-402C-421B-B55D-AC257234BF04","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":"Q2480773$B546A508-F7E0-48A5-8C76-EA794E209461","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3093f3234bf46309cc05a654552ce80416bc265","datavalue":{"value":"W2032480779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$781EB071-D1A9-4A42-ADC1-F5957DA45E51","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"14c48b799d30c64e9d23eb32341dac746f5ea11c","datavalue":{"value":{"entity-type":"item","numeric-id":4302805,"id":"Q4302805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$88B6710C-AD20-45E7-8F35-344D2E04CCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84b60b6016e2874f3433a4a41cc31aafa6dd93fc","datavalue":{"value":{"entity-type":"item","numeric-id":5616207,"id":"Q5616207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$D320DCC0-B823-4942-B1A9-D2D203CCF3FD","rank":"normal"},{"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":"Q2480773$70076EF1-B962-46FF-B494-878790BDE2B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bcebe3e5e589b59809b54b4843b39a94cae5f60","datavalue":{"value":{"entity-type":"item","numeric-id":3714479,"id":"Q3714479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$69BB8E4B-8EB7-4A04-BB3D-764BCC5677C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4743d8545e31e5374c6f8da972c29d51e6a90417","datavalue":{"value":{"entity-type":"item","numeric-id":1575552,"id":"Q1575552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$DE78361E-7116-42D6-8EB5-6CDD6DB04A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69d90cc4fbc5f5010b872b4415e8fd3d87ac5522","datavalue":{"value":{"entity-type":"item","numeric-id":809608,"id":"Q809608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$CEFFD7CB-1928-4074-A277-CCC08C1850E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00debc852f8640499ed8f2b406c6bd43dbff990c","datavalue":{"value":{"entity-type":"item","numeric-id":4040880,"id":"Q4040880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$31D17935-5135-413F-BCC2-5F90012D4D5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$A63510AE-EAD2-4AF6-BE30-A384415A59A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d3cbffed8a301b84b1253490d8c6b17bf2e322","datavalue":{"value":{"entity-type":"item","numeric-id":4145882,"id":"Q4145882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$0390922B-C197-4558-A23B-50F5FDD1F365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"823e2328202f2501bb4c0a3bf0d9b4af246ee89b","datavalue":{"value":{"entity-type":"item","numeric-id":5513066,"id":"Q5513066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$A124E865-7D53-4953-941B-C8B3BDE68F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"653a847b0e494a47307ab3dabe8253959a47e518","datavalue":{"value":{"entity-type":"item","numeric-id":4039407,"id":"Q4039407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$6DE46F79-5A45-4F1E-99BF-F6D60AE36C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc991b6b90e8360baaa546e9dfdab51d8674e144","datavalue":{"value":{"entity-type":"item","numeric-id":1055547,"id":"Q1055547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2480773$931C6424-F71F-4324-AD53-0B4AD93CA9D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b56a9361b9ff93afb2b32599362ffd3343d4dfd","datavalue":{"value":"10.1007/S00233-007-9024-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2480773$A4DC4AB3-BFA5-4A40-93CA-1D4F3EDE7748","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cab921d3c33448159a89aed4eaaa4e52cf21dda","datavalue":{"value":{"entity-type":"item","numeric-id":1575552,"id":"Q1575552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13550ac41155f487119988a7ad506df5cfffe467","datavalue":{"value":{"amount":"+0.7971447706222534","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":"Q2480773$CEFDD470-4140-4D92-8DDB-5715001B1848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328d3fd41b6e1072c430224e6ae019caf997f4cc","datavalue":{"value":{"entity-type":"item","numeric-id":5701839,"id":"Q5701839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed54e30dc11b5ec1792670cc9f27e0ee6e21a79f","datavalue":{"value":{"amount":"+0.7946357131004333","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":"Q2480773$0AA4AD2D-E699-4E93-AFD1-911992A48AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51183160268480f0601d444b711faea175f1f5f0","datavalue":{"value":{"entity-type":"item","numeric-id":4632433,"id":"Q4632433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd03aa53edd6aa6dd6d821e7badee078ff594f09","datavalue":{"value":{"amount":"+0.7615838050842285","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":"Q2480773$B8627799-CA12-47F3-86AC-F83E03B9B517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2e0914246e804c7def16db2c48f259b71beae39","datavalue":{"value":{"entity-type":"item","numeric-id":1118045,"id":"Q1118045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e19808ecd3b3ceec39a96a8e8792bee147c6e12","datavalue":{"value":{"amount":"+0.7596498727798462","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":"Q2480773$80CE46C6-A22E-4CB2-B9A4-EAE406EC0D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f28c6336cbbd950d279977f579d598176090d80","datavalue":{"value":{"entity-type":"item","numeric-id":2957911,"id":"Q2957911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5ddc203b780cfe2a79d1e9c2c8fafe1dc879be","datavalue":{"value":{"amount":"+0.7510297894477844","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":"Q2480773$50819CBD-C126-45C5-88E7-872D9791305A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two-letter group codes that preserve aperiodicity of inverse finite automata.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two-letter_group_codes_that_preserve_aperiodicity_of_inverse_finite_automata."}}}}}