{"entities":{"Q2202012":{"pageid":2212755,"ns":120,"title":"Item:Q2202012","lastrevid":53824253,"modified":"2026-01-25T18:57:52Z","type":"item","id":"Q2202012","labels":{"en":{"language":"en","value":"On the semantic equivalence of language syntax formalisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7248846"}},"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":"Q2202012$3DE4E7F1-3C8F-4265-BBE6-1FE8F3A3C174","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"acd47f9f47e44117590532930761db28d7a22667","datavalue":{"value":{"text":"On the semantic equivalence of language syntax formalisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2202012$8EE3DAE7-4A7F-4FAF-A5E9-E307107D73C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"716104a00c86ea247d2d897f0331e076f6394040","datavalue":{"value":"1461.18001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$BD01F0F6-B617-4C3F-B8FA-535889EE4234","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9270580dc3c4f6fbe7c907fb198c4aae566e2167","datavalue":{"value":{"entity-type":"item","numeric-id":2133468,"id":"Q2133468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$1D105B13-9EFF-43F6-BB98-CB78DDC28692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"145dfc643b53f471cb50f045a5c8b4f60a920b97","datavalue":{"value":{"entity-type":"item","numeric-id":511011,"id":"Q511011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$178A3655-D153-4D02-9C9F-9E09962A0465","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":"Q2202012$2B644F6B-910E-4DB5-945D-434B8D3FD6F8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7b654844b81166f884849fbb386fac59a7d85c1","datavalue":{"value":{"time":"+2020-09-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":"Q2202012$677EAFBB-A1B8-4552-A782-879DE1C7B4E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b24f515a4faceebe5dcaa7253d584ab465b385da","datavalue":{"value":"There are various approaches to describing the syntax of a language [\\textit{E. Visser}, Syntax definition for language prototyping. Amsterdam: Univ. Amsterdam (1997; Zbl 0900.68290)]. Formal grammar [\\textit{N. Chomsky}, Three models for the description of language. IRE Trans. Inf. Theory 2, No. 3, 113-124 (1956; Zbl 0156.25401)], [\\textit{J. Earley}, Commun. ACM 13, 94--102 (1970; Zbl 0185.43401)], [\\textit{D. E. Knuth,} Semantics of context-free languages. Math. Syst. Theory 2, 127-145 (1968; Zbl 0169.01401)] is widely used to design the syntax of programming languages [\\textit{M. L. Scott}, Programming language pragmatics. Oxford: Morgan Kaufmann/ Elsevier (1999; Zbl 1005.68031)]. The methods of context-free parsing are especially effective [\\textit{L. J. Valiant}, J. Comput. Syst. Sci. 10, 308--315 (1975; Zbl 0312.68042); \\textit{L. Lee}, J. ACM 49, No. 1, 1--15 (2002; Zbl 1323.68332)]. Algebraic signatures provide an algebraic approach for syntax specification used in universal algebra [\\textit{P. M. Cohn}, Universal algebra. Dordrecht-Boston-London: D. Reidel Publishing Company (1981; Zbl 0461.08001)] and model theory [\\textit{C. C. Chang} and \\textit{H. J. Keisler}, Model theory. Amsterdam etc.: North-Holland (1990; Zbl 0697.03022)].  The paper under review is devoted to the comparison of three syntax formalisms: context-free grammars (\\(Grm\\)), many-sorted signatures (\\(Sig\\)), and order-sorted signatures (\\(Sig^{\\leq}\\)). These syntactic formalisms are treated as categories, as justified in Propositions 1, 4 and 5. Translations of descriptions from one formalism to another are considered functors. \\[ \\Delta: Grm \\to Sig, \\nabla: Sig \\to Grm, \\vee: Sig\\to Sig^{\\leq}, \\Lambda: Sig^{\\leq}\\to Sig \\] This capability is established using Propositions 10, 11, 14, 15. It was proved that the functor \\(\\nabla\\) is left adjoint to \\(\\Delta\\) (Theorem 1). Moreover, these categories are equivalent (Corollary 2). The functor \\(\\mathrm V\\) is left adjoint to \\(\\Lambda\\) (Theorem 2). Propositions 16 and 17 show that these categories are equivalent.  Any of these functors preserves classes of semantics, in the sense that if \\(Alg ({\\mathscr X})\\) denotes the class of semantics of an object \\({\\mathscr X}\\), and \\(\\Upsilon\\) is a functor, then \\(Alg (\\Upsilon {\\mathscr X})\\) is equivalent to \\(Alg ({\\mathscr X})\\). This is proved in Theorems 3, 4, 5. (Functors \\(Alg: Grm\\to Cat^{op}\\), \\(Alg: Sig\\to Cat^{op}\\), \\(Alg: Sig^{\\leq}\\to Cat^{op}\\) are constructed using Propositions 4, 7, 8.)  Similar questions were studied by \\textit{J. A. Goguen} et al. [J. Assoc. Comput. Mach. 24, 68--95 (1977; Zbl 0359.68018); Theor. Comput. Sci. 105, No. 2, 217--273 (1992; Zbl 0778.68056)], but their results are special cases of the results of this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2202012$AADA5560-8C06-4870-AA58-6280CA6A7A27","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005f05cf648e43cad8e44abd96ef50fda59adae","datavalue":{"value":"18A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$574478E7-326F-4589-B700-1936114E6934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$D0C66B8C-4079-4503-808F-C1215CEE5833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$ED2BA8F8-74F8-4EC0-B467-8E3056FFFBBB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83e39059708b226508e30e93d996e59099e4353a","datavalue":{"value":"7248846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$B57FC852-3544-4D8C-A54B-78946B634EE7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"437fc959356c6f20727db9b4b3525bfe1629b06b","datavalue":{"value":"syntax specication","type":"string"},"datatype":"string"},"type":"statement","id":"Q2202012$487B6D94-2AAD-4208-BBB0-415BD3FBC0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a37f1b310a3dab2e44459244c624b1e251e5b8cd","datavalue":{"value":"context-free grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q2202012$3A1FFB7D-EC0E-4756-9BA0-288FD60F626D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d5ba137c1f50bf79bb249e37fbc27f043078f5d","datavalue":{"value":"algebraic signatures","type":"string"},"datatype":"string"},"type":"statement","id":"Q2202012$66E960DB-799C-48F3-BCC3-07728E26E2DE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"16c26e4ac190a2cc8301d13290ef2f97e240c6b3","datavalue":{"value":{"entity-type":"item","numeric-id":590338,"id":"Q590338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$468B9388-94C1-41B9-AAC1-85F091B91D83","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":"Q2202012$10BA3724-FD84-4DB2-AF53-18728E2CA476","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d42a795b5331e3b53bc0d829f86879304ab0df3","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2020.08.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q2202012$80A210AC-A7F0-4216-B38D-2574A4FB7887","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d3df4afce90675315c4f92e64f381292d4837fde","datavalue":{"value":"W3080522507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$D6509D9F-FE49-4BBB-AFA0-60A03531CA9F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdb7de0c02ce87915bf7ac1ca4032299bfef41cc","datavalue":{"value":{"entity-type":"item","numeric-id":1129122,"id":"Q1129122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$7F8459C8-2700-49AF-A00C-23B16788EE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36cc44b9102625eb334a136f424df325e05567e6","datavalue":{"value":{"entity-type":"item","numeric-id":2633623,"id":"Q2633623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$CF3B0A34-0AE9-445A-B4A8-726006396BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee5d097f7c9c8bc1fce167a67611fb36307bcf68","datavalue":{"value":{"entity-type":"item","numeric-id":808278,"id":"Q808278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$85BF87EB-32AE-43DD-999A-AE2C798E483A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0065dc8b5c25773ef1d9719266c7992d0edd4dd5","datavalue":{"value":{"entity-type":"item","numeric-id":4131619,"id":"Q4131619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$48D179E1-D74B-4E03-99EB-87431D05F722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d3151584bc22ebf6ff853fb550e2046ddd0ec90","datavalue":{"value":{"entity-type":"item","numeric-id":4136594,"id":"Q4136594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$FF0424CE-A3DD-454D-8A5D-AD837606122F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d9ae9d25c165776926d92ae2f293b4bf9587937","datavalue":{"value":{"entity-type":"item","numeric-id":5727668,"id":"Q5727668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$C0F03676-933B-44E7-973F-452B94119E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e2db18f956a86c51893ceffc869b394629d46fd","datavalue":{"value":{"entity-type":"item","numeric-id":5611775,"id":"Q5611775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$20DCBA2F-035F-46D0-A844-0A2B52C9CE5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9205c171d8dfbbf836ec95e215a99db195f75a67","datavalue":{"value":{"entity-type":"item","numeric-id":4102722,"id":"Q4102722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$FEC08F8D-89C4-45F6-9444-0CB3ADCA0E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3239d3bc022112b37f4da6991a3c7bf09667ee35","datavalue":{"value":{"entity-type":"item","numeric-id":1196302,"id":"Q1196302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$48FA3CE3-6935-437D-A386-4F1D8E198167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e21add89c79d34c9c773902500a073cf067b419","datavalue":{"value":{"entity-type":"item","numeric-id":4215869,"id":"Q4215869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$A3AE3CEF-3BF4-4A78-9B41-2715592B4034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97002deaa32bce9238411fd6668f6b28c627864","datavalue":{"value":{"entity-type":"item","numeric-id":5536272,"id":"Q5536272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$8E7B44FB-60C1-4E26-BC56-E6BD5E39AF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b78adcee74e0f5ade00e0948eea875c91d9521e5","datavalue":{"value":{"entity-type":"item","numeric-id":5578055,"id":"Q5578055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$0CFD94BD-5D59-45CC-B8F8-2EA5B79802F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2ffad56ff7cb3f1b7bce5a75e03b0b6586eb531","datavalue":{"value":{"entity-type":"item","numeric-id":5555691,"id":"Q5555691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$98FDE17A-AFAE-4E8D-9D08-C10514E8730E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"335e4ec2e1c2c616c1a0b6320a1f6a565be9a774","datavalue":{"value":{"entity-type":"item","numeric-id":4779980,"id":"Q4779980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$7D53B87F-02CA-41DE-A03B-2515A93BE15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16cf335d5b7594672e390f44ff0f73ea66ddcf55","datavalue":{"value":{"entity-type":"item","numeric-id":1219690,"id":"Q1219690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$9D71966B-2725-425F-B776-8C18BF9540B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3c8408be1f2cf1730799a6f789e4ab549978865","datavalue":{"value":{"entity-type":"item","numeric-id":3196632,"id":"Q3196632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$E40D596B-A96E-435D-BEA4-5F553D9DBCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c859dc9bc5c44c673f4132f2e7bef4d53162ec9","datavalue":{"value":{"entity-type":"item","numeric-id":1188602,"id":"Q1188602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2202012$74E12D58-415C-4DA3-8227-718D0A2EAD52","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8243661a5fbb74d9821125b4a506bba3e1ab42ed","datavalue":{"value":"10.1016/J.TCS.2020.08.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2202012$72EB4881-23B3-4EC2-9AE2-6833F99F1C63","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f26b7f58728b6660ea9f258c31e870b7448032da","datavalue":{"value":{"entity-type":"item","numeric-id":3703897,"id":"Q3703897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74b704f413eccd509cb237491bcdafc64d8af251","datavalue":{"value":{"amount":"+0.7278648614883423","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":"Q2202012$221E08FF-EBB9-45F4-966D-9E5561801EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"479cf0a1e8d577af60a5bad2f25ba0e6015128f6","datavalue":{"value":{"entity-type":"item","numeric-id":3086528,"id":"Q3086528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2215a18c6c914eb19e45c91419066219d63c6448","datavalue":{"value":{"amount":"+0.7185104489326477","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":"Q2202012$690C8D09-9BBC-4FC1-B544-730A8CF7822F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b79c0365b671a8f6e4bc72c4a6fbd379e844c491","datavalue":{"value":{"entity-type":"item","numeric-id":1129122,"id":"Q1129122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5ff2ef15b984298a7b9c8083613e76a6263e274","datavalue":{"value":{"amount":"+0.7127661108970642","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":"Q2202012$4D7809AD-3AB4-4E3C-9917-995ABA61CE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1659c74c355375289077102b8ef84bfd8c827b6b","datavalue":{"value":{"entity-type":"item","numeric-id":3315018,"id":"Q3315018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acf9ef0502645b5e2ef5ced34db6e78392f5cc52","datavalue":{"value":{"amount":"+0.7118253111839294","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":"Q2202012$176F50C1-2116-492F-A82C-C078DE2A8F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93509e17828976e09a61fd4ac19decab76c73283","datavalue":{"value":{"entity-type":"item","numeric-id":2915022,"id":"Q2915022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff0e1958319218277904ddd56dc9ce2ef6a120c4","datavalue":{"value":{"amount":"+0.7105990052223206","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":"Q2202012$AE78DE06-7871-4BD7-B33C-96770730EFF3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2202012","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2202012"}}}}}