{"entities":{"Q4938634":{"pageid":6968216,"ns":120,"title":"Item:Q4938634","lastrevid":108550865,"modified":"2026-11-06T23:02:20Z","type":"item","id":"Q4938634","labels":{"en":{"language":"en","value":"Two-way finite state transducers and monadic second-order logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1405653"}},"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":"Q4938634$9C6FB4BC-5C49-48C8-BE83-C890AB310964","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d2ca79cf582365c312f38aebbf2115cc46cff0b","datavalue":{"value":"0946.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$1FF05484-0258-4EC7-AF6F-6F5132DB03D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d3b51f718829bdc40d57f1305c80d06e624ee4b","datavalue":{"value":{"entity-type":"item","numeric-id":396843,"id":"Q396843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4938634$B9B898B0-C12A-4859-91D4-BDBC382EB87B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdaa763056574d670db49d3b9b4fb6f07d823420","datavalue":{"value":{"entity-type":"item","numeric-id":255286,"id":"Q255286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4938634$417BBCE9-85BC-4312-B61F-AF6FF1D627E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"33cd021da003ce90b694dcd1b369ed11b6f26639","datavalue":{"value":{"time":"+2000-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4938634$797006CE-C0C3-4777-A5D9-763A73380B2D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$6B4185D6-0CBA-4E53-AD2F-D89F7CA57FE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$E58DE149-8FE4-45EC-A64E-FE8089EEA771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$CC6B360D-15F6-40F9-8B4A-19D0629C4F88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6160ec7cbcec7591b00c01550fe314475aaba7c7","datavalue":{"value":"1405653","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$686B2F11-9F54-408A-83CC-54426B2361EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$77E902BC-8D9E-48F1-BF23-5E3A681F2214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d40cffa5451fbca21b93d969035593365e195661","datavalue":{"value":"graph transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$D14FADC2-1FED-4A6A-A9F9-8F5A498B36D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0338534f1f13f391fb2d3082fcb10667f2fcfa27","datavalue":{"value":"string transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$1374A8AA-0F88-4FC9-8ECE-CC23CC24BDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f61c9f8c89c9067d8dc019d97ef41857cd132491","datavalue":{"value":"two-way finite state transducers","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$67CDB386-3FF1-483E-9B94-CB13E550044A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$DC3C0F85-A346-443A-991D-1F5DEAE8BCDE","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":"Q4938634$697164D5-8B77-461E-A164-209344878D43","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2497d137333c9127394362356567cb33e7824d88","datavalue":{"value":{"entity-type":"item","numeric-id":4406290,"id":"Q4406290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84e8ed2886dde5106dc522eb0ead146ad65e11e3","datavalue":{"value":{"amount":"+0.8955144882202148","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":"Q4938634$961050D6-B61E-41E4-B979-A1FD72908C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c5a5d513422b25a037c210ca5fb5f097493f918","datavalue":{"value":{"entity-type":"item","numeric-id":4910492,"id":"Q4910492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7b05fbab98ba4d06cb0c6519a9e71df99de0832","datavalue":{"value":{"amount":"+0.8748014569282532","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":"Q4938634$4D9B3482-E0A8-452E-B456-6D3ECB898B09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0207ab900629890eb05a437aec1194950867f8f","datavalue":{"value":{"entity-type":"item","numeric-id":5271084,"id":"Q5271084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daf40dac7d895f05ee131c83f30b72ef21ee350d","datavalue":{"value":{"amount":"+0.8219517469406128","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":"Q4938634$229D6AC8-4479-4DE2-A829-24D68D5CB0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d152411e264cf69862712307df6e37521245ff26","datavalue":{"value":{"entity-type":"item","numeric-id":5431915,"id":"Q5431915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7fc424d3ae9ac5d10d7b7361fd3880e074140ef","datavalue":{"value":{"amount":"+0.8072812557220459","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":"Q4938634$86115BBD-56D5-440B-856B-13B70BF881E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce44e62103ac17352890abce43dbc1647c96ca55","datavalue":{"value":{"entity-type":"item","numeric-id":5351956,"id":"Q5351956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc78e671ab1240f4244c78e45bc0dd1bb67a0d65","datavalue":{"value":{"amount":"+0.7861464023590088","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":"Q4938634$7A41C36C-9880-4909-B63F-EF096869CEAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2eef4a6f8384d5832f3693bdf7f697644509fc43","datavalue":{"value":{"text":"Two-way finite state transducers and monadic second-order logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4938634$89E15CC7-27EA-4098-9743-5F0271027784","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c6555c7c1f0a2cbb4c63fe03d82fd1d7562e8e4","datavalue":{"value":"10.1007/3-540-48523-6_28","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4938634$E8416BEB-5F75-4D56-927E-B797A021166E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"45a73ad9dde6201d3992960226c8bcaa1c3844b4","datavalue":{"value":"This paper contains several results concerning string transductions realized by two-way finite state transducers or defined by monadic second-order formulae. The main theorem equates the class 2DGSM of transductions realized by deterministic finite automata with a two-way input tape and a one-way output tape and the class MSOS of transductions obtained by restricting monadic second-order definable graph transductions to strings (which are represented as directed graphs in two natural ways). On the other hand, the nondeterministic versions of these two classes are shown to be incomparable. The nondeterministic counterpart NMSOS of the class MSOS is obtained by allowing free node-set variables in the formulae. Some composition and decomposition results are also presented. For example, it is shown that \\(\\text{NMSOS} = \\text{2DGSM} \\circ \\text{MREL}\\), where MREL is the class of certain marked string relabellings. Finally, the authors give a complete inclusion diagram for the main families of transductions considered. For the entire collection see [Zbl 0917.00014].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4938634$83599BAD-422E-4904-9417-84368942178B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4938634$2DD3FD55-F317-41E3-A117-68091B487C4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two-way finite state transducers and monadic second-order logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two-way_finite_state_transducers_and_monadic_second-order_logic"}}}}}