{"entities":{"Q1099641":{"pageid":1110393,"ns":120,"title":"Item:Q1099641","lastrevid":49145980,"modified":"2026-01-06T16:20:17Z","type":"item","id":"Q1099641","labels":{"en":{"language":"en","value":"On the decidability of some problems about rational subsets of free partially commutative monoids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041310"}},"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":"Q1099641$901DE319-2284-4268-BB05-69092269BF9C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a96f24cd8a2cea520dfc999016fdee8b8f25768a","datavalue":{"value":{"text":"On the decidability of some problems about rational subsets of free partially commutative monoids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099641$AD9C88BF-1721-47EF-8B01-F3530F5BCCD3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"218e8b448d065c7c52765cd9cafc814bf0be2ef9","datavalue":{"value":"0638.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$669F8E53-2568-4140-B296-E3F6EC5F2471","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"49252ae5d9535a2deeaea7ead7f23e04d4a66d89","datavalue":{"value":"10.1016/0304-3975(86)90101-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$CA24751C-E47B-47D3-9338-F002B83DF68C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"446a873621e510ca421dac98a0ecf4b1b1cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":313971,"id":"Q313971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$54875BA5-DF3E-4870-98AD-439D8DD1FC22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c2007c012e2066d8cc629304090204741e0baae","datavalue":{"value":{"entity-type":"item","numeric-id":1107327,"id":"Q1107327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$8C867469-5ABB-4026-994B-C90775173B5C","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":"Q1099641$5E3F44C5-57E1-4896-B130-D47B7E7A9CB0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1099641$7C244A32-AA25-4706-B1BC-F2F44154BB8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0a3d6d35b0b7c4f468365d5b7fd1f3038a7f996","datavalue":{"value":"http://wrap.warwick.ac.uk/60778/12/WRAP_cs-rr-079.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099641$7F33C3F8-4BF9-4524-9850-C22117C4C6EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e317aff4bb76b09f138b5291a8df70b1eb63631","datavalue":{"value":"Let \\(I=A\\cup B\\) be a partially commutative alphabet such that two letters commute iff one of them belongs to A and the other one belongs to B. Let \\(M=A^*\\times B^*\\) denote the free partially commutative monoid generated by I. We consider the following six problems for rational (given by regular expressions) subsets \\(X,Y\\) of \\(M\\):  \\[ (Q1): X\\cap Y=\\emptyset? \\quad (Q2): X\\subseteq Y? \\quad (Q3): X=Y? \\quad (Q4): X=M? \\quad (Q5): M-X \\text{ finite?} \\quad (Q6): X\\text{ is recognizable?}  \\]  It is known [see \\textit{J. Berstel}, Transductions and context-free languages (1979; Zbl 0424.68049)] that all these problems are undecidable if Card\\(A>1\\) and Card\\(B>1\\), and they are decidable if Card\\(A=\\) Card\\(B=1\\) (Card\\(U\\) denotes the cardinality of U).    It was conjectured by \\textit{C. Choffrut} that these problems are decidable in the remaining cases, where Card\\(A=1\\) and Card\\(B>1\\). In this paper we show that if Card\\(A=1\\) and Card\\(B>1\\), then the problem (Q1) is decidable,and problems (Q2)-(Q6) are undecidable. Our paper is an application of results concerning reversal-bounded, nondeterministic, multicounter machines and nondeterministic, general sequential machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099641$AACED55E-DA45-4C09-B215-E56F5DBAD449","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$57880265-C14D-4B95-A1E7-245407CA1B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$D1E9D2B1-DCDB-439D-9D22-3CDD3191D235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$3CBDAE87-60AD-451D-A999-DF20BEDC2A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$BA2825EA-7EA5-4187-9B9C-6BF6FE385220","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"002742a5fe13f63294450483d1f8f62ba1210a93","datavalue":{"value":"4041310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$F846AB75-7272-4767-894D-B650624E05C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6e39485aee225ec4a293d088b1dfc560fb50c51","datavalue":{"value":"decidabilty","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099641$9B7E8E25-16DB-4BBA-A41D-8696128E2F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0b298d413e9fd7d290cff246ab71c9eba812305","datavalue":{"value":"rational subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099641$AB176AAF-E44D-4941-B3B2-CDFA272C3237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17e9efccf80d0dddb7e99616ac28a0706679bc76","datavalue":{"value":"free partially commutative monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099641$0C94273D-DEA9-42ED-BB51-93571DDE78BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb8d04c869a7c957a2fb637bf61f6c6b39fe9a39","datavalue":{"value":"regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099641$23D7A80A-8B62-404E-86E8-2734C01B78C9","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":"Q1099641$473919EA-0B51-4615-BFE1-5E46BD7EBD50","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1bf17aa2aed5959067513d80fe95c4097dc7811e","datavalue":{"value":"W2035413543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099641$A657D4D8-D878-4793-A34D-97E9EAB2F4CA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$C12D9CDD-7D1C-4746-A6FA-8C3F7C4EAFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266e74dfc49b54318e6f3c94ba097b82b39ab983","datavalue":{"value":{"entity-type":"item","numeric-id":3947146,"id":"Q3947146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$509DF075-12C7-4C7E-8D22-6F12A2D7F984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd38e96fe91088bafb7ca44aca7e38df28082445","datavalue":{"value":{"entity-type":"item","numeric-id":4728262,"id":"Q4728262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$89078C60-A5E2-4F74-95DB-D025A425A0C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182981e0e770b39d22d2da0fccd0d6dd8798182f","datavalue":{"value":{"entity-type":"item","numeric-id":4140393,"id":"Q4140393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$43459DBD-BAB7-4265-97E5-AC2B2F94A2C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9684d84be3b8355a2edee9961c6843594427ba04","datavalue":{"value":{"entity-type":"item","numeric-id":4167584,"id":"Q4167584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$4572C180-55FA-4B25-84C0-4950B9326CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4882aab3f5763a57154468372c56e809350f14d5","datavalue":{"value":{"entity-type":"item","numeric-id":3698316,"id":"Q3698316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$E8CCBDE1-DBB0-43CE-B075-20C108D4BECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c150383cc0fa67f4b0991eea16def9222670642c","datavalue":{"value":{"entity-type":"item","numeric-id":3336723,"id":"Q3336723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$5D7E370C-8462-4D01-A54F-3BF8A67F7CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a183afa5d41db8ddb84d7d54bb187fead798b2d","datavalue":{"value":{"entity-type":"item","numeric-id":3947145,"id":"Q3947145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099641$717B7A6D-7775-4603-B843-0D2145E5BC12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89d9f76202a74c75061e7f8d5b384b46f8b59c35","datavalue":{"value":{"entity-type":"item","numeric-id":2266128,"id":"Q2266128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d5cd361dd8c9341e9b89bd3307b0e317364639b","datavalue":{"value":{"amount":"+0.8239555358886719","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":"Q1099641$8108E534-671B-43FC-A4EF-B25E6AD1A878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db522d13b6a457586f78f2e4d1ce2d536dcadfaa","datavalue":{"value":{"entity-type":"item","numeric-id":1086682,"id":"Q1086682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc936ea0141a7b36964c227545e9e1dce8305e01","datavalue":{"value":{"amount":"+0.8202033042907715","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":"Q1099641$1027DAE4-9A88-40E6-9558-C09943AE0A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8531acb214371c130d640e7f8e1a587ce6d07a7","datavalue":{"value":{"entity-type":"item","numeric-id":2378535,"id":"Q2378535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2b5e5fa41e4696ed7447e82fdeee29dba0e7eb7","datavalue":{"value":{"amount":"+0.8031690120697021","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":"Q1099641$F6DB1E6A-768B-4D24-A7B1-DF179252E6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88add304504bfc87578bb0c605da1a0fb8488473","datavalue":{"value":{"entity-type":"item","numeric-id":3725561,"id":"Q3725561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e59d9521372824d2199adc56513afd0e5ed63e46","datavalue":{"value":{"amount":"+0.8022982478141785","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":"Q1099641$94041BE6-88A4-4E60-B534-A276DB348B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3e5af98d1da1cd2bb10314d9d8cd73c7bca3bee","datavalue":{"value":{"entity-type":"item","numeric-id":1111703,"id":"Q1111703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce72f809aed1730583fb6998a8f92fe970f8b030","datavalue":{"value":{"amount":"+0.8010973930358887","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":"Q1099641$3EDFD9CB-C835-469E-A42B-3C0BD38AB537","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1099641","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1099641"}}}}}