{"entities":{"Q2343138":{"pageid":2353881,"ns":120,"title":"Item:Q2343138","lastrevid":52254110,"modified":"2026-01-21T06:40:56Z","type":"item","id":"Q2343138","labels":{"en":{"language":"en","value":"Checking determinism of regular expressions with counting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6432712"}},"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":"Q2343138$E9A2DBD5-76C3-4AE4-8272-65FCD086C32A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d0dea667e8720d9cad7305331dfce27a26f50f8","datavalue":{"value":{"text":"Checking determinism of regular expressions with counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2343138$A1BFF955-FFDF-43FD-81D5-67ED2FDDFBE4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"77b7e9856515a08e4c8260ba0bf257c30fa7588b","datavalue":{"value":"1330.68151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$6D424303-787E-49E0-8024-6C1D84C9524F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c726ca44d8b29953a360b291f7d3727b22939a07","datavalue":{"value":{"entity-type":"item","numeric-id":208299,"id":"Q208299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$7254C849-12EA-47E6-9111-4806245049F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a7b7fb7cd82e8d3f5ccd130a1f0c1cc04179e6b","datavalue":{"value":{"entity-type":"item","numeric-id":493649,"id":"Q493649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$12B2184E-E091-4D43-AF73-18FD10E12BD4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$D73F65B8-1A43-49D2-AA58-D107DA1098A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c3d99bc4b033c565fb0342435936dda6246db079","datavalue":{"value":{"time":"+2015-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2343138$A2B268D0-072C-4975-90D4-17CBC42079D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"76ce8422a75bc7711ba560c25897bdfe8e7bd70f","datavalue":{"value":"The paper is concerned with improving the worst-case run time of regular expression determinism testing algorithms. In particular, improvements are made with regards to regular expression counting operators. Complexity of \\textit{matching} problems is not considered.  Informally, a regular expression is weakly deterministic if, when matching a word against the expression, a symbol can be matched to only one position in the expression without looking ahead. A regular expression is strongly deterministic if it is weakly deterministic and if the operators appearing in the expression can only be used in a unique way when matching the expression with a word.  Based on earlier works [\\textit{B. Groz}, \\textit{S. Maneth} and \\textit{S. Staworko}, ``Deterministic regular expressions in linear time'', in: Proceedings of the 31st symposium on principles of database systems, PODS '12. New York, NY: ACM. 49--60 (2012; \\url{doi:10.1145/2213556.2213566}); \\textit{P. Kilpel\u00e4inen}, ``Checking determinism of XML schema content models in optimal time'', Inf. Syst. 36, No. 3, 596--617 (2009; \\url{doi:10.1016/j.is.2010.10.001})], the authors generalise linear-time determinism testing algorithms established previously for standard regular expressions onto regular expressions with counting. The paper culminates in presenting an \\(O(|\\Sigma_E| |E|)\\)-time algorithm for checking weak determinism of regular expressions with counting, and in presenting an \\(O(|E|)\\)-time algorithm for checking \\textit{strong} determinism of regular expressions in that same class.  The results will find applications in the analysis of XML content models (weakly deterministic as per a W3C requirement) or queries over XML streams where strongly deterministic regular expressions are naturally found.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$79FCC2DB-2D94-4776-9C84-297BA85D853A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5c634a7a610dc4a60ec0b802b8dd89a79b8a3056","datavalue":{"value":{"entity-type":"item","numeric-id":588686,"id":"Q588686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$97133ABD-7DF4-47A0-9B73-B49DC6BA52A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$6D8D5CDF-A269-43C8-BEAD-70C012047449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$24FC3BBD-A23D-40C6-9C7C-A9BE91E98192","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9061794ac08366ff1c3bb7e8806081b097f4017e","datavalue":{"value":"6432712","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$795C7633-FBE6-4E50-A133-9534DFC7CF92","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bc7fb0f3b4f20438957915b111172d48ee2fa4a","datavalue":{"value":"weakly deterministic regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$419AA535-2A6B-4688-96DF-0F4F4C32A930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27cbc386955c836dac1e6b4240039a99f8481c99","datavalue":{"value":"strongly deterministic regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$3DF65ED4-F93B-46F7-AA3F-82F80C548641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86209b64bd4b0771a38669ec9a2da4dbf6c6ab8d","datavalue":{"value":"regular expressions with counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$DE221B2E-B5BA-42A1-B11E-3C97466036C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dd568bb5cad7cec83fb429e9786b93d9f7ebfb9","datavalue":{"value":"determinism testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$84FDC7C4-EFD2-495E-A086-4F579B73DE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7c105b9df034687aa1ee423419ea0a503343f89","datavalue":{"value":"star normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$1F49C3A3-FF31-4101-ACF6-EE23F776DF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aabd4afba0cd2c9ce51e29a601ebe26e8c5b21b2","datavalue":{"value":"Glushkov automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$0521306F-74B0-4EE9-A5E2-42424219ACA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e18b3b3ed4d7e99ece9f1cc387a817350b68905","datavalue":{"value":"first and followlast sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2343138$011B1D1F-501A-42EC-850C-CAE7E546D0F1","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":"Q2343138$F72A123F-EE7D-4E2F-BC90-BB36E8A9E298","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1710686f7d3019d34dad96071419eee714073a12","datavalue":{"value":"https://doi.org/10.1016/j.ic.2014.12.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q2343138$6AFE650C-DAF5-424C-919E-CA6A95C7C247","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8dd07761842eb90a3a62765bd16c23dc6bf2ed46","datavalue":{"value":"W2077263738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$FC1BCC59-39AD-43C8-B290-FF2F594FFE26","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e71f9f3b7e407bdff49b0af1ad185d8f9ce259","datavalue":{"value":{"entity-type":"item","numeric-id":3167507,"id":"Q3167507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$AAD11566-7F57-4B88-9055-00A837F0369B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4eb55a9a5e4c111bddeb36cf19bf8e8abc5d737","datavalue":{"value":{"entity-type":"item","numeric-id":1314367,"id":"Q1314367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$A8465142-3CFE-4781-A0F1-C6A555FCDB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"108ba3fd5201fe0305322ff4f7361f671bc41615","datavalue":{"value":{"entity-type":"item","numeric-id":5906297,"id":"Q5906297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$1933BEDD-E7B8-4931-917D-987D40EB4F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1780c531bef2cce514180b12f47d2d5de6c9687","datavalue":{"value":{"entity-type":"item","numeric-id":5096780,"id":"Q5096780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$F26C7ED7-E883-4560-80A8-62442663102B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0da9007df3d683da233677991a25cbc5816385d","datavalue":{"value":{"entity-type":"item","numeric-id":5891559,"id":"Q5891559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$636AE93D-BE61-4FCC-9A9E-42F528DF683D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c161911368e95aeec4ffa7e9e9102373a69c553b","datavalue":{"value":{"entity-type":"item","numeric-id":2946652,"id":"Q2946652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$8B7F3870-16CC-4FB0-A9B4-03505E4871BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c46ed93e83cdf84bb76c9faf163845eafb7221f7","datavalue":{"value":{"entity-type":"item","numeric-id":5311160,"id":"Q5311160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$4FCCC5E7-2C46-400E-A030-203924276F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0b3cb0eec2663a59b78b80cf736228e0ac10f95","datavalue":{"value":{"entity-type":"item","numeric-id":2890202,"id":"Q2890202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$C21D799D-BEA7-4AAC-AE58-E76B6D817B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3806517ccf66ca46a6ca3b5a3150596248763b31","datavalue":{"value":{"entity-type":"item","numeric-id":2373702,"id":"Q2373702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$EEB2A86B-709F-43FC-9F21-FD67F5B4870B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de5c706af26597a23c59f8b94c3772be3a8c03c9","datavalue":{"value":{"entity-type":"item","numeric-id":4040284,"id":"Q4040284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2343138$7C9FF921-2954-4796-93A6-CA2260E4FC90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3ba5f3355efea5b5b8771c84fa202973e3fe642","datavalue":{"value":"10.1016/J.IC.2014.12.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2343138$5A060F13-A14C-48CC-A755-75749F2D05D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"916261f26465af3adbd4ff64e82ea108dd544720","datavalue":{"value":{"entity-type":"item","numeric-id":3167507,"id":"Q3167507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bde5431c998d4bba6901e4e2303e641ec8758cc","datavalue":{"value":{"amount":"+0.9163790941238404","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":"Q2343138$4EB30768-66DD-4789-9607-A22BC6BD98F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e021c32ffb9774c2ec49b2c0269d7b534e4a760b","datavalue":{"value":{"entity-type":"item","numeric-id":5891559,"id":"Q5891559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e09ec69d746b93f71efc94e8510adbd14c50869","datavalue":{"value":{"amount":"+0.8723295331001282","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":"Q2343138$FE04800E-8B51-48D8-A307-7AA053F1A20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77535a80614c412867f83083998ba857acd3c15f","datavalue":{"value":{"entity-type":"item","numeric-id":5895105,"id":"Q5895105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e2c1fad5cef317af3ee904e14b02f63616603c0","datavalue":{"value":{"amount":"+0.8720439672470093","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":"Q2343138$034D988B-224F-48DD-90E6-0C1DF8387005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70e07ca98430ea0f67988363309b9e28969d4e3b","datavalue":{"value":{"entity-type":"item","numeric-id":2361347,"id":"Q2361347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9d8c25ab259c6a4db651f79a10e6a0b3b07ed2a","datavalue":{"value":{"amount":"+0.8683218955993652","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":"Q2343138$703F81C1-1ECD-4253-A034-D7BE9468D5BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c26c85702d2dca8cfea25ecc3d82781fb298a3","datavalue":{"value":{"entity-type":"item","numeric-id":2787424,"id":"Q2787424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b583bd0b2feef426cc996dfcfbcaac9911a63cf","datavalue":{"value":{"amount":"+0.8218991160392761","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":"Q2343138$AB6686FF-D445-4788-9931-76715E6C8E87","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2343138","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2343138"}}}}}