{"entities":{"Q1758227":{"pageid":1768969,"ns":120,"title":"Item:Q1758227","lastrevid":73376136,"modified":"2026-04-14T15:39:58Z","type":"item","id":"Q1758227","labels":{"en":{"language":"en","value":"Amalgams of finite inverse semigroups and deterministic context-free languages."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6103704"}},"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":"Q1758227$0DE1F6E5-AF1C-4700-974C-7B3ADE986375","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a63d6d3fc5aacdf7cc9b1171b21ec9769ff7acb7","datavalue":{"value":{"text":"Amalgams of finite inverse semigroups and deterministic context-free languages.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1758227$6E9A5592-02E3-4155-86A7-2A1BF001EBA5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6822fb5ef9804ff3e70fdbe5401fa9025728e170","datavalue":{"value":"1275.20066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$9B9D6AA7-FB41-4537-8C51-32A48838F97E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"921ef8225a113382e2c3b0c1a5478b76849a9cce","datavalue":{"value":{"entity-type":"item","numeric-id":1758225,"id":"Q1758225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$D353F454-335B-4E90-9174-DA6E1B3310F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a2a6aa52f309a3eb5fdf219849c665e44471751","datavalue":{"value":{"entity-type":"item","numeric-id":1137651,"id":"Q1137651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$32FAF3AF-7296-4F0A-BA59-CBF0A7D6738B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"765d69378dc5e63e1ac7347f6754dda6bdd6b8ba","datavalue":{"value":{"entity-type":"item","numeric-id":305763,"id":"Q305763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$D7B14BC3-65EE-4A71-B2B5-947BA16B7BFA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$8DE47664-C6FC-42D2-A180-E00C9606BE85","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fd40b453552197bf6992e0512f747c68abfc621","datavalue":{"value":{"time":"+2012-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1758227$7CD169B7-EFC3-4C38-A8DD-B2161F626812","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"644c53d5a3bd71daeed27575aaba22fe12580b35","datavalue":{"value":"The paper deals with the standard presentation \\(\\langle X\\mid R\\rangle\\) of an amalgam \\(S=[S_1,S_2;U]\\) of finite inverse semigroups. Through the investigation of the structure of the Sch\u00fctzenberger graph \\(S\\Gamma(X,R;w)\\) of a representative \\(w\\in(X\\cup X^{-1})^+\\) of an element \\(s\\) of~\\(S\\), several algorithmic conclusions are drawn. The main ingredient is to show that \\(S\\Gamma(X,R;w)\\) is a context-free graph in the sense of \\textit{D. E. M\u00fcller} and \\textit{P. E. Schupp} [Bull. Am. Math. Soc., New Ser. 4, 331-334 (1981; Zbl 0484.03019)], and whence the transition graph of a pushdown automaton. Thus, the language recognized by the associated Sch\u00fctzenberger automaton, which recognizes the language of all representatives of elements of \\(S\\) which lie above \\(s\\) in the natural order, is a context-free language. An explicit construction for a pushdown automaton recognizing this language is also given. As an application, the authors show that the non-uniform word problem for amalgams of finite inverse semigroups is solvable in polynomial time; decidability had previously been established by \\textit{A. Cherubini, J. Meakin} and \\textit{B. Piochi} [J. Algebra 285, No. 2, 706-725 (2005; Zbl 1069.20052)]. Another application is that it is decidable whether all \\(\\mathcal D\\)-classes in such an amalgam are finite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$DC991E31-ADB7-44D8-B1D4-B885EC4F32D4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99980a1fe8b67be8570894d1f605195f6f2e1e0e","datavalue":{"value":{"entity-type":"item","numeric-id":375866,"id":"Q375866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$A82D7B5A-3834-450C-9C3E-21FBEA383D33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4ac0e84a504a59b674a6c5271111dec0d2b6bb2","datavalue":{"value":"20M18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$8747A5B8-E7AB-41F4-93EB-1A4286BE5105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$C8D7DDD2-F5E0-4A5C-B69D-AC28FAA8DCA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$35FD1FD6-92CC-49A0-9030-ED880AFE8423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$FEC7D48E-0C4D-4A6B-B68D-7B5B0E8A345E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81e2c5c1edde5fa2c3ca0c1f014bbcd466246cc6","datavalue":{"value":"6103704","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$4D951582-3939-486A-9D6A-A2C34403196F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ad4489bb8ad8514198b18a1dc2b558878ff9ead","datavalue":{"value":"finite inverse semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$E5069051-47E2-4779-A45F-77B6053056C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04de1f27292206e268b3a6c06e1deab51ebf3645","datavalue":{"value":"amalgams of inverse semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$1785DB77-4447-44E3-8FBE-76AA428A674B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e27b79edf622046efaf6f6ec1dcbe5d6ff53e34e","datavalue":{"value":"Sch\u00fctzenberger automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$520B9E45-F9B2-4290-BA92-3CFC9A114CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b58a9db06da05029b9b9e50c5b23ff5479c4757","datavalue":{"value":"context-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$4FAD1BDB-E582-4EA4-9E70-27E94166726F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$30D8F9D2-A005-4950-8CDE-85215E2A4878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$474E479A-5C34-4A1E-ABEA-7ACB020C7C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758227$354C4848-598E-4FBE-B740-C1A5D7750A0D","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":"Q1758227$456D30B6-E53C-4A42-9BF6-0A3FD35A602E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ecfe7b5568a7fb035aebb137dd202013eeb42505","datavalue":{"value":"https://doi.org/10.1007/s00233-012-9399-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1758227$678538FF-A8B7-4B59-88C8-8C8467716FA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9891475b6b71bf7d434403af48d8b68561d60bc5","datavalue":{"value":"W2067396744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$7C19D7AB-90E0-4196-8C54-5D9ADEAB919D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed4158e9526994a65a76e954808a817b67bcbff9","datavalue":{"value":{"entity-type":"item","numeric-id":5449818,"id":"Q5449818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$EA331AA7-E2C1-45D4-888D-CEB99D0D2CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcf646a1c8b2ea881cb67aa6ecf8c0c3787ac2a7","datavalue":{"value":{"entity-type":"item","numeric-id":5906846,"id":"Q5906846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$1A12ED71-F9F1-42AE-8325-819D8CEF1786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fd1ff12b9b2806fb4b40f14497e6a66352332db","datavalue":{"value":{"entity-type":"item","numeric-id":677103,"id":"Q677103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$8B7F9A1D-38D3-4DB5-99BA-70628477ADA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79dca27bc91ce83425500a8d3740ebe4d7e70401","datavalue":{"value":{"entity-type":"item","numeric-id":1772442,"id":"Q1772442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$829438EE-F8C7-4540-9FF0-3D79F49E02D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61832d931827b78c83ec3f93e92177156138e5b5","datavalue":{"value":{"entity-type":"item","numeric-id":2996838,"id":"Q2996838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$1A92A9F5-2A33-4801-8F86-551324FFCAD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4c189c60e4235e9fe1a76eaedd99557e51704a9","datavalue":{"value":{"entity-type":"item","numeric-id":3094735,"id":"Q3094735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$F6CE17E6-D7A9-4F8A-B98B-B9777658A48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6abb2e4f94eadc3b2f403c6b0d70e5f46d563df","datavalue":{"value":{"entity-type":"item","numeric-id":1225688,"id":"Q1225688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$31CDC5FA-3E09-440D-A2C2-625F5011ED52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$8598398B-83F8-433B-9E4A-89EE8D655E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ae246a6e53e55446eb5e90b6e4a5ef0764472a","datavalue":{"value":{"entity-type":"item","numeric-id":4038472,"id":"Q4038472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$613A6C64-40C6-4CA0-B419-62C70AB93B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cd06688d0a2118d72cedd0d86de5ca69bef5bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1084096,"id":"Q1084096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$F38A7862-37D9-463B-9F7C-C8F0E8DFCBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66ccb759190ed6fe5a6f7e7ca0faf992aa8f2107","datavalue":{"value":{"entity-type":"item","numeric-id":4061136,"id":"Q4061136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$1970F2D7-B4B8-4D4C-AA18-0D8EB470EEA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c53d57a230b4bbfeeca49cf0ac14239a914a144e","datavalue":{"value":{"entity-type":"item","numeric-id":3337662,"id":"Q3337662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$6D1783DA-48F8-4956-8FA0-272642F63040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43d2ffb755428c7bae6e734f88daa13d3032d856","datavalue":{"value":{"entity-type":"item","numeric-id":1177178,"id":"Q1177178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$D7054093-9623-482B-8A25-7A6DF5990BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1109bb8724ea9cf0f5538843e49a3254bc6f0b34","datavalue":{"value":{"entity-type":"item","numeric-id":958188,"id":"Q958188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$E89F9607-6053-4ECE-B364-265A78FA3E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a027183543d00576c58da7b8a0d9928c4754d47","datavalue":{"value":{"entity-type":"item","numeric-id":3552317,"id":"Q3552317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$68BBDE75-D8CA-4F6D-8F98-835689DDF893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c040415d351156844afd3404e4c23cb0d719d904","datavalue":{"value":{"entity-type":"item","numeric-id":582399,"id":"Q582399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$8EE7DD82-BD86-470A-A873-A2F592CAE8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f66f875e893d2e1d2daa7f1c04a97f3c6d85e41","datavalue":{"value":{"entity-type":"item","numeric-id":3112581,"id":"Q3112581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758227$9AD61408-73DE-4A9C-87C8-D43720FFA79A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f501aa4d1805a488803e8ab55739dd7cbfe22ba3","datavalue":{"value":"10.1007/S00233-012-9399-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758227$681DBF3C-D129-41DE-91BD-D9347EAC2C85","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35ba0e9f71ed0d1f3567318b4dd7f0fab23b745","datavalue":{"value":{"entity-type":"item","numeric-id":1772442,"id":"Q1772442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c17b8d46ef1dbfb30ad3757e86a29a1f6b13606","datavalue":{"value":{"amount":"+0.8600319027900696","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":"Q1758227$AADBCEBD-9839-4399-9355-7164AEC9688C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"117fcbc184a7eb1d5a210c3380361253c91dcd6b","datavalue":{"value":{"entity-type":"item","numeric-id":3449708,"id":"Q3449708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82e762a787cb4d8a8b9148bb9d8aadc646908337","datavalue":{"value":{"amount":"+0.85431969165802","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":"Q1758227$09AB5885-E44C-4C01-A981-D3BABA144DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac66742be4ee88bbae2cfd79b7cabf6ffc44030b","datavalue":{"value":{"entity-type":"item","numeric-id":2481330,"id":"Q2481330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"864dd06fadf237411d349296fbf0a89427a8e337","datavalue":{"value":{"amount":"+0.8489267230033875","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":"Q1758227$421F600D-B354-49E1-BA2B-C61600655994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5674f8fc09fc81bb6f6ecac2b2a452dfa535591a","datavalue":{"value":{"entity-type":"item","numeric-id":2350945,"id":"Q2350945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88e9aa7d08922b85dfcbde84c8845eb9f3cb2251","datavalue":{"value":{"amount":"+0.8434436917304993","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":"Q1758227$2F3706D9-8766-4F65-8074-427485127198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6d974ec71a98caa45572bd48e73adbcb221b0e8","datavalue":{"value":{"entity-type":"item","numeric-id":5279227,"id":"Q5279227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"500fa1847288cecf1e1b7bf3b2af5024cf640823","datavalue":{"value":{"amount":"+0.8417881727218628","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":"Q1758227$557D16CB-81B1-4D4B-8E9C-0F828B0D221B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Amalgams of finite inverse semigroups and deterministic context-free languages.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Amalgams_of_finite_inverse_semigroups_and_deterministic_context-free_languages."}}}}}