{"entities":{"Q1103732":{"pageid":1114484,"ns":120,"title":"Item:Q1103732","lastrevid":69649944,"modified":"2026-04-13T08:27:24Z","type":"item","id":"Q1103732","labels":{"en":{"language":"en","value":"Automata accepting primitive words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053931"}},"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":"Q1103732$FABC4631-4E5E-4C41-847F-EE87FAC27F45","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25b9dd8432922be2ffc9a4b55846bb91ec413df3","datavalue":{"value":{"text":"Automata accepting primitive words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103732$867E5A5F-3C8E-40EC-9B6A-0B884209A38E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5cd59849561c2a3fd3a70752335f487d23a69db0","datavalue":{"value":"0646.20055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$007BE3D2-81AA-4997-B80B-DFECB6BE9817","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"790aaaa9d838bb81112461b6e4456d7710816783","datavalue":{"value":"10.1007/BF02573122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$E86EE826-2FF7-4926-9623-B0E9E7E19D26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d66c55b2090f999e6ce11f8c5edbc12ea7326d37","datavalue":{"value":{"entity-type":"item","numeric-id":799822,"id":"Q799822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$5885D524-A359-4488-9696-7610FBC6150B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf9593eaa493928400909236679b9ac572ddbd7c","datavalue":{"value":{"entity-type":"item","numeric-id":418778,"id":"Q418778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$97D1E264-0EED-4192-90E1-40019BF0F4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93829cf1e7393880b0d1558fc8a66776700c1a27","datavalue":{"value":{"entity-type":"item","numeric-id":590535,"id":"Q590535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$07688756-0FA3-438A-916B-10D18E58583A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"daefbcf4dea9b6830d84a9b2f4986d8c8abe2905","datavalue":{"value":{"entity-type":"item","numeric-id":745797,"id":"Q745797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$30187658-CB84-4AD4-A8BC-E350EEEC7780","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":"Q1103732$467E38EF-15B7-4D8F-96EE-858B4D580B59","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1103732$C987E931-AB77-4B9E-8AF3-030A978A9E07","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"34d4b3494b1bb3e5ecb75ef1c3c90b77742a5076","datavalue":{"value":"https://eudml.org/doc/134913","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103732$13E7C131-F47E-4F51-81B0-211B3BBE6039","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"034500843005598a7ff9a7271484323cfcd19a41","datavalue":{"value":"Let X be a finite alphabet, \\(| X| \\geq 2\\). A word w over X is said to be primitive if \\(w=u\\) n implies \\(u=w\\) and \\(n=1\\). In this paper, properties of sets of primitive words accepted by finite automata are studied. If a given n-state automaton accepts a primitive word at all it accepts a primitive word whose length does not exceed 3(n-1). On the other hand, it accepts infinitely many primitive words if and only if it accepts at least one primitive word whose length is no less than n. In particular, it follows that for a given automaton the questions of whether it accepts any primitive words and whether it accepts infinitely many primitive words are decidable.    In the final section of the paper, the authors focus on the following problem: Among those automata with n states accepting only finitely many primitive words, what is the maximal number \\(\\vartheta_ n\\) of primitive words accepted and what is the maximal number \\(\\eta_ n\\) of primitive words which are roots of accepted words. The surprising result is  \\[  \\vartheta_ n = \\eta_ n = \\begin{cases} 0, & \\text{ if \\(n=1,\\)} \\\\ 1, & \\text{ if \\(n=2,\\)} \\\\ | \\{x|\\quad | x| \\leq n-2, x \\text{ is primitive}\\}|, & \\text{ if \\(n\\geq 3\\).}\\end{cases}  \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103732$6312C4A8-98DD-48CA-97E3-3747CF7DDD2A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$A280724E-AC34-49A7-BE24-54F037B7EF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$6B4D272C-32BD-4CA1-904B-61C4564CF88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$4FA641F5-1428-47BA-886E-C9F3D51BCA04","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"20e342bc347bb231398d5b9f907c4eaa707f37dd","datavalue":{"value":"4053931","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$3B1568E9-3365-42BF-AA5C-66F938C9891B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a73e2a07dc7c76a1d2c6a9efcd9e7f0989c95cdd","datavalue":{"value":"finite alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103732$255652A3-CE99-4C5E-B92E-7455FE90663A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1107ab5a4e5e5d78c39b214167705a7a34be04f","datavalue":{"value":"primitive words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103732$F8FACCD3-4BCD-4F31-9C5D-12D67BF112A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103732$618536AD-8691-4C55-A416-587B2DCB6B2B","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":"Q1103732$C5FBA952-19AB-42BD-B362-90D67A775196","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$59E46619-1BA9-453D-8B83-D2A18A2E6999","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":"Q1103732$F8CF34A1-69A4-45D6-9A31-EE492D1FFAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e7777a3f4e6a09ae8e6739493e732c9eba2e083","datavalue":{"value":{"entity-type":"item","numeric-id":4142707,"id":"Q4142707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$476BAC8D-CDCF-40C1-A4D1-F13639301A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a989d5b893328eb4ee90b6b35e09f2cbbef6561b","datavalue":{"value":{"entity-type":"item","numeric-id":4001349,"id":"Q4001349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103732$74E91B20-8887-464A-8531-D4012EE28226","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08bb5be9f4bd298db89add2995d7936041e2e700","datavalue":{"value":"W2049135619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103732$4D843B41-F49D-4766-821E-3A34C1DE8165","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d2dce3314538e87c752c6e4fda65fa7ff3d8d5c","datavalue":{"value":{"entity-type":"item","numeric-id":4289940,"id":"Q4289940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa9cb677fbfa610b22cd0634acb206d79f2fed16","datavalue":{"value":{"amount":"+0.806702733039856","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":"Q1103732$7723006A-014A-4EDA-902E-055A57985577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755c8cf7be7231c18442c46a906b309995385cd8","datavalue":{"value":{"entity-type":"item","numeric-id":5199965,"id":"Q5199965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf374598256305f47fe978545a9963201adf66ff","datavalue":{"value":{"amount":"+0.8056314587593079","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":"Q1103732$E33B5E65-8E42-43FC-BBC2-3543298C97BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20aa92a2f7ba1eb4f641ff7a192f0b00d244541e","datavalue":{"value":{"entity-type":"item","numeric-id":4835097,"id":"Q4835097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9822c15c1dc79297a2a3814c7c240b483c15a21","datavalue":{"value":{"amount":"+0.7961266040802002","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":"Q1103732$9EA73BB0-B182-4EFC-AAFA-FAB825E01543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1afa9d8901b4f325b1030ad5a06dcb30860a090a","datavalue":{"value":{"entity-type":"item","numeric-id":1351946,"id":"Q1351946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"589c2fac03cb9305f6522a8d85930524baf74bf5","datavalue":{"value":{"amount":"+0.796032190322876","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":"Q1103732$CC564352-F163-411B-8D40-FEA06004ADD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3de1e6b8c97255cc8fb614ca3537ebc174d10367","datavalue":{"value":{"entity-type":"item","numeric-id":4902891,"id":"Q4902891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ddee69dac3d11b99d94dfb97f303fcbfff034c7","datavalue":{"value":{"amount":"+0.7932801246643066","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":"Q1103732$9976B76A-9B18-44AF-A95B-FB17104AA224","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Automata accepting primitive words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Automata_accepting_primitive_words"}}}}}