{"entities":{"Q705067":{"pageid":706916,"ns":120,"title":"Item:Q705067","lastrevid":63759957,"modified":"2026-04-11T15:21:39Z","type":"item","id":"Q705067","labels":{"en":{"language":"en","value":"Existential and positive theories of equations in graph products"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2130947"}},"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":"Q705067$5E1E3FDD-5EF2-4D85-A71F-745B864E1602","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"740053a282156bd695c5123ae46ae5199674853d","datavalue":{"value":{"text":"Existential and positive theories of equations in graph products","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705067$5C3C395F-C1FF-4087-AFD5-6966E001FC21","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c48e9fe9ea59227f0856f3eaf956563c04d1097f","datavalue":{"value":"1067.03017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$0DDEF3DC-7582-49FD-8D8C-5083CA6DE346","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"81c83c28843efefafe1f80734e19c2e6ff309a9c","datavalue":{"value":{"entity-type":"item","numeric-id":213104,"id":"Q213104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705067$2437E7ED-48DB-4017-A974-D9B34E1D9666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db8f30a521e20eb0f40199bc337d407bb71223c1","datavalue":{"value":{"entity-type":"item","numeric-id":269346,"id":"Q269346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705067$799F9443-33B7-468E-9BD7-9D06C1D6EC19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705067$A8CA9A3C-2E80-4D91-BF9C-D07E2C5D6903","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1590bd54b214ce942d11ecbfe0ede26ab9b97ec","datavalue":{"value":{"time":"+2005-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705067$DEC52845-F738-406D-8CE2-BC08B2DC1867","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"27ae54b59dddc6a83b8253f09f8a1a402c135007","datavalue":{"value":"In this article it is proved that, for a fixed graph product \\(\\mathbb P\\) of finite monoids, free monoids, and free groups, the existential (i.e., sentences in prenex normal form without universal quantifiers) theory of equations can be decided in PSPACE. Moreover, when the equations have normalized rational (NRAT\\((\\mathbb P)\\)) constraints, the problem becomes PSPACE-complete. Another main result states that, for graph products of finite and free groups, the positive (i.e., sentences without negations) theory of equations with recognizible (REC\\((\\mathbb G)\\)) constraints is decidable. These results continue the stream of research on decidability of theories of equations on monoids and groups started by \\textit{G. S. Makanin} [Mat. Sb., Nov. Ser. 103(145), 147--236 (1977; Zbl 0371.20047)]. The results in this paper are based on the main result of \\textit{V. Diekert} and \\textit{A. Muscholl} [Lect. Notes Comput. Sci. 2076, 543--554 (2001; Zbl 0986.20036)] on existential theories of equations in trace monoids with involution. This result is used within the underlying trace monoid with involution of the graph product. It is proved that, for an existential sentence \\(\\phi\\) with constraints in NRAT\\((\\mathbb P)\\), there exist an existential sentence \\(\\phi'\\) such that \\(\\phi\\) holds in \\(\\mathbb P\\) if and only if \\(\\phi'\\) holds in the underlying monoid with involution. In this reduction, a specific confluent trace rewriting systems is used. The decidability of the positive theory of equations with constraints in REC\\((\\mathbb G)\\), where \\(\\mathbb G\\) is a graph product of finite and free groups, is proved in two steps. Firstly, it is proved that it possible to restrict the investigation to graph products of a particular type, and, secondly, the positive sentences with constraints in REC are reduced to existential sentences with constraints in NRAT. The result then follows by the first result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$201DB1E1-ACB8-4D11-AA91-D3A4B937010E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9dce5c88da99cb4b1021e2cac25a18f2fa317715","datavalue":{"value":{"entity-type":"item","numeric-id":287018,"id":"Q287018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705067$E4305CB3-75B7-4268-9801-1FC80A08071E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$B3679704-661B-490C-B50D-BB584191B594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$72C02751-23E4-4F04-9B68-00813A5A3B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$F3B3FCAE-8073-431F-AA58-B50091151CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$F30810CE-D63B-4197-A1D8-0E5628EAD714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$1A694EEC-3A94-4D22-B4AC-A5CFBA9C3184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$F36BC4EC-5D07-494E-9F84-10E5341D697E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$CCB75F24-DEDE-4B8C-8A0A-DCC37E2440C7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f60256fa4eab4a48ac4a5cda0f54be9d3f91889","datavalue":{"value":"2130947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$928AD639-B4D7-4367-A801-E813899B9B88","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22bfb5290267123d54bba59d5bb5699bc262a8ca","datavalue":{"value":"graph product","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$2F537042-5D00-4A99-B59D-DAB5F9BF6A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15167c944b1085c17bcbb300e741b3e077562d3e","datavalue":{"value":"trace monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$95F1630B-0B72-48DC-A650-E5884D8C0641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d095bd6cc24eec27ac4215660390f5b0d0cf34c","datavalue":{"value":"existential theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$AE048D7C-3F76-4BD5-A125-0578FA46C16E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b58607a23002f1ed7236d38d508c9214da49f7f","datavalue":{"value":"positive theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$062EB56C-8DEA-4523-82B5-5417B12D0413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$A2D7389E-5F98-4B36-A30A-E9FED3A55A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c107bb63de79565718d188b33fcc483957cfdd","datavalue":{"value":"PSPACE","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$094EBA27-5476-425D-AF87-328643AC6CDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$867645BB-0076-43C0-B0B1-7C025468C4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b241c2e53ac9c4073e4f6a37f6442b7c79d7d","datavalue":{"value":"free monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$A4D642E3-25D7-404D-A3EE-3A73A6996992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffb9b557bffdfa5cd70d593a7ec3f8594345072","datavalue":{"value":"free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q705067$E353834D-1BF3-4169-8C2E-12FFA067F61D","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":"Q705067$1C65D652-6278-4D26-BE2A-5C66C5922BB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2fddbb54ba23ec8db4e2e242d2dc56be013e8c5a","datavalue":{"value":"https://doi.org/10.1007/s00224-003-1110-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q705067$38137764-1CD9-4394-8906-62DF384E85ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c553ca3a36b6ce7f11d0e662456a3327e4221b88","datavalue":{"value":"W2090997504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$D75D3369-D1E0-4705-A117-EF31BF92A816","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e9edee9b179fe1bdc8fa32b80d1a947b2bf8daf3","datavalue":{"value":"10.1007/S00224-003-1110-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705067$4EF435DA-E48E-4DA9-8F01-232F4EB3EC5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d06dc04df624d2612a720dcb8a49ae1366b926c2","datavalue":{"value":{"entity-type":"item","numeric-id":4736866,"id":"Q4736866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc46660a5f61a39fe23b79fcf9ec8497afbe488","datavalue":{"value":{"amount":"+0.99999976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$E551FC27-C506-4D6F-87B2-B5B9F745084F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cacbf1b8db4847367e2d78922e7576cd0d3461c","datavalue":{"value":{"entity-type":"item","numeric-id":2212708,"id":"Q2212708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a746f68974e4387d549bb48ec4b9cdfa42dc5644","datavalue":{"value":{"amount":"+0.87586945","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$0B0DB340-3560-4D7B-BCD9-38E273DC6F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1384ca90a6847d404e5f06f4dab11bec97f038c1","datavalue":{"value":{"entity-type":"item","numeric-id":1901893,"id":"Q1901893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ab1ba43ec19d0b308b8bbcada0930e5b9dc7bc9","datavalue":{"value":{"amount":"+0.8705812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$61A67416-5638-408E-A03F-957283EA7DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf6b8126603b7d281d4c08e777fe02919b55e34b","datavalue":{"value":{"entity-type":"item","numeric-id":3809777,"id":"Q3809777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68f0640ff524c5ec8192c825c79ab6478712ece6","datavalue":{"value":{"amount":"+0.8687951","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$FDEECBC9-A26A-472C-8F0C-C7F1B4D28AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b8ffbee8d3b56b2f110cd62f9cb84db8c8b94c1","datavalue":{"value":{"entity-type":"item","numeric-id":4631973,"id":"Q4631973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a4b36714eb353192c8fad36a73c17433e616a3a","datavalue":{"value":{"amount":"+0.85503006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$E0D9CD89-F0A4-4356-BD32-5046E03CB1DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"967e8e3abf5ee8837a570c44a1e24bb64cd25178","datavalue":{"value":{"entity-type":"item","numeric-id":4348001,"id":"Q4348001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6cef13ea525aa314a581cacf8cf7351b0c43658","datavalue":{"value":{"amount":"+0.85279393","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$08290873-627A-498C-AECB-511D37A3EDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"241a4336503c1bbf1259487f5f10938ea76db5dc","datavalue":{"value":{"entity-type":"item","numeric-id":2671599,"id":"Q2671599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9746d81b11ade2c2378953eeb284281f348a86ed","datavalue":{"value":{"amount":"+0.848607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$779643C5-4E22-40FE-BB85-F33168A5D600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bc91298d5a2e8f97e0f044e8f314a958647b58d","datavalue":{"value":{"entity-type":"item","numeric-id":2710602,"id":"Q2710602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"958347e26dfb96e29da2198ce0496359d8e65275","datavalue":{"value":{"amount":"+0.84843385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$18CEB9B3-1C01-4BC5-AD62-E9AFC09C9AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7073a4de9f33e23d9503581daeac03c4cd4f816","datavalue":{"value":{"entity-type":"item","numeric-id":1987109,"id":"Q1987109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"639da6027b4ecf09d949deeeea9a5bfca330eba8","datavalue":{"value":{"amount":"+0.84638166","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$703681B5-70B3-46B3-A32F-B9EBB29B23F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a41f1edd09350e58c74928ee6b73e6100e8611c8","datavalue":{"value":{"entity-type":"item","numeric-id":2452678,"id":"Q2452678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3ada5c2ce051bd0f0a61cf217e5518145a44fcd","datavalue":{"value":{"amount":"+0.8452283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q705067$A26178C6-35AF-40F5-9D7E-C0C28F3AD08D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Existential and positive theories of equations in graph products","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Existential_and_positive_theories_of_equations_in_graph_products"}}}}}