{"entities":{"Q714828":{"pageid":716677,"ns":120,"title":"Item:Q714828","lastrevid":63766050,"modified":"2026-04-11T15:23:59Z","type":"item","id":"Q714828","labels":{"en":{"language":"en","value":"Lower bounds for the size of deterministic unranked tree automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6093045"}},"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":"Q714828$AB3F2792-B504-4AB0-82A7-8EA3AD3473CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bacd82c15cc1fabc0eed2e4b3b36db898ab97433","datavalue":{"value":{"text":"Lower bounds for the size of deterministic unranked tree automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q714828$FBA4E1A0-2F9E-4576-BF18-7A136EACB2E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e705258cefd7a72d9aec82d852ae80e3f1c5a7a8","datavalue":{"value":"1257.68099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q714828$4C2BCB69-A938-44D5-9AC5-27CF041BEB35","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86fbc3a6a8095f237b31a764137f9fa9b1423a02","datavalue":{"value":{"entity-type":"item","numeric-id":418802,"id":"Q418802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$6691BFB0-C19E-4ECD-A562-B2B0E84EF837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8455035442168fbb99576351474dec2ff822256f","datavalue":{"value":{"entity-type":"item","numeric-id":247255,"id":"Q247255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$902D2B17-A001-4204-94E6-4BEF6B32E6AD","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":"Q714828$A5001253-8872-475C-9423-5CA474024734","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"627a9c6691e92dc7a2f0927bf16af5db49918284","datavalue":{"value":{"time":"+2012-10-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":"Q714828$7802D247-3279-40C4-9A04-484D4DEE4B19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4b033fef223dab767e372284166e2a3b0bdde51","datavalue":{"value":"In an unranked tree a node labeled with a given input symbol may have any number of children. Therefore, the state transitions of a finite bottom-up automaton operating on such trees are defined by regular string languages over the state alphabet. These languages, one for each input symbol, are defined by finite automata. Hence the tree automaton has two kinds of states, the vertical states used in the bottom-up main computation and the horizontal states used for computing the vertical state transitions. Both the vertical and the horizontal behavior may be either deterministic or nondeterministic. In general, the deterministic bottom-up tree automaton with the minimal total number of states recognizing a given regular unranked tree language is not unique, and finding lower bounds for the total number of states is hard.   In this paper the authors give an improved lower bound for the size blow-up resulting from the determinization of a nondeterministic unranked tree automaton.","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$E8EA80DF-B754-4BEC-97EA-AAC1F07F7907","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$DD1D91EC-82ED-4F84-BFEC-A0E9D699A6DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q714828$17D9BFDD-66F9-4FC1-B5CF-06ACA9684A7B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f45871b79093c6f61763c98c21fe2cfa075d800d","datavalue":{"value":"6093045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q714828$AED81689-6ACE-4AA4-B987-BD2C80440AAB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7fe2f2415709197ca17d2732570ef76c1e4f0b0","datavalue":{"value":"tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$B1EFFF03-20F7-4CCB-AD5A-0778D63D4C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c83cce0405a1ac1a224c1ee76ae11be8d175baf0","datavalue":{"value":"unranked trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$062E0F31-C0C7-4805-8D7F-9473CEBDD114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a2bad4593dfa53b9bdf6d73901a5fbf0b67c8a","datavalue":{"value":"tree languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$1297F03B-601C-4B74-B26F-B597046BC4F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b10ab4d2fc75823309415cc3027a505ded7b2f","datavalue":{"value":"state complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$DD3A206C-D191-47BA-88B7-5B4D8E27E77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01d01ba0554735b278236b61d3de2db638b07c84","datavalue":{"value":"determinization","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$2808664A-E78D-484F-A54F-DCD7EC4A9FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q714828$E7B82384-4794-4F57-AB70-2EA9D528261B","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":"Q714828$E60AEEBC-9EC7-4958-92DC-4C2B07DABBCE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbe3e28e6f242ec26dc0302e306c2c14be574c00","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.03.043","type":"string"},"datatype":"url"},"type":"statement","id":"Q714828$C788C792-E148-46D9-A033-BAB92CC8D04B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"006397ecbe5e0352f431c8914109cb24c30f8e37","datavalue":{"value":"W2081745941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q714828$F145BBE6-24CF-4CFE-B54A-EFB0A3E447B9","rank":"normal"}],"P223":[{"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":"Q714828$ECE2D8DC-1981-4E4B-B97F-F48B41F4BF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76cea3542b5288cbcd214d35457615438e870af2","datavalue":{"value":{"entity-type":"item","numeric-id":5492917,"id":"Q5492917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$63A25B04-DF78-4121-94BD-8E45E6B0E26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320a3fcf055a065d4c34a245edc1e12c19483007","datavalue":{"value":{"entity-type":"item","numeric-id":2271462,"id":"Q2271462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$89CC8FB9-F519-4409-B50A-EEE7B7E576E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f6b3962d0b7810403b7eee71ced0a053db5765","datavalue":{"value":{"entity-type":"item","numeric-id":671381,"id":"Q671381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$D9FB710D-65EA-45C5-811E-F859A9D1E683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a214656dac4fa9fe492ef1497e5656980477b222","datavalue":{"value":{"entity-type":"item","numeric-id":5422234,"id":"Q5422234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$AC3D4401-E7AD-46EE-8692-AE47EAF53782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5659e3f1fc30cf8a1aac92fd2c1ed2783063f06","datavalue":{"value":{"entity-type":"item","numeric-id":3395129,"id":"Q3395129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$E8DB734A-AC9A-4B10-A873-FC1E1FBA81EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25671577fa4958887cecc5eb5572a0caef1b2663","datavalue":{"value":{"entity-type":"item","numeric-id":553312,"id":"Q553312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$3B0D5138-90CD-4E76-9151-03DEA336D354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f06e31eaae3e7c9bdc20c4ffadaf92d3ac9fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4337605,"id":"Q4337605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$528D6A46-01D0-4B35-8C85-0B6941E49067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2d2507304ab609ba2df7863cc2c442e53a20052","datavalue":{"value":{"entity-type":"item","numeric-id":5704377,"id":"Q5704377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$A8E590F7-3263-473A-9C5E-1BDDCD6C381E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53026eff20cf878e72e195ddde23952c6fed9319","datavalue":{"value":{"entity-type":"item","numeric-id":882435,"id":"Q882435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$C8EA3897-6795-4A18-A63B-A5DF196C8B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6daecdeac1d806d8c648d3cda27ee91c08d239cf","datavalue":{"value":{"entity-type":"item","numeric-id":1394797,"id":"Q1394797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$DDE53DA1-8763-452E-92D8-18257D288A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71af02a11f0cbe069e4ea9beb45ae622432bd444","datavalue":{"value":{"entity-type":"item","numeric-id":5638224,"id":"Q5638224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$6C606A67-0ADE-4EE4-B981-59D92CE05A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b84a7772f4e4c12b0b3b3b738ee9262293d5ae9","datavalue":{"value":{"entity-type":"item","numeric-id":3586113,"id":"Q3586113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$4EDDFAC9-10A2-4DD5-B15B-6A0DD4BCBB5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9aef6d2fc4673de3ca805226c09b547d05d8c55","datavalue":{"value":{"entity-type":"item","numeric-id":3100917,"id":"Q3100917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$1A945C1E-18E7-475A-93B6-B71478E0A6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7900a4f09af951f69e66031c48265b826745ce","datavalue":{"value":{"entity-type":"item","numeric-id":5200097,"id":"Q5200097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$55BC92E3-7F3F-4340-A518-4422622FF0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20571cead99fdf93edc76e3f012361321411cb1","datavalue":{"value":{"entity-type":"item","numeric-id":2891328,"id":"Q2891328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$ECC62862-327A-44F2-8D3F-64F0268391FC","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":"Q714828$4FFD03A8-09BB-438A-BE1F-F52920C601AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bbfee710cd8daecb146a3d2aed41fcf26202fdb","datavalue":{"value":{"entity-type":"item","numeric-id":3004607,"id":"Q3004607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$30A693AA-4786-4B69-AF5B-B7C79DED97AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beb27b7af34ab0402f1db377455dec0d9d637933","datavalue":{"value":{"entity-type":"item","numeric-id":878749,"id":"Q878749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$4FCA88DB-023C-466B-A7AF-51C3DD13D3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f99d516f03f630b465144bf2edfacff7e586661f","datavalue":{"value":{"entity-type":"item","numeric-id":3549457,"id":"Q3549457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$1E5E085B-E019-4B99-84F4-8588F7A6570B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caa22c2a09da29028b32fbdec6997075843df5fa","datavalue":{"value":{"entity-type":"item","numeric-id":3698326,"id":"Q3698326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q714828$85C876C7-EFF6-40BF-BBE2-1B65A931DE60","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c12e7239fc0a54d025c8e445f3f9ced4bd0dddc9","datavalue":{"value":"10.1016/J.TCS.2012.03.043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q714828$8FC2406E-C061-4407-95B3-51AFD1308B2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1c7039b4541d62af623adb3c92ec311f1e3f2b0","datavalue":{"value":{"entity-type":"item","numeric-id":5200097,"id":"Q5200097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80b069b984be15f374c121760d09004849f270f7","datavalue":{"value":{"amount":"+0.8672630190849304","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":"Q714828$23CE57DF-01AC-42A1-9820-FDCC11D4EA54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01573a9238d105d036758867a1587119ee2e9bbe","datavalue":{"value":{"entity-type":"item","numeric-id":5492917,"id":"Q5492917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f3bf664f3c04e97a404274ad4059c937b5ffd46","datavalue":{"value":{"amount":"+0.8573076725006104","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":"Q714828$2C633626-8C52-48F3-8238-5C45867404D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00184f6c36606ff3b74698493e0fe535662009c7","datavalue":{"value":{"entity-type":"item","numeric-id":3100917,"id":"Q3100917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa834d0f92350f7207905a643fa94f284ce2bd32","datavalue":{"value":{"amount":"+0.829535961151123","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":"Q714828$910269D9-8F39-4EA3-8775-158B247C513E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20de04992f1b5f951d3338fefb2351f506ecbf4b","datavalue":{"value":{"entity-type":"item","numeric-id":4964021,"id":"Q4964021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"185a09b5a3e4c896d464e9db647ff2ff54407f12","datavalue":{"value":{"amount":"+0.8280697464942932","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":"Q714828$C86D3FF6-8870-4597-B2AC-65C9318DC22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9706156998e8df55cccf04d13f79f22b26670a0","datavalue":{"value":{"entity-type":"item","numeric-id":4964022,"id":"Q4964022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c34b831bd0ed721ac4f4bdfbb08f8afc62390323","datavalue":{"value":{"amount":"+0.8250390887260437","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":"Q714828$89C7BC6B-0C2F-4707-B8DE-AEBB2ADA505B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for the size of deterministic unranked tree automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_the_size_of_deterministic_unranked_tree_automata"}}}}}