{"entities":{"Q1190464":{"pageid":1201213,"ns":120,"title":"Item:Q1190464","lastrevid":66517638,"modified":"2026-04-12T10:36:55Z","type":"item","id":"Q1190464","labels":{"en":{"language":"en","value":"Minimisation of acyclic deterministic automata in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 55525"}},"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":"Q1190464$F119A450-ABBE-4204-8B71-C8727CE11550","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a719c47dd613f5a03c0ad604da65cfcb099ce47","datavalue":{"value":{"text":"Minimisation of acyclic deterministic automata in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190464$90CFE211-F99A-4BA1-B24C-A5F5F7FEFA7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"005390e0cf0ae06571388ceb48c02ffe56c8c832","datavalue":{"value":"0759.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$C3180B19-663E-4001-BA71-8C989BE6A01A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"040b777c0dcd68b25e4fb2e07280a6b96b14208b","datavalue":{"value":"10.1016/0304-3975(92)90142-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$72A43831-3E7F-44DC-9358-A48086FB1905","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5636caa9c01358db7a33a44a9168a4574ce6000","datavalue":{"value":{"entity-type":"item","numeric-id":1190462,"id":"Q1190462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$5E361B71-CBE4-49F9-8C62-5A9FB4F54E5A","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":"Q1190464$2F71DAA6-9FA6-4FA7-9419-162CFFCD8FBF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9b40ce89936be2de8343a01d1ced7ff59f76b3e","datavalue":{"value":{"time":"+1992-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190464$D2DF87CB-9C02-42DB-80AB-BEF07D84ADE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8fd5577126a126834343e9bff158f8986badb74d","datavalue":{"value":"A deterministic automaton is acyclic if the underlying graph is acyclic. Two automata are said to be equivalent if and only if they recognise the same language. If \\(A\\) is an automaton there exists an unique automaton \\(M\\) minimal by the number of states, recognizing the same language. An automaton with no pair of equivalent states is minimal. The minimal automaton for a given language \\(L\\) is the unique automaton with the smallest number of states among those recognizing \\(L\\).   The author presents a linear algorithm for the minimization of acyclic automata. This algorithm can be used, in particular, on automaton representing lexicons.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190464$72C846EA-A84F-40C2-8A49-E6163740D042","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$81272E60-1E4B-4F00-A65E-7EF2C4CC478D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$1938A972-B2BA-4D21-A5DC-D57AF6BD402E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f4d3126d2327a164f3b143cb653a4e40a6765d75","datavalue":{"value":"55525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$AF1A90F3-1558-4CFE-A19B-D6BC10CD902A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"207f10c4b49e7a8185ccd53556264d79bbc60a2d","datavalue":{"value":"deterministic automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190464$565FD174-DC26-412E-998A-40983D659FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1279221fe7735b1b47afd1411b335eca7e3f0e","datavalue":{"value":"minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190464$A84FED95-62C5-453E-B8EF-31AEDC5CBB5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a7dd648682c9f449fcdc117b0be0469821008fb","datavalue":{"value":"acyclic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190464$4EA756F2-C785-46F3-9E1E-72670114949F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9562b75d48d8702f3c8d361f7254e70829af4778","datavalue":{"value":"Q56048077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$A9E9F431-14C9-42B2-BFDE-801B7F232EB7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"772ac58ef64cff0179116c137ebd3ac0033485d5","datavalue":{"value":{"entity-type":"item","numeric-id":949813,"id":"Q949813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$F922D593-88C6-4920-B5E9-DCEF82B9644D","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":"Q1190464$B8ABED2C-20D6-463D-82AE-3DDCE6FBA355","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"35057cf9eb1c2527209841a2839075e07721651d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(92)90142-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190464$2D047D41-6E82-455A-AD91-076931DF6EA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ddb96e9f68a0d6d9cf18cf3c0ea2c8dd6fba582c","datavalue":{"value":"W2070830131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190464$A7499E11-D4EA-469F-838A-4F619A41D81A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$EEB8E587-CDCD-4817-B2DD-1E67351B51C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d0863918228d158fae088a6efc6f79f2c8e8057","datavalue":{"value":{"entity-type":"item","numeric-id":3724245,"id":"Q3724245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$26B43273-31AF-4CA7-B47E-225B6B6B5F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12e19f5649f447c901608ec27ab70de717baeb33","datavalue":{"value":{"entity-type":"item","numeric-id":1161293,"id":"Q1161293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$42F72BFD-B353-455F-B63D-DA4C766549A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$7AE3C845-F7D7-46F3-9B5A-AB4C212D34C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9279cb0155a09e2e81787116515cfe1e304a87c6","datavalue":{"value":{"entity-type":"item","numeric-id":5551191,"id":"Q5551191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$AC908855-0BA2-4F6A-955E-FA6EF95C4151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$5A4A25A0-A6A0-4E26-92AC-0AFD353065CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"027a170d6c137febe9630c9215be9b24dde92ee3","datavalue":{"value":{"entity-type":"item","numeric-id":3239817,"id":"Q3239817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$AD31171E-2619-4629-8F7B-AA2133E7A874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65fa25ecef461a83ce03679a7bacb00b33cb4090","datavalue":{"value":{"entity-type":"item","numeric-id":3801084,"id":"Q3801084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$B09286C4-AC88-4FCD-ACAE-5031E54E9D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107b480decc678c92b78dee11f4a9915c90692b","datavalue":{"value":{"entity-type":"item","numeric-id":5541339,"id":"Q5541339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190464$FB5DEA75-1B6E-4826-B1F3-4186CC31FEF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61ffa1534f6c0184b4827b91751ac372c7e7277","datavalue":{"value":{"entity-type":"item","numeric-id":496535,"id":"Q496535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de9e8b1fd183024c5aba290d92061ce76cc9f435","datavalue":{"value":{"amount":"+0.87852543592453","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":"Q1190464$91C2608B-B960-4646-90DE-7436427D4C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77c7fc99d7503babb56d886e6874483431dcccda","datavalue":{"value":{"entity-type":"item","numeric-id":5422246,"id":"Q5422246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"455e98cb80bf4803dbf3e6b9196376c95b92e825","datavalue":{"value":{"amount":"+0.8207328915596008","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":"Q1190464$A4F8D667-BC60-44C3-AC47-86A5575572C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efe234da41ec3523394a1a18fba18052a8887944","datavalue":{"value":{"entity-type":"item","numeric-id":2489949,"id":"Q2489949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e62f4d47475b9c475fa1606eed1961a0c03b0841","datavalue":{"value":{"amount":"+0.8192793130874634","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":"Q1190464$E7852CAC-06F5-4EE9-A586-0FB24C75C42D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e30879256dce487c083da85bd962c982df2940c5","datavalue":{"value":{"entity-type":"item","numeric-id":3365579,"id":"Q3365579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b59d05a9fd280d20ab3f81af2fbbaef9d0402520","datavalue":{"value":{"amount":"+0.8149402737617493","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":"Q1190464$8CF7C956-B706-401F-AE97-3642A82473D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c5dcea73d4732bc1392e0237ae216bd661ab85f","datavalue":{"value":{"entity-type":"item","numeric-id":1426028,"id":"Q1426028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27136ecb37b4ac5d59caee286ad87c5df754b1d8","datavalue":{"value":{"amount":"+0.8091769218444824","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":"Q1190464$2684ED9B-8735-4030-A1D9-39167760E07C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimisation of acyclic deterministic automata in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimisation_of_acyclic_deterministic_automata_in_linear_time"}}}}}