{"entities":{"Q1116698":{"pageid":1127447,"ns":120,"title":"Item:Q1116698","lastrevid":69680859,"modified":"2026-04-13T08:40:22Z","type":"item","id":"Q1116698","labels":{"en":{"language":"en","value":"Separating strings with small automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090805"}},"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":"Q1116698$173DF4F9-D5F2-474F-A34F-F90BCA075E4C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e2f292f29228781073c010734a1de7f52a71a95","datavalue":{"value":{"text":"Separating strings with small automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116698$908D34A3-9CB5-4A3D-98C2-A81EBFA1CC6D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"530c33f9178f09a74b585b6f85e88fe8bfca663c","datavalue":{"value":"0666.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116698$2A249022-8EFB-4B88-90A8-A4B0BA1CB00D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c11ff2a96f4a073669d1ca764ebbc4822126d79c","datavalue":{"value":"10.1016/0020-0190(89)90215-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116698$8C5A4A7C-3BA3-4C06-B008-5E54F140C18F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$D95F03BE-445E-495C-9E6A-E5AA5272CC22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1116698$F40176BB-44D9-4A9F-8CC7-4A423DE3FC88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b70e0073c388d4d18f0b06dc6ac839d323ccbb16","datavalue":{"value":"A finite deterministic complete automaton separates a pair u, v of input words if the actions of u and v are different. A problem arises of bounds for the function Sep(n) defined as the minimal number k of states such that for any pair, u, v of words of length at most n over a finite alphabet A one can produce a k-state automaton separating the pair. The paper brings the best yet known upper bound, to wit, \\(Sep(n)=O(n^{2/5} \\log^{3/5} n)\\). The author regards the estimate \\(O(n^{\\epsilon})\\) for any positive \\(\\epsilon\\), conjectured by Ch. Choffrut, as unlikely.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116698$9BE2349C-C737-4870-B7D5-EBCAC593E1BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116698$589F2EFD-0B73-41F9-879B-7079EE8D15F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28f0cef31393497c79bcaf25c6bb2324f6f917b7","datavalue":{"value":"4090805","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116698$12BA4862-7619-42F8-BF7B-1B6590AE85BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ac3aa141a5e99f6d4ec0321d581483dfafb5e9","datavalue":{"value":"finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116698$4F08826E-2F41-41B3-A16E-A187F7BF4C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"549f0f1b66c36f8f80b8f33e286a1ff6b5444b18","datavalue":{"value":"rational function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116698$1A2A32BA-A6DC-442A-BF1A-E70EBA69DBA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b50519725d7e01002dadf87553f67c1625a16504","datavalue":{"value":"deterministic complete automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116698$93A2D736-29CF-4B2C-B3B3-56AE1919A28C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2414d88a8882328e4807f46176099bdadd88af5f","datavalue":{"value":{"entity-type":"item","numeric-id":426817,"id":"Q426817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$CE691890-137A-4A72-8391-6171A09EF39C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$5AC5EAA4-00FF-4BE6-A09D-20A582095685","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":"Q1116698$69EF1BAD-5295-4230-BC39-94BACF9E7FF1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b9188ea3cd35387983e1524408aed0fc93e794d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90215-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116698$504F0301-EE1A-4388-BFE4-0380B85B7BE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee28ee358da9cd50033c2f58b15e51f4589d1afd","datavalue":{"value":"W2060826277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116698$7186CFB2-94DA-40F8-B594-58829DD9D5C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"06452caa6baef4f96ff6c134534367cafd33e238","datavalue":{"value":{"entity-type":"item","numeric-id":3725551,"id":"Q3725551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$20DFC9A0-EC2C-4F0B-AC1C-5C048D63ABF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdba607cc3a28114c6291ca15f21dcda933d1f1d","datavalue":{"value":{"entity-type":"item","numeric-id":5661970,"id":"Q5661970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$0D0ACFC9-2007-46A9-8DFC-CFF6F0F42EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25aeb0cd6bad7e9ad25b8cbfaddfb36f51f9f34a","datavalue":{"value":{"entity-type":"item","numeric-id":3746906,"id":"Q3746906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116698$29620576-2B32-47CC-9668-14AA43414578","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d719324171a7087dc240862ea40e1d05f570ce43","datavalue":{"value":{"entity-type":"item","numeric-id":4347164,"id":"Q4347164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0bd189ef6f3b8af2f3c994a0f4a88cf1bc06b70","datavalue":{"value":{"amount":"+0.8596061","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":"Q1116698$D5D11A1C-D5F6-424F-8AF7-91A5662611B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"006157f0fc531b601f178a6bcb25a245432da97f","datavalue":{"value":{"entity-type":"item","numeric-id":4939575,"id":"Q4939575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43faeb4eedb03713d450d4066c1d75be539963c5","datavalue":{"value":{"amount":"+0.8412447","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":"Q1116698$6AD0754B-CBDF-4338-9742-F3616B2F4CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dbd904384b427c302b0cdddb29cb2f644a768b1","datavalue":{"value":{"entity-type":"item","numeric-id":4633540,"id":"Q4633540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"622706ee5f7458e8adc06f79b31cf142215c049a","datavalue":{"value":{"amount":"+0.83953","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":"Q1116698$493AA6AA-8CB3-47D1-858F-5BA2DE9B21DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eeadda1685ffcda0409727ef7e3fb0cd7984877","datavalue":{"value":{"entity-type":"item","numeric-id":3075486,"id":"Q3075486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bf42591e50f8e82913025c8ab6d47a194540123","datavalue":{"value":{"amount":"+0.8386469","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":"Q1116698$DBD8D265-2FC9-4BA1-8CC0-FF5DED41D5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7013ce4f9f0f86ff108a83a9a5985202d3c110cc","datavalue":{"value":{"entity-type":"item","numeric-id":3508569,"id":"Q3508569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ba27271c5f87256a08de2929048ab73e9f67749","datavalue":{"value":{"amount":"+0.83207583","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":"Q1116698$F8E57F19-C956-44F6-BED5-789B98473DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff96dac6610beccbad4a123e63b648201cdcd9f2","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65459a9d4a817c2aa65d9819ea2dc5653618eb53","datavalue":{"value":{"amount":"+0.8292464","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":"Q1116698$4BCDB6D2-3BEF-4C86-9C07-BEAF85B85C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7e8e798b954f81c96994819f25cf2983b579a9b","datavalue":{"value":{"entity-type":"item","numeric-id":3194867,"id":"Q3194867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c55f9605d71734726122eb04474f8aa7559267b3","datavalue":{"value":{"amount":"+0.8273481","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":"Q1116698$0F25BEE4-AD20-4CC5-8E2D-881F41513BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b4618cf27c49465255acb1a017c78e5093f8a1c","datavalue":{"value":{"entity-type":"item","numeric-id":722214,"id":"Q722214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7d3cfe88fdd31965d796c71ee2db09f3f36ada4","datavalue":{"value":{"amount":"+0.8269061","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":"Q1116698$16458323-742A-40CF-A67B-C1AC8AE69F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"928e2093ed6338f770a9ef8a5181d97de69b8097","datavalue":{"value":{"entity-type":"item","numeric-id":2904489,"id":"Q2904489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45dab9a4c0e6bc970783a6cd18bb7b69230088eb","datavalue":{"value":{"amount":"+0.8264878","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":"Q1116698$DE667736-0881-40E2-AE86-355BF6C11FE0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Separating strings with small automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Separating_strings_with_small_automata"}}}}}