{"entities":{"Q1179182":{"pageid":1189931,"ns":120,"title":"Item:Q1179182","lastrevid":42300383,"modified":"2025-06-04T14:31:19Z","type":"item","id":"Q1179182","labels":{"en":{"language":"en","value":"Decidability problems for unary output sequential transducers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 24093"}},"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":"Q1179182$CF2A7B8F-745C-46CB-B3C6-9B96EE6A7E57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49ebb3c31b7f9323588fb195ea90169511680556","datavalue":{"value":{"text":"Decidability problems for unary output sequential transducers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179182$851F831B-1FFB-4CA7-A357-C1493D59A04F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7aaaaaaeeef8bb9c3d8f7e0801c87e295b1ead35","datavalue":{"value":"0743.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179182$2E43B8EB-5594-49D6-9953-C2BCCE07FC4B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ced0c13053343f480d8fc5be889ad3ed25b10b6","datavalue":{"value":"10.1016/0166-218X(91)90096-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179182$0E57EADD-3F2C-4FCC-A3F9-75FF761A2D1B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5eb12e286e978a89b59265932583f917042300b","datavalue":{"value":{"entity-type":"item","numeric-id":598183,"id":"Q598183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$8EE902C7-D1E8-41EC-990E-9DA28DB11BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e1040094bf74402ed6fa4c78436dda64e324757","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$A6C54800-7B1E-4F7C-86A6-59D1024DEA31","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$7C9B17CE-14C2-4EB0-A0DC-B70BF0AE4765","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179182$72956E47-DCD8-4E77-B0CC-5DA55F1E3A84","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"644008ba1d21e7ea96a6af012477f5940420e72c","datavalue":{"value":"By a well known theory of \\textit{Ibarra}, the equivalence problem for unary output sequential transducers (that is, nondeterministic generalized sequential machines having accepting states) is undecidable. This is the case even if one of the transducers is a finite substitution which, on the other hand, is a special composition of morphisms and inverse morphisms called morphic composition.   Using a normal form for morphic compositions due to \\textit{M. Latteux} and \\textit{P. Turakainen} [Math. Syst. Theory 20(4), 261-271 (1987; Zbl 0638.68087)], the authors first prove that it is decidable whether or not a given morphic composition is equal to the finite substitution used by Ibarra. The problem is reduced to the emptiness problem for counter languages being decidable. Then using Ibarra's theorem they show that it is undecidable whether or not a given rational transduction is a morphic composition.   In contrast to Ibarra's theorem the authors prove that it is decidable whether or not two given unary output sequential transducers are multiplicitly equivalent, that is, whether the transducers have equally many computations for each input/output pair.   Using Ibarra's result again it is shown that it is undecidable whether or not two given generalized finite automata (that is, finite automata capable of reading words while performing a computation step) are equivalent when also the lengths of the computation are taken into account. Also some other related decidability results are established.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179182$087CD9FE-E3DC-4015-B521-A55B382D9CC9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b5825a72a857aefa8d65d6208cfbd36a98a782ee","datavalue":{"value":{"entity-type":"item","numeric-id":1163381,"id":"Q1163381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$554D890E-D6BD-4920-AC60-FAB8D5619536","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179182$314C7CF5-8357-4BAC-A9EF-500D03CFFE53","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dcf7c68e8081d2770f8820e523d08e473698b73b","datavalue":{"value":"24093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179182$FFCE629E-14A3-44B2-924D-342A85378E7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040b5ec6f2cd3f9b94d75e1a076c6df9e5a5c289","datavalue":{"value":"sequential transducers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179182$6607972F-DF19-40DC-A31A-5696EB10680E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29cb51eb06c0b5b47195b42f6707e32af88e16f3","datavalue":{"value":"morphic composition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179182$99C82CF7-389A-4A53-A5E6-A3458B564DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179182$B7F61A97-92E5-4903-A2F0-2801A16B518A","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":"Q1179182$CB159E59-2315-4044-88CC-A4B9376AE80C","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":"Q1179182$AAA65DFF-7EDB-420E-9FAC-A2D424CD1380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$59B0DA2F-5ED4-4E3B-B6A2-125240631A1A","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":"Q1179182$6AC7C347-06DD-422B-8B5C-54036A25E102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bef445b94f796006d9d98abaf7a953e05a5e1367","datavalue":{"value":{"entity-type":"item","numeric-id":1171887,"id":"Q1171887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$6DD2954D-38C3-4FBF-A92C-86689845A6CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d4710ed058b1391d623f9ad5b2f5a085ff13f94","datavalue":{"value":{"entity-type":"item","numeric-id":3674079,"id":"Q3674079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$74BC5B5C-F388-4A01-AFC8-1CA1DB394E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d75db66ca6768003f58f01c6df92f0c7b2899251","datavalue":{"value":{"entity-type":"item","numeric-id":3779774,"id":"Q3779774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$93D99666-C33F-46BC-AEF9-9B268009EEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3dba5a36e5560eb4f6939071d9695bdcce7198f","datavalue":{"value":{"entity-type":"item","numeric-id":3804221,"id":"Q3804221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$E9E0ACA1-F107-42A9-B1E3-63F91BE384F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"457f98ff54d69a785bffc6c765772d12b20b9461","datavalue":{"value":{"entity-type":"item","numeric-id":1836994,"id":"Q1836994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179182$21E1F0A0-C8BD-4283-92F6-B9DE99CB144D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"179e1621bb4cb4818e1f0b962c4bb443f0ef4c80","datavalue":{"value":"https://doi.org/10.1016/0166-218x(91)90096-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179182$A43159A8-FE18-400D-9F1E-FEEBEADA4A4A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d4e0c2922cc43c0ebc07d87c6c243184b482ba4","datavalue":{"value":"W1988398776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179182$79C41085-C36E-4594-8A8F-F5BAC4697A89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ffa6ae9c4368a56d25226f937312e0dcfefd112","datavalue":{"value":{"entity-type":"item","numeric-id":3806848,"id":"Q3806848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5eb656c9af22e347159834c929efa2f0729a726","datavalue":{"value":{"amount":"+0.8191937","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$364F7911-6D49-46BF-85B8-4D77544066D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f71a19a531deb1ae4a4908f952b06fba5e49f469","datavalue":{"value":{"entity-type":"item","numeric-id":3736916,"id":"Q3736916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"589899fbb7b752fcc7b0ff33990ea538f9ad1291","datavalue":{"value":{"amount":"+0.8092812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$8AA2D338-040A-4FD4-8AEE-E5EDA58F54B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d786f1fb78bc79fa8d01845691b2e58b6f604532","datavalue":{"value":{"entity-type":"item","numeric-id":3219110,"id":"Q3219110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0ee3f49c9c0c8dffaf35819554539fe1ec2a3b","datavalue":{"value":{"amount":"+0.7945861","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$575943D5-B388-4DA5-9E62-7B5337780D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc8059c890634eadc28d091d837e1e2703e8fc76","datavalue":{"value":{"entity-type":"item","numeric-id":1280978,"id":"Q1280978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"692712bad785bda9a7a6bdbd55c995109b4669fe","datavalue":{"value":{"amount":"+0.76847625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$F5FEF399-E8C9-4541-B0BA-30A07BD090EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03c3e86fb6714988ded945440100cb506c5da763","datavalue":{"value":{"entity-type":"item","numeric-id":4265636,"id":"Q4265636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48dc2f0209d5ef43c8824336ee3869dcc359daed","datavalue":{"value":{"amount":"+0.763366","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$664E57FF-EBF9-45EE-93D7-B1BDAAE89DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"127a2a0511df6e7b00259d7bfc88a1ab10c03f35","datavalue":{"value":{"entity-type":"item","numeric-id":1592108,"id":"Q1592108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9a7cd1e724912e555b9410a997118c5ace9f574","datavalue":{"value":{"amount":"+0.73801506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$E1DE4323-628B-4447-9FEB-8F509FCF6D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c05a1a7223e2b693a3c2e37aa07a48008c9a0c2","datavalue":{"value":{"entity-type":"item","numeric-id":3795238,"id":"Q3795238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db98bb88f9cc40e49efbfd402080523f620be773","datavalue":{"value":{"amount":"+0.7365298","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$2894AD46-702E-4EB1-A6F1-4F30CA8FB773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6468c1b7cda368190af6b8d688c71a18c9b5f367","datavalue":{"value":{"entity-type":"item","numeric-id":4598267,"id":"Q4598267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef37bbe7a3b6e795c5ede51f1aa893ec4dd0e740","datavalue":{"value":{"amount":"+0.7326822","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$424B5268-9077-4708-85CC-DEF4E831151E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce9c93e34ad3bf7680b08bcfa32c411a370da1e","datavalue":{"value":{"entity-type":"item","numeric-id":4712653,"id":"Q4712653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d519e6a8f70cfea6e8039a508169fa62922b96fe","datavalue":{"value":{"amount":"+0.7324177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$B3F0F7DD-AB96-4992-AE23-3221FABC020D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a27bfe2df57f0f89c4e9ca718694f7af9842590f","datavalue":{"value":{"entity-type":"item","numeric-id":5444976,"id":"Q5444976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba2fda49c7881c8a78ed5e2a682c2a9759d6baa","datavalue":{"value":{"amount":"+0.7313023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179182$A74F5535-0CCD-4A61-AD8B-EF90CCB9C1A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1179182","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1179182"}}}}}