{"entities":{"Q1853167":{"pageid":1863909,"ns":120,"title":"Item:Q1853167","lastrevid":71501505,"modified":"2026-04-13T22:41:00Z","type":"item","id":"Q1853167","labels":{"en":{"language":"en","value":"Simulating finite automata with context-free grammars."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856497"}},"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":"Q1853167$5B63A37A-2858-4FB9-82E9-152CAD920A3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56552bf63e8018b179bbec168f069b248e106eb8","datavalue":{"value":{"text":"Simulating finite automata with context-free grammars.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853167$B45A2CFC-9DD1-4999-B0CD-91ED715D518D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d3599d92687344689361d73d1d2e3db29f5aeae","datavalue":{"value":"1042.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$4752AF6C-FB5B-4958-A995-D624F856D612","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ae703aeb637b1748155fe129faee2409bb9f40d","datavalue":{"value":"10.1016/S0020-0190(02)00316-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$4A3B441C-C991-4548-9501-B0B9C122947A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5a51db63b464e29115f137e45fc0a5c610726c1","datavalue":{"value":{"entity-type":"item","numeric-id":596096,"id":"Q596096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$BC2D9A30-1DAF-4815-9C01-ACD9777BE182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f920db5aff0a8e6518a5a866c3161192fca7ec8","datavalue":{"value":{"entity-type":"item","numeric-id":383364,"id":"Q383364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$F2124341-C738-4E67-B9C8-B8D28F5C9294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$A5A61966-8345-499F-A0D3-6EF04F9B25BC","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":"Q1853167$00D57AFB-4642-4329-949C-9E0F376D5427","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853167$B4FC17F6-6DBC-470F-BCA6-F86E91F5743E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"114cf29ef376893bb613c3a2f09d38bd5b8e019d","datavalue":{"value":"We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky Normal Form (CNF). We show that any unary DFA with \\(n\\) states can be simulated by a CNF grammar with \\(O(n^{1/3})\\) variables, and this bound is tight. We show that any unary NFA with \\(n\\) states can be simulated by a CNF grammar with \\(O(n^{2/3})\\) variables. Finally, for larger alphabets we show that there exist languages which can be accepted by an \\(n\\)-state DFA, but which require \\(\\Omega(n/\\log n)\\) variables in any equivalent CNF grammar.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853167$0D743B99-947C-4B40-8AB8-514D72E51E1A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$B9C8F5FE-BCB7-4304-8E5E-7AC2CA508FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$26FB4912-04B1-43F3-86D4-5D20C0FAE7EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78e0681cba3b493e934ba4d14d366161f7a32fb4","datavalue":{"value":"1856497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$C3DB5759-E7BC-4748-BCFC-CC9B514E785F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8eb270d4ed4b446b915ab174a0d0120cef86df","datavalue":{"value":"Formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853167$CAB78E75-B401-48A1-8CE5-7511CE8F6BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc493705bfe128256dd6e42254b71a5c117094df","datavalue":{"value":"Context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853167$14F78B7A-379A-4715-82E9-36C45A57B2BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7c74c5552698bc5f1378c74a5f1a3f533d21987","datavalue":{"value":"Finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853167$101FD6F4-95AC-472C-B752-C5F9EAE6B35D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ce5121964163d8c3ae675a4347d120e864c24027","datavalue":{"value":"Q61677530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$A509E92F-9E18-447D-B3E4-B7A982755219","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":"Q1853167$448011D8-B66D-4300-A21C-542D4DA8EB33","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0754d3a742b181ffa61c73709a5cb271e4558135","datavalue":{"value":{"entity-type":"item","numeric-id":915454,"id":"Q915454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$8AF3193B-FE47-4740-AF4F-9949A8B38E19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc22b47c42ba322f4bd830111391b026b40a348","datavalue":{"value":{"entity-type":"item","numeric-id":1108812,"id":"Q1108812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$9475BC5C-0940-49D7-966F-02646FABD720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47cebc04b7eb71cacd961bf04ae46d43cff618b","datavalue":{"value":{"entity-type":"item","numeric-id":1199879,"id":"Q1199879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$0DE2DA00-E8F1-47B7-9213-25EB3FE1AF94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972ff908209cbae1dc0a10a9462932031345a6a7","datavalue":{"value":{"entity-type":"item","numeric-id":1099644,"id":"Q1099644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$9D367D2F-55EC-4C32-BCF0-531C1BBA3DFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fd39f0364449e5e5c2a79cc060419158de8d88e","datavalue":{"value":{"entity-type":"item","numeric-id":4939575,"id":"Q4939575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$BA3AF5B6-CC5E-4F66-847A-0405F7F900DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a350a646df05af2cd765c289d28ce10d45e83b7d","datavalue":{"value":{"entity-type":"item","numeric-id":5834367,"id":"Q5834367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$A84F95E3-A3FF-44F9-B2EF-6C0D3823B63E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a3937da7c4f68748dbeb886cf8ab8244d102dc5","datavalue":{"value":{"entity-type":"item","numeric-id":1165026,"id":"Q1165026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$1597657C-6818-4020-B9B8-4B5633C8A392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3f0dc35b38c0d4c197158839b5b91f68e624bf6","datavalue":{"value":{"entity-type":"item","numeric-id":5834368,"id":"Q5834368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$1ED60781-F0A2-48E3-96F8-A24FE11906C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"179d220356dcb5befb066d611c61b1fc47320f79","datavalue":{"value":{"entity-type":"item","numeric-id":5541336,"id":"Q5541336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$85158DC0-F4DE-4C85-AFEB-B63C4D46D637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"842925c3f00729504114c782c00814cfad550931","datavalue":{"value":{"entity-type":"item","numeric-id":5562596,"id":"Q5562596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$BC491A7A-BFE4-4134-B96E-8E8C4E7C6380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18a53ca570dc0817a413f0d97dff02d9e887338c","datavalue":{"value":{"entity-type":"item","numeric-id":4105792,"id":"Q4105792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$29691355-C12D-4E9A-9C21-3D76201B48FE","rank":"normal"},{"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":"Q1853167$684296FD-B7AB-40DE-8AC6-23E2FEC95B58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8c91f3e531d0087256bd01284f860adad823be3","datavalue":{"value":{"entity-type":"item","numeric-id":3021944,"id":"Q3021944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$19ABBBB8-376E-419E-9C3B-74068E23AA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b8425e8209e6312a4bbffa91ef01a2b5e5a251f","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$6A182765-2488-4D01-8C35-A6997593F493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd892181c3e615e393cab5bfa821f8fa2f710cad","datavalue":{"value":{"entity-type":"item","numeric-id":1318694,"id":"Q1318694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853167$79690D7E-D42F-4BF4-8FF8-5A8BBFEBB4D2","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"ecfee339e572cc71b455319a75b31e2e6ddbe7f8","datavalue":{"value":"journals/ipl/DomaratzkiPS02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853167$6E7D749B-C345-4528-ACF0-E800ABD30F58","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c35bc783702202851f3258d0362c962a50d401e7","datavalue":{"value":{"entity-type":"item","numeric-id":930285,"id":"Q930285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb43a644366f19f93b9153bf2038f227ebfbb2b8","datavalue":{"value":{"amount":"+0.8782802","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":"Q1853167$AEE6C0B4-BF47-4E48-A408-FA80D6E9F036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3a6bce66475ab24dd4a7a5a49364ad297ec3b20","datavalue":{"value":{"entity-type":"item","numeric-id":4371017,"id":"Q4371017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"829ad0e3e1d7a223a0220c6c2247d12c6b4dd55f","datavalue":{"value":{"amount":"+0.8703316","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":"Q1853167$6BFA58BA-613C-45AA-911B-E2FA607D2042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3de7a797b98d43ab8eced4003d41715e357496b","datavalue":{"value":{"entity-type":"item","numeric-id":4418597,"id":"Q4418597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"375ca5395e8ff13fdc963eb45cbf7dc97deca83d","datavalue":{"value":{"amount":"+0.8652022","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":"Q1853167$7F22B071-648D-43DF-A006-907DCE071B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02b57c19bf12472ba0e1ebfe14a41680e7ea6e6a","datavalue":{"value":{"entity-type":"item","numeric-id":1575547,"id":"Q1575547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73e0798236d0282518c8717c3894ccef95decbe0","datavalue":{"value":{"amount":"+0.85573965","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":"Q1853167$757A27D9-885B-40C7-903B-61354943E3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"980e1afddf133f5bae5638b0a091cc6afaba20c1","datavalue":{"value":{"entity-type":"item","numeric-id":6100191,"id":"Q6100191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10265737563abfa6ae589d2e75478c3683cd047b","datavalue":{"value":{"amount":"+0.84609187","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":"Q1853167$04ED8735-4672-4551-B5E2-59536E109C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9775de5d43229c8409eec5cc3fb8c2e030e91fa","datavalue":{"value":{"entity-type":"item","numeric-id":4782102,"id":"Q4782102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d410f4a78aa347715fa300d30530c1767f1b14d","datavalue":{"value":{"amount":"+0.8448767","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":"Q1853167$CA0CCF23-5C3B-45CE-A6F5-64F11D17F911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62764c6a32c1e1c2db0a7cf727fac6222e0b697f","datavalue":{"value":{"entity-type":"item","numeric-id":6109584,"id":"Q6109584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47be8b2d08813db81e74d2aa2b281141eddb269c","datavalue":{"value":{"amount":"+0.8441049","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":"Q1853167$F671009D-7075-47E2-8E17-2101E7C1AB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dad93b1f7a30adf68ef24b7accf54c5214e9cfd8","datavalue":{"value":{"entity-type":"item","numeric-id":2805404,"id":"Q2805404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4276be55a9cf61ec3f3c274f0b3efbcffd7fd71a","datavalue":{"value":{"amount":"+0.8420383","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":"Q1853167$14A20875-1730-41E2-976E-1159BD76793B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Simulating finite automata with context-free grammars.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Simulating_finite_automata_with_context-free_grammars."}}}}}