{"entities":{"Q2641868":{"pageid":2652611,"ns":120,"title":"Item:Q2641868","lastrevid":50150513,"modified":"2026-01-13T06:57:15Z","type":"item","id":"Q2641868","labels":{"en":{"language":"en","value":"Minimizing nfa's and regular expressions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5182130"}},"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":"Q2641868$72D7271B-29EC-4972-BB3C-0C290F26D5D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6bdf418b1bc266abb2f2c84d9f7e4b4d830b0d9","datavalue":{"value":{"text":"Minimizing nfa's and regular expressions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2641868$E31B8924-F6D6-47E9-9662-9FF1EC26AB33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bbfbaa4c2be0ae323d690713047ec3babf48e3f5","datavalue":{"value":"1152.68459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641868$BA17F80D-EE76-406C-84FF-ED15A22E82AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53fe8816f4fcc577cb10a1338bf0d4b157652e0f","datavalue":{"value":{"entity-type":"item","numeric-id":2641867,"id":"Q2641867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$E9A121DD-133C-4945-AF82-E8C5C6A92BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea84784d0ec02c56a3f38dfe8d621cdc682004f","datavalue":{"value":{"entity-type":"item","numeric-id":436320,"id":"Q436320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$5349376E-0D2B-4E8E-8BE1-AA624E3225AE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$F006D24A-0973-426F-8913-E681751E7B0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"226fad3e536b676c763bdce84a93ee9c766c4ae5","datavalue":{"value":{"time":"+2007-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2641868$7180BBCC-C2A4-47EF-9D09-70EFD280BE2F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3cd141855fe6dae2bb8188767da330e10d54b79","datavalue":{"value":"We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as of regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's). We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, respectively symbols within the factor \\(o(n)\\), unless P=PSPACE. For the unary case, we show that for any \\(\\delta>0\\) it is impossible to efficiently construct an approximately minimal nfa or regular expression within the factor \\(n^{1-\\delta}\\), unless P=NP. Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least \\(\\frac{n}{poly(\\log n)}\\). Our setup also allows us to analyze the minimum consistent dfa problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641868$7FC8E80C-C9B9-40E9-A41E-88BC6F413771","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641868$6EF24C36-2D8C-43DA-AB13-37D6251C660C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a764142c81d4740571dd9367129823402c3aa2e1","datavalue":{"value":"5182130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641868$6693C051-13ED-4DD3-86DC-558453CCB590","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c9735f1167df766bb7e33e6d0f45c52d40ede0c","datavalue":{"value":"automata and formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641868$EA08E926-38AA-4324-BB60-A44D089D8621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641868$E9640A71-3BBE-40E4-8384-3B427C7B3AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762537bc50f732e72b5a90a6c8258b47ac0f486c","datavalue":{"value":"approximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641868$90C0A962-8822-4BCB-AC0D-9D8E90393317","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":"Q2641868$6D167EE9-6683-41F0-A1AE-749E0411A045","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e923adb55a2981c10d63b7f2564ef0449bf54597","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2006.11.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q2641868$5153D44A-BA5A-43AF-9D5D-19E28B6F43FA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b837856372c9b1db657bc598c6b557a0ee7a0cc","datavalue":{"value":"W1979603834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641868$9E649F05-2394-4F13-8C9C-73546CE39FE1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c82703cb3a78d0ce31c2351c8c1c3a26f8f4dbc","datavalue":{"value":{"entity-type":"item","numeric-id":703569,"id":"Q703569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$AD19F770-B579-4649-8163-28C55030E785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e87fcd7dd4f79e0eafa1a59a3bba175b24806b","datavalue":{"value":{"entity-type":"item","numeric-id":4465333,"id":"Q4465333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$3EE243B1-5DD3-41B8-ACE6-14FFBCC4A929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"289b3f54ed329da6aaad3f6a36f2c6d4055862bb","datavalue":{"value":{"entity-type":"item","numeric-id":5431333,"id":"Q5431333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$A907FE93-583D-467D-BA35-F8C5A3A56CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a27dc96f0a65e06d5ffc24907f33faeedbabbc5","datavalue":{"value":{"entity-type":"item","numeric-id":5710693,"id":"Q5710693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$138170B5-6F04-45C1-B34E-1D499300AC6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7c21f7dc6f1a4b31896afb5d675fe5a2882d1b1","datavalue":{"value":{"entity-type":"item","numeric-id":5894870,"id":"Q5894870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$A668C9E0-A2BF-4F04-9C21-499CE3A0CED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"677e10984800b2f973ce1edcd5a2f197d9d5da43","datavalue":{"value":{"entity-type":"item","numeric-id":1426009,"id":"Q1426009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$5D1B10F9-4506-4B7E-B21A-91A6AF99F5A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3fee3ee46b51000f961ccdbb8be1668a3d108bf","datavalue":{"value":{"entity-type":"item","numeric-id":3988841,"id":"Q3988841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$3A987EAD-857D-4C18-8901-93CE81D01FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e78d7d44652f20c2a60f72580420d04a08808e1","datavalue":{"value":{"entity-type":"item","numeric-id":4277533,"id":"Q4277533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$0FDDA8E3-0720-4FA4-82E6-B2173F76D5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a84fe142876319c1801d90692f9f0fb104b1ab44","datavalue":{"value":{"entity-type":"item","numeric-id":4299296,"id":"Q4299296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$2B70D55A-44AA-488B-BDB4-2374694161D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb4f323569dfef40dd6c84aa4c1dcfafbbf33988","datavalue":{"value":{"entity-type":"item","numeric-id":3168269,"id":"Q3168269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$DD3004BB-6072-4AE9-A83F-5C29A89E0A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf27812a5724375e81a15961b928aa4c95d98a91","datavalue":{"value":{"entity-type":"item","numeric-id":756441,"id":"Q756441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$16F83489-5677-483B-BD99-C5FA133A2ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9598998e9f1a9f08566f0ee3680c46f1431959ba","datavalue":{"value":{"entity-type":"item","numeric-id":4033836,"id":"Q4033836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$20669D2E-DF88-4FBD-AA69-72A71ED0A706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072e91014367104cf566b8b67a728f68b171a4bc","datavalue":{"value":{"entity-type":"item","numeric-id":5906823,"id":"Q5906823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$68973B66-79C1-423E-9980-7EDC14A683BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641868$0B3DB044-03DD-4388-BFD3-AB47D8D1097D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a711d9b969cbc65e67db0f7c91c3d0d4c346e26","datavalue":{"value":"10.1016/J.JCSS.2006.11.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641868$135CF66B-91A1-455F-A582-5C451D9A4A1E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51051b4c05bc494c71eecb5dbeddd247bf704652","datavalue":{"value":{"entity-type":"item","numeric-id":5710693,"id":"Q5710693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b95c3a8b0a9b9ca198160cb5a07475bdd6b6b18","datavalue":{"value":{"amount":"+0.9910880327224731","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":"Q2641868$E5E58669-3F7B-440E-B720-6A54C7F5B05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7f6bd9ff85ac88f689a03fa36d504b45b22981d","datavalue":{"value":{"entity-type":"item","numeric-id":4033836,"id":"Q4033836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06df4754015732eb25cb754f1a1126fc48c0205d","datavalue":{"value":{"amount":"+0.8629757165908813","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":"Q2641868$03385748-0AFA-4EB8-A2AF-52B8EBF32511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99099b4a9a28928f7d38b3a12fd29467384e7372","datavalue":{"value":{"entity-type":"item","numeric-id":3988841,"id":"Q3988841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f0304ec0a7983353e793b8df59e6b779cd917c3","datavalue":{"value":{"amount":"+0.862237811088562","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":"Q2641868$F4DAF350-FF40-41E1-AA57-3BF08BA7C523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2601df53cdb120e5c1aa1427a425ec0fe0e545cc","datavalue":{"value":{"entity-type":"item","numeric-id":3532998,"id":"Q3532998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e291188ad0f2737977f963617348ca8b5164b5ab","datavalue":{"value":{"amount":"+0.8545229434967041","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":"Q2641868$EDC3AEA9-096C-41AC-BE81-424C1A24F8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281714197287e59802b6b45bab6a1ec17c5a21fe","datavalue":{"value":{"entity-type":"item","numeric-id":414869,"id":"Q414869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f61a877872b4b1ed63590ba74f5bb1b0133ab456","datavalue":{"value":{"amount":"+0.8399096727371216","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":"Q2641868$3832579E-8154-4FC8-A1CE-522635C497C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2641868","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2641868"}}}}}