{"entities":{"Q703578":{"pageid":705427,"ns":120,"title":"Item:Q703578","lastrevid":63745383,"modified":"2026-04-11T15:15:28Z","type":"item","id":"Q703578","labels":{"en":{"language":"en","value":"Minimizing finite automata is computationally hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2126133"}},"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":"Q703578$FABCEC17-04CA-48C4-8539-7F308DC0B19A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ca6fd20cce8b204a6e9d31c416a7d766700d0b0","datavalue":{"value":{"text":"Minimizing finite automata is computationally hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q703578$7B51E4DF-2684-45CE-9C28-B57647F3EAC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6f35a41d78b93812fd791690e97b62da711522a","datavalue":{"value":"1071.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$9DD83084-678C-4B89-9E2A-C0473A36F9E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"43e5b44684a6cc8af75870784fb52a5ba3f9758e","datavalue":{"value":{"entity-type":"item","numeric-id":383363,"id":"Q383363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$BAB0B0AD-B3BD-4626-AFFE-E2EE6259069C","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":"Q703578$C8891380-6510-4EF2-903A-7C8150158673","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64fc1bb835ad7d7e19dde657c65db04a5fd1cde0","datavalue":{"value":{"time":"+2005-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q703578$F51D54C7-E525-4387-AC59-8B366E611A04","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$FEE001D4-D250-4F9C-845C-2FE834B48456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$C2135AA2-391D-496A-A3ED-A3A1F08B7427","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0aa1b6291d0f48d1fbb302a557d884de52da606a","datavalue":{"value":"2126133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$61B2C4A4-1207-416B-B80B-B8482A76D12C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7c74c5552698bc5f1378c74a5f1a3f533d21987","datavalue":{"value":"Finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q703578$6F14C238-1267-4D8F-9A81-35A8EA4FD07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f7d608b7bd6af32451c6c72eda7faea4229edeb","datavalue":{"value":"Limited nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q703578$9B42014D-F13A-44BC-A0B0-627EEB6640C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ce38741fa0940ede05db11cba207307a91e14d5","datavalue":{"value":"Minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q703578$2AFEF2E1-4B79-44AB-8B5E-C7A3DB76F0D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q703578$0674D8EE-862F-4837-910D-607539B3706B","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":"Q703578$299922B9-A5AE-474A-B7C1-102CC461D866","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a99eadafab50bf11112776cd746808c278cfa14e","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.03.070","type":"string"},"datatype":"url"},"type":"statement","id":"Q703578$B4CE8346-A742-488A-8BC1-A222D5ABE58D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d635266a44d16c251b188aa99ba69fe723c67b68","datavalue":{"value":"W1964127120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$13DEBDD9-B53F-4F5D-9C02-DE691F9EC6DA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$480C707C-60BB-4581-9EF3-7C6EBC3657C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32388ea5638d0e1edfae4d039429e58846b1cbf4","datavalue":{"value":{"entity-type":"item","numeric-id":1845859,"id":"Q1845859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$F50B2EBC-EAD4-468F-AFC1-5FC4E8C336A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ab91af9300c03108c83f175294005fece9bfeff","datavalue":{"value":{"entity-type":"item","numeric-id":4153610,"id":"Q4153610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$C3A596C7-1836-4E43-830B-A6AA2FA1946C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f56e7c09b71d6e6794c7b6bdb13ce75c77a19e4","datavalue":{"value":{"entity-type":"item","numeric-id":912641,"id":"Q912641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$FF4D74F2-4955-4F0B-A06F-DF0791778569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8849b41b10a4381a4de7dd81114a45d1ffea3b1","datavalue":{"value":{"entity-type":"item","numeric-id":4531373,"id":"Q4531373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$0495841A-BBE7-4395-BF0A-DC0B4EA733A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be2ce44bdf80df52f5a97dfe72ac01ea51570a9","datavalue":{"value":{"entity-type":"item","numeric-id":4045961,"id":"Q4045961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$CD5858CA-4C61-4E78-8190-4FB8FD572F83","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":"Q703578$BE7E47E7-BC6F-4225-83E6-6CF22B2ACF1D","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":"Q703578$7580ABCA-6837-4C2C-9A49-AF9042E0FC14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$6D8EECEE-62A6-40EF-90B9-72F74286DE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d396cb7909eb8ef7cf9892a2d4d1be562fcbdc7","datavalue":{"value":{"entity-type":"item","numeric-id":4109298,"id":"Q4109298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$69DB0B9B-5DDC-4C30-B660-2B79DB64A3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"971679bdf7cbd095011d431a823cf403c3425242","datavalue":{"value":{"entity-type":"item","numeric-id":4503150,"id":"Q4503150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$D360389D-391F-4462-81E1-DDCC007E08E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ea2e682b9c0dabf93e8bde92af2ec08d19a46be","datavalue":{"value":{"entity-type":"item","numeric-id":1134517,"id":"Q1134517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$4FDF52F9-5CB0-4371-A5FE-E3B2B22B707D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"005a72c1edeb14a152d3d24ef383c7204eb6ae58","datavalue":{"value":{"entity-type":"item","numeric-id":1271338,"id":"Q1271338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$48231513-B2D4-487E-84A7-54BB8490F9CB","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":"Q703578$AFD52EAC-D965-4C8A-9ACA-3E84B81FD3E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703578$74309B72-BF30-4CDD-B735-6625BD992FE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aaf2a45a1cfe093a091099aa51fe74249d3bca3c","datavalue":{"value":"10.1016/J.TCS.2004.03.070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703578$FF4B3E32-85B2-4AAA-8BBC-B7E3986E62B7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"355f749d8b6cc6533dc776ebcaa3b35ab9ffedca","datavalue":{"value":{"entity-type":"item","numeric-id":4452078,"id":"Q4452078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7548083310fa9090596f09ebf2239c3daf07ac6","datavalue":{"value":{"amount":"+0.9963061213493348","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":"Q703578$E802F28D-ADB3-4CF0-A22D-E9134AEFCD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5975dc09d73095710e16012ad1990b07bf743b36","datavalue":{"value":{"entity-type":"item","numeric-id":4036599,"id":"Q4036599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ad7b17bfb602ab9c4ec0b141fd4abaeba113ba6","datavalue":{"value":{"amount":"+0.8787203431129456","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":"Q703578$E85BED75-4521-48BC-87C6-236AAE62462F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67230df40e3d3d1f5cec3a129fd9fe46d85a050c","datavalue":{"value":{"entity-type":"item","numeric-id":3832058,"id":"Q3832058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ad7b17bfb602ab9c4ec0b141fd4abaeba113ba6","datavalue":{"value":{"amount":"+0.8787203431129456","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":"Q703578$3D5C944B-05DF-49A0-A90B-E5C3391E17DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"048183140c44732c3eaed0a207c927f65c9c6b56","datavalue":{"value":{"entity-type":"item","numeric-id":3520301,"id":"Q3520301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"065d1f31db09bc4e5827f43c05cf16afa50f5fdc","datavalue":{"value":{"amount":"+0.8768031597137451","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":"Q703578$B20ABDA8-FC16-48BB-8EDB-1637057C8335","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":"128fb7bab120351cdb28323d77a96eb028acc637","datavalue":{"value":{"amount":"+0.8670961260795593","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":"Q703578$2BF76F5D-8478-476A-9416-A6975C835261","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimizing finite automata is computationally hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimizing_finite_automata_is_computationally_hard"}}}}}