{"entities":{"Q493655":{"pageid":495422,"ns":120,"title":"Item:Q493655","lastrevid":62257650,"modified":"2026-04-11T04:51:32Z","type":"item","id":"Q493655","labels":{"en":{"language":"en","value":"Restarting transducers, regular languages, and rational relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6478535"}},"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":"Q493655$36BAA008-6050-40C0-AEF9-1B4E4517CA6A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6883a679531c72bc93a528fe6f7aa12ada2a6456","datavalue":{"value":{"text":"Restarting transducers, regular languages, and rational relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q493655$5B127C13-3A05-4116-A14C-7DFCF959B4CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d9eac3ad4ce1305f0c11cf4dc89994983fd19c6","datavalue":{"value":"1339.68149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493655$B95CAC3F-B9DD-4FDF-B276-D7B1371F084E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0e5c5fc848d568621d8bd53077c01095ad03bba","datavalue":{"value":{"entity-type":"item","numeric-id":493654,"id":"Q493654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$1C6FE4C7-E2BF-4BC5-89A6-6D7EC7F155CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f46c7c00558d7121734d489049799fa24953dd04","datavalue":{"value":{"entity-type":"item","numeric-id":287428,"id":"Q287428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$8E332D38-0854-438A-80A6-53230C06129A","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":"Q493655$3C757544-ED1C-4147-8045-60E146E9D324","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"78c696a28fe9bd077d52d8c9c7a03ea79d54978b","datavalue":{"value":{"time":"+2015-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q493655$EB9CC9D7-6A9B-441A-B546-717DC79D5DA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e9b01a10e359959d9ca1481368114a210b42f75d","datavalue":{"value":"The paper deals with variants of finite state automata equipped with the ability to delete a currently scanned letter of the input word and then move its head back to the beginning of the input, without forgetting the current state; they are called non-forgetting restarting automata with read/write window of size one. Additionally, these automata are required to be monotone, in the sense that the distance between erased letters and the end of the word does not increase. First, it is proved that such automata accept only regular languages. Then, transducers with such underlying automata are studied. Certain variants of these transducers are proved to define exactly some basic classes of rational relations; in particular, it is shown that deterministic transducers, which are not required to move the head to the beginning immediately after deleting a letter, define precisely all rational functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$DCF95929-0701-4C84-A224-B989E625B191","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e360e835094103aee0817dd4cb43ec4ae2adb196","datavalue":{"value":{"entity-type":"item","numeric-id":443745,"id":"Q443745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$A5596732-0E1B-4E97-82E6-F43F27378645","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493655$17E7F437-67D2-4488-95F3-1D46EAFCC1E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eb868c421a597d80931d66916c63f5ede6b45f3e","datavalue":{"value":"6478535","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493655$F21272F1-4159-4AAB-BC04-68F4BF8975D0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47b73eaf055fa5c5651be12b099d226baddd2407","datavalue":{"value":"restarting automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$E10E6322-071A-4278-8C5E-4BC00DC4F7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea9b35a533d874f0a32d77e584c8b61e0e7c2fe","datavalue":{"value":"regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$F90DB644-5CD9-4A68-B9E2-F456EDBF8895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53b488afee186dd8c316e7fd1025e1d4c49c9607","datavalue":{"value":"restarting transducer","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$74EF0A52-38B6-45C4-B2E7-E8B24F7EFA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"549f0f1b66c36f8f80b8f33e286a1ff6b5444b18","datavalue":{"value":"rational function","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$06B43B29-8906-4A2F-AEB7-42CFC2F8A3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82f48942922ac3c033aaafe9e8aec55b8b05de36","datavalue":{"value":"rational relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q493655$A4542BA5-7981-4359-BC34-C98DD466B26A","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":"Q493655$9C4DABAF-890C-4A9F-8452-5C14DD1AE2C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d27372e56757b9ba9403abee8c405ffd88f1a70c","datavalue":{"value":"https://doi.org/10.1007/s00224-014-9579-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q493655$F513E418-9C2C-4367-B8AE-3930350706CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a4f77865416efc0f6c93a42b65fca1e0a657404","datavalue":{"value":"W2089148617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493655$1884E4E8-BFCE-4050-975B-B291BCC7B62B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c44edb19f28965339b74cf5f321d211225af1d5","datavalue":{"value":{"entity-type":"item","numeric-id":5563368,"id":"Q5563368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$0642A9E8-44F9-46E6-947D-6BEE0C5A7413","rank":"normal"},{"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":"Q493655$D303E5C1-4F59-4049-A11B-48720C6712FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20a4c0f576c2e98ed7f1726c78894d24b07d8751","datavalue":{"value":{"entity-type":"item","numeric-id":1383712,"id":"Q1383712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$5094C931-5070-49B4-9DB3-D9EC90035A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f1311c15dbc9d474d0748f2a9141b58d23b60d2","datavalue":{"value":{"entity-type":"item","numeric-id":3657458,"id":"Q3657458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$77063813-DD08-43C7-A546-AE8DFFD7315E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80a88a78b80bffe3fa4fe466a637aaf355fd08d2","datavalue":{"value":{"entity-type":"item","numeric-id":5573974,"id":"Q5573974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$88529678-3CC2-444F-B4E6-176017F51D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$19C8B9E5-46CA-4012-8977-C8F64874FF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09577fc8f859802b497145cfc05577e464aa73af","datavalue":{"value":{"entity-type":"item","numeric-id":5199973,"id":"Q5199973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$B0894578-A058-431C-A535-03D51E99F282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5056c52d311b9489025ccfc45c81a38a5994c4","datavalue":{"value":{"entity-type":"item","numeric-id":2890203,"id":"Q2890203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$98848985-A24D-4797-B53C-D2C6A37BB7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa2ed3a15e24b5c294c748e7d8cc944c2220fd3e","datavalue":{"value":{"entity-type":"item","numeric-id":3073635,"id":"Q3073635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$11D3448A-48ED-4AA4-A682-B1B3BDF7D579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"082805638f73651f41b875b7dfb32ce3fb85b7b4","datavalue":{"value":{"entity-type":"item","numeric-id":3517257,"id":"Q3517257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$BAE65D0E-E910-4967-8B4B-C800FFE7F13F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85130355225ee80b5f151339399b037ebf95a436","datavalue":{"value":{"entity-type":"item","numeric-id":5055900,"id":"Q5055900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$7848B487-66E3-4153-BB58-04AA043AF9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3beed1f92ab5ab34306ff333cdeab4d5f826e7da","datavalue":{"value":{"entity-type":"item","numeric-id":4934755,"id":"Q4934755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$EAC27E7F-5D16-44D3-B5F6-0716C4CC7CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"979c25617ae86ee5c768d794cd353170e40b3691","datavalue":{"value":{"entity-type":"item","numeric-id":948085,"id":"Q948085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$2186A56F-5AAF-42A6-A65D-F73F0472686C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7748e3b3234df9858cc64324ecb25fec8864d7bb","datavalue":{"value":{"entity-type":"item","numeric-id":3798271,"id":"Q3798271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$B3F9FD09-AEBC-49E9-91D6-8CFA0B72AAB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"702180279b1e47de558db2e7b1c9bb04e09ddc80","datavalue":{"value":{"entity-type":"item","numeric-id":3401482,"id":"Q3401482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$1F695BE0-7F50-4F4D-B3E3-3BCC6DEDB77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf090b2d4ce16527f1fd1e00a1853ff2975f81d9","datavalue":{"value":{"entity-type":"item","numeric-id":3620621,"id":"Q3620621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$5855CE8C-0B63-430A-ABF8-D9123ADA904F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8de6f421b3061e94b252ede6dd00fe1e85836d5a","datavalue":{"value":{"entity-type":"item","numeric-id":633765,"id":"Q633765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$7F43B536-ECBE-4607-8CA9-6DCAC9A72287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d03f3c417b59d2fa04cf690f1d6137c2826ac78","datavalue":{"value":{"entity-type":"item","numeric-id":4531378,"id":"Q4531378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$D5E6FCC9-9DDC-4E2D-9B77-F053EA273DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"934c275563422ae7bd3015e3efe9b3094ea6f438","datavalue":{"value":{"entity-type":"item","numeric-id":4654646,"id":"Q4654646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493655$327EBFF6-E8C4-4D62-A648-FC004B8F283A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84fd68d6d6043692f804eee7d252c7b1a901be1d","datavalue":{"value":"10.1007/S00224-014-9579-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493655$04673195-2EDF-4324-8433-15CBF7ED2FED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dbb42c5ec23c9bc15ed8c6baa435a537a2a9db3","datavalue":{"value":{"entity-type":"item","numeric-id":2890203,"id":"Q2890203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2725601be78129561890636d204b7ebba1197fb2","datavalue":{"value":{"amount":"+0.8587270379066467","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":"Q493655$A4031671-EE21-4C2F-A10A-DF2195810628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"262e17c557882a6cf28b5144950d0f60c326d998","datavalue":{"value":{"entity-type":"item","numeric-id":5199973,"id":"Q5199973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e4defadd3042c1404779ade90cfc75ca3373462","datavalue":{"value":{"amount":"+0.7823505401611328","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":"Q493655$927123A2-F641-4DEE-9023-5A05B647EAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5f3b4e0cd0bd25751f30b788819fcd274a6b3c","datavalue":{"value":{"entity-type":"item","numeric-id":3451119,"id":"Q3451119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd9e6a3a9e58eacbdd562568a7525b50d7041c84","datavalue":{"value":{"amount":"+0.7764241695404053","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":"Q493655$E7282D89-3D15-474C-AB86-26E0F9426D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de20421c1bb7f64c6418bbf4f0d0129ad4ed3ba9","datavalue":{"value":{"entity-type":"item","numeric-id":3434699,"id":"Q3434699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69f271868d8e90ead467ae2f226f8c128fe6dbb3","datavalue":{"value":{"amount":"+0.773032546043396","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":"Q493655$1DFCE18B-237C-4367-A765-B23196A8775C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ee9ec52c62f315fcea1dd3412e5f2774716e3c4","datavalue":{"value":{"entity-type":"item","numeric-id":5055900,"id":"Q5055900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"729dca3e59b4cd1f63efe73d317bfee7177e6ff6","datavalue":{"value":{"amount":"+0.7634393572807312","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":"Q493655$0FD01304-CC42-4A60-9E4E-397F40845D38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Restarting transducers, regular languages, and rational relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Restarting_transducers,_regular_languages,_and_rational_relations"}}}}}