{"entities":{"Q1068549":{"pageid":1079301,"ns":120,"title":"Item:Q1068549","lastrevid":66205815,"modified":"2026-04-12T08:15:13Z","type":"item","id":"Q1068549","labels":{"en":{"language":"en","value":"Succinct representation of regular languages by Boolean automata. II"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3932398"}},"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":"Q1068549$516AE8A1-7EEF-4D0B-8AD9-1D985ED8DCA0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8513aa1763304e2567d7be56e8b348b8b035cd81","datavalue":{"value":{"text":"Succinct representation of regular languages by Boolean automata. II","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068549$022C67A3-05F8-4207-9BDA-B4264573657E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2e6de97a5e3c21787553f3e35135695620282796","datavalue":{"value":"0582.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$FDA205D2-D72B-4FDA-B1E7-F280ED0EA7EB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"49527bd334e6d6774eb7b2373102ac20e4ea5d2b","datavalue":{"value":"10.1016/0304-3975(85)90215-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$904C766D-075B-4747-90FE-54B6DACC84DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$09288FE9-4EC3-4783-A8BD-32189C3CB819","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1068549$D27348A4-B711-49AC-AE42-4C2911D74799","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c11b04437a357198611538367af98e907a99c9e1","datavalue":{"value":"Boolean automata are a generalization of finite automata in that the next state (the result of the transition function, given a state and a letter) is not just a single state (deterministic automata) or a set of states (nondeterministic automata) but a boolean function of the states. Boolean automata accept precisely the regular languages; also, they correspond in a natural way to certain language equation involving complementation as well as to sequential networks. In the first part [ibid. 13, 323-330 (1981; Zbl 0458.68017)] the author showed that for every \\(n\\geq 1\\), there exists a boolean automaton \\(B_ n\\) with n states such that the smallest deterministic automaton for the same language has \\(2^{2^ n}\\) states. The present note continues this work by giving a precisely attainable lower bound on the succinctness of representing regular languages by boolean automata; namely, for every \\(n\\geq 1\\), there exists a reduced automaton \\(D_ n\\) with n states such that the smallest boolean automaton accepting the same language has also n states.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068549$052B872B-182A-4E8A-B124-F579A60A0B9D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$28CF66C6-8ECD-4D66-8F5E-6C19AA377E3D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04c586c36e4fcffafebd1635b7ec2ddab4128d05","datavalue":{"value":"3932398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$984ABBA2-3139-4634-A777-4188ACAA6CED","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a765e14474ea87f3f2bf326bf166aa1013a8104d","datavalue":{"value":"Q56550598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$5BE0C86B-2511-4BAC-A0FC-AC9C7DD63AB8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2d1b1de458b5286a1fb74f71cf3fc8f09d83854","datavalue":{"value":{"entity-type":"item","numeric-id":386048,"id":"Q386048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$8961604D-36D6-4C1F-AF64-6D087A3A1233","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":"Q1068549$06924C08-83EE-4D5A-8D32-5D4E767260D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b7950b436613dbb8ce59e3d9db4755ab1c3cbf88","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90215-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068549$D4509FB4-8E6B-456D-8DC8-1FCC4E522AEC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa8894153191a54d988767c35a51ef304e911b62","datavalue":{"value":"W4231305083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$3C63B19F-A589-47A5-A8E7-51B8C65E2FCF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe955fb7f9026c48a3b74bf365e86ce77d5a2f05","datavalue":{"value":{"entity-type":"item","numeric-id":5725992,"id":"Q5725992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$5FED1D39-2D91-430A-96D1-DEBB3ADB424A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5533d056fe8b5f03876ad0811b874f1e1fe1c396","datavalue":{"value":{"entity-type":"item","numeric-id":600253,"id":"Q600253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$FDDC0581-3151-43BA-BEBF-2EEC97A8A010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c364902deabefaaf4675cf6de45f9c70ebf6a4fa","datavalue":{"value":{"entity-type":"item","numeric-id":1149791,"id":"Q1149791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$30AABCBD-305A-46E4-AD0C-BBD8BF0F70FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6550549f6a6ae41859a83760194e81ec3591e36","datavalue":{"value":{"entity-type":"item","numeric-id":1151754,"id":"Q1151754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068549$E323FA6C-ACB5-4166-9393-82BE5014F1C5","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"4efbfe3c2f5b4be560c0ef580a71a519ec05b0c0","datavalue":{"value":"journals/tcs/Leiss85a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068549$1CCF9876-1B20-42C5-8129-5E3A75561FED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"909fc54f224113f0ca88aa1c5dd1d3ac048d80ec","datavalue":{"value":{"entity-type":"item","numeric-id":4994955,"id":"Q4994955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0575bd4760c43a04e6b60548a423d716d116ed3d","datavalue":{"value":{"amount":"+0.7824614644050598","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":"Q1068549$8990C0E2-38BC-4A71-B61E-1D9F39393868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24f498ca4ba88ec39727ef6be3a9251fa8a17ef4","datavalue":{"value":{"entity-type":"item","numeric-id":1101207,"id":"Q1101207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"216899cea652545ea55a233aacdc2efde5b71cd8","datavalue":{"value":{"amount":"+0.7695333957672119","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":"Q1068549$610B7E3E-D0AC-4DE9-87A9-2801349FEDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5fce29ab4073ce77a0773887d966a002cdd16c5","datavalue":{"value":{"entity-type":"item","numeric-id":5205045,"id":"Q5205045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a4813e438146bd1f924edcecfdc59215cab4e5d","datavalue":{"value":{"amount":"+0.7665233612060547","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":"Q1068549$8CC4EC22-816E-4F32-A7E4-93B6F3B7BA12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b610d7a388ac5f5e5aec2ee09a738588a9446a05","datavalue":{"value":{"entity-type":"item","numeric-id":1625163,"id":"Q1625163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39c86782d97db8569e8b9e4cbb03ff8a0a6e1535","datavalue":{"value":{"amount":"+0.7663314938545227","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":"Q1068549$E0D8DFA7-6246-49A4-9AA9-394F3C635090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"741ccdceb13b58e719678e13427a803cae19b88c","datavalue":{"value":{"entity-type":"item","numeric-id":2401004,"id":"Q2401004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d68365e8f1fddba73c017d8ddad5e98c2937d03","datavalue":{"value":{"amount":"+0.7558786869049072","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":"Q1068549$32845C13-A1B1-45BB-A8B0-129054668624","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Succinct representation of regular languages by Boolean automata. II","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Succinct_representation_of_regular_languages_by_Boolean_automata._II"}}}}}