{"entities":{"Q43941":{"pageid":43997,"ns":120,"title":"Item:Q43941","lastrevid":105429182,"modified":"2026-10-09T10:11:27Z","type":"item","id":"Q43941","labels":{"en":{"language":"en","value":"MSO_Regex_Equivalence"}},"descriptions":{"en":{"language":"en","value":"AFP entry MSO_Regex_Equivalence"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"cf2c4e20b2326c09f08acaeec8e66a9be8a2283a","datavalue":{"value":"32230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q43941$7B73BC37-162C-4728-924E-6FCADB3AAABF","rank":"normal"}],"P286":[{"mainsnak":{"snaktype":"value","property":"P286","hash":"cbbcc749e586d02367d1073103e72e2ef013eafb","datavalue":{"value":{"entity-type":"item","numeric-id":5371957,"id":"Q5371957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$63DEB26D-C22E-49D8-848C-B7EE2D4B410A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$8978526B-9AB1-424A-B1FD-10F0E1BA3BF2","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"225f548c32c3bb11aa34a3888d22b0cf98e374c0","datavalue":{"value":"https://www.isa-afp.org/entries/MSO_Regex_Equivalence.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q43941$1C40F75E-9925-4C4D-8383-6B3F1F5F7EC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0db99c3b17fc587dc6d0b047e5ff5ce0de1786ab","datavalue":{"value":"03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q43941$695D7C2A-0CE4-4B15-A618-F19385E84DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q43941$00162548-EFB8-4EDA-8A40-9681ACB09D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ccfc2ffdb7a60cd36d8dca0a4e6d9d45f5228f3","datavalue":{"value":"3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q43941$D56DADE8-6CE7-4E5D-95C4-DC82D6251E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f5e0c6033338f59ef27e37d6877da0f26d9646","datavalue":{"value":"68.0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q43941$94156210-DA79-425F-A3AF-C87F5CE71307","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"2778ef58df5d105bc5fcd1f1e6190b4cffc33d19","datavalue":{"value":{"entity-type":"item","numeric-id":40261,"id":"Q40261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$75C62768-D091-4879-874A-8832E701EAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"feba23e7c41ba4aa38bf2dee9205344029ea237a","datavalue":{"value":{"entity-type":"item","numeric-id":40317,"id":"Q40317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$2F2C4084-F18A-417D-9DFC-14CED3CDCB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b49b6cd0d730920a3a4cd5d33a24263cc6515903","datavalue":{"value":{"entity-type":"item","numeric-id":43940,"id":"Q43940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$90D48A2B-DA98-493F-B018-0BA132CB18BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$70CEEE89-13D5-46B6-BFE8-B4686AAEB7A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ea53781dc0a29ca150a09c3de99800e897e49297","datavalue":{"value":{"entity-type":"item","numeric-id":40507,"id":"Q40507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$1572C5C6-BD4B-47A5-9BC4-D1A768A839CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"81319f5b8664d8398f69fd7004689cf3156bb740","datavalue":{"value":{"entity-type":"item","numeric-id":40964,"id":"Q40964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$AC3CAB36-68C5-4589-A3F3-516B987A9826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"87ec2ca742c9eb10fbaa98b1820ddb7f4298bb25","datavalue":{"value":{"entity-type":"item","numeric-id":40963,"id":"Q40963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$B7209B90-EBB0-4B2C-B930-6167D55B777D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"c1161e1e8de5a1bc9eb8260f27cf5114412c2b8a","datavalue":{"value":{"entity-type":"item","numeric-id":21343,"id":"Q21343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$9E70DF8F-8255-4782-AEE8-BF02182AFCA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$FF2A383A-4284-4D42-9D3C-0C6D68F3C7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"33a2c00edd213d9c703e35c0ce5b77b6ea1dd277","datavalue":{"value":{"entity-type":"item","numeric-id":18304,"id":"Q18304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$84172E8C-E915-4EE3-9E35-993E49241DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$EB4B7FEA-11D6-446C-87D2-402BE63A06D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"8533330b9fa0c1f7979d4af1d0e8bdba3ffc811c","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$71815829-DF2A-416B-AD07-77FCC31D7555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$E183F242-CBD8-4593-A3F1-D42CF45D9DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"373b63863b775147169b00da6e2e02a5f8cd3aa3","datavalue":{"value":{"entity-type":"item","numeric-id":40256,"id":"Q40256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$C40177F4-01A0-4F5B-AAC1-94EADA607ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ec6dbb1548c12606916852927cc780aa1e549693","datavalue":{"value":{"entity-type":"item","numeric-id":25788,"id":"Q25788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$8998ABAE-0C1D-4BF2-A79F-8F834E03C048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"f37c4bd9e3a1e8f671d27130134b89693886108a","datavalue":{"value":{"entity-type":"item","numeric-id":22908,"id":"Q22908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$3E76FCDB-1816-4871-BFD1-D1CB0E6E4465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$75F14843-34DD-4F15-9EAA-2E541E71E2A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b31273075f42a5fc76c3bb0e6c5c64c5365a9221","datavalue":{"value":"https://isa-afp.org/entries/MSO_Regex_Equivalence.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q43941$D04BE146-0AFC-432E-923A-467DDC0C2A10","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"2500aa80beaafa12dfa4ab6c7d8363674f762e6e","datavalue":{"value":"Dmitriy Traytel","type":"string"},"datatype":"string"},"type":"statement","id":"Q43941$A2B02CAB-8570-4ED9-B2AE-8366BFFD2395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q43941$5B00A968-260A-4330-84C0-77AE051DE2CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15b7d3f95392d44f15a246575c7c26851dcbe389","datavalue":{"value":"Monadic second-order logic on finite words (MSO) is a decidable yet expressive logic into which many decision problems can be encoded. Since MSO formulas correspond to regular languages, equivalence of MSO formulas can be reduced to the equivalence of some regular structures (e.g. automata). We verify an executable decision procedure for MSO formulas that is not based on automata but on regular expressions. Decision procedures for regular expression equivalence have been formalized before, usually based on Brzozowski derivatives. Yet, for a straightforward embedding of MSO formulas into regular expressions an extension of regular expressions with a projection operation is required. We prove total correctness and completeness of an equivalence checker for regular expressions extended in that way. We also define a language-preserving translation of formulas into regular expressions with respect to two different semantics of MSO.","type":"string"},"datatype":"string"},"type":"statement","id":"Q43941$F887234D-6303-410F-A129-93F43E038B28","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"edaae9fe0e5779978f85e3c7bb7897012bfd4b62","datavalue":{"value":{"entity-type":"item","numeric-id":7361610,"id":"Q7361610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$CE68F448-092D-4E46-AC3C-3C0F645D19AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0b5465b6a0d9e05645cdb7168eee1aaf7eb2845","datavalue":{"value":{"entity-type":"item","numeric-id":7361518,"id":"Q7361518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$AC244488-CAE4-49B7-AB82-840D022E5E18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"213fd3ab5f25a17aadb6df8b4d179ba21632b8bc","datavalue":{"value":{"time":"+2014-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q43941$82B310ED-BE8E-48E8-9D6E-F703D7AD0566","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd344d3a41e61571bceeca37a2b0e45503752bc8","datavalue":{"value":{"text":"Decision Procedures for MSO on Words Based on Derivatives of Regular Expressions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q43941$FC533492-D0D8-425F-9177-BBB2AE9343C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"913d390a955b3d78ab90198320a7e4d2725e8b2c","datavalue":{"value":{"entity-type":"item","numeric-id":5244782,"id":"Q5244782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$81342EF3-D1D5-4461-BA1F-E3623FA4D326","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$AE59A8E9-0D8E-47FE-85F4-9B66682F0F86","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"73d93a21b0749f7f2c51d7daeb11b162660cd756","datavalue":{"value":{"entity-type":"item","numeric-id":7360784,"id":"Q7360784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q43941$BCCFF5AA-87E9-4428-8EDF-9BEE529C3AC6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"MSO Regex Equivalence","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/MSO_Regex_Equivalence"}}}}}