{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00032378","sets":["1164:2592:2686:2687"]},"path":["2687"],"owner":"1","recid":"32378","title":["弱可逆有限オートマトンの分解に関するいくつかの結果"],"pubdate":{"attribute_name":"公開日","attribute_value":"1994-11-18"},"_buckets":{"deposit":"22acd366-bb44-496c-b418-8ed953867fd1"},"_deposit":{"id":"32378","pid":{"type":"depid","value":"32378","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"弱可逆有限オートマトンの分解に関するいくつかの結果","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"弱可逆有限オートマトンの分解に関するいくつかの結果"},{"subitem_title":"Some Results on Decomposability of Weakly Invertible Finite Automata","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1994-11-18","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"群馬大学工学部情報工学科"},{"subitem_text_value":"群馬大学工学部情報工学科"},{"subitem_text_value":"群馬大学工学部情報工学科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Computer Science, Gunma Univercity","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science, Gunma Univercity","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science, Gunma Univercity","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/32378/files/IPSJ-AL94042003.pdf"},"date":[{"dateType":"Available","dateValue":"1996-11-18"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL94042003.pdf","filesize":[{"value":"1.2 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"f6806ef1-dc85-4e09-a998-5a0167c32103","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1994 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"鮑豊"},{"creatorName":"五十嵐, 善英"},{"creatorName":"于小梅"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Feng, Bao","creatorNameLang":"en"},{"creatorName":"Yoshihide, Igarashi","creatorNameLang":"en"},{"creatorName":"Xiaomei, Yu","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本論文で取り扱う弱可逆性有限オートマトン(FAと略記する）は入力系列を同じ長さの出力系列に変換する変換器である。長さt+1の入力系列の最初の文字が出力系列と初期状態から一意に決るとき、その変換器を遅れtのWIFAという。入力アルファベットと出力アルファベットが同じで、その大きさがnである変換器をn?WIFAで表す。n>1のとき、二つの遅れ1のn?WIFAに分解できない遅れ2のn?WIFAが存在することを示し。任意の素数pについて、遅れ1のp?WIFAは遅れ0のn?WIFAと単位遅れ回路に分解できることを示す。また2?WIFAが遅れ0のWIFAとk個の単位遅れ回路に分解できるのは、Mの全ての状態が遅れkを持つとき、かつそのときに限ることを示す。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A weakly invertible finite automaton (WIFA for short) is an invertible transducer which converts a finite input string into an output string of the same-length. A finite automaton is called a WIFA with delay t if and only if the first letter of the input string of length t+1 is uniquely determined by the coorresponding output string and the initial state. The composition of two WIFAs is their natural concatenation, which is again a WIFA whose delay is the sum of the delays of the two WIFAs. Previously, seldom is known about the decomposition of a WIFA into the WIFAs with smaller delay. In this paper We present various results on this subject. The interest of this topic comes from both theory and application aspects. In order to capture the essence of the decompposability problem, we only conc entrate on the WIFAs such that the output alphabet is the same as the input alphabet. We call M=(X,X,S,δ,λ) an n-FA if |X|=n. We prove that for any n>1, there exist some n-WIFAs with delay 2 which cannot be decomposed into two n-WIFAs with delay 1. and that for any prime number p, every strongly connected p-WIFA with delay 1, can be decomposed into a WIFA with delay 0 and a delay unit. A delay unit is a special WIFA with delay 1, which is actually a logic memory cell. For any 2-WIFA M, M can be decomposed into a WIFA with delay 0 and k connected delay units if and only if all the states of M have delay k.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"24","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"17","bibliographicIssueDates":{"bibliographicIssueDate":"1994-11-18","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"100(1994-AL-042)","bibliographicVolumeNumber":"1994"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"updated":"2025-01-22T16:11:31.694170+00:00","created":"2025-01-18T23:01:29.024542+00:00","links":{},"id":32378}