{"created":"2023-05-15T08:38:24.050793+00:00","id":1208,"links":{},"metadata":{"_buckets":{"deposit":"6cc71f73-0b10-42b3-be25-c9bef0b3ff0a"},"_deposit":{"created_by":3,"id":"1208","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"1208"},"status":"published"},"_oai":{"id":"oai:uec.repo.nii.ac.jp:00001208","sets":["9:13"]},"author_link":["7228"],"control_number":"1208","item_10006_date_granted_11":{"attribute_name":"学位授与年月日","attribute_value_mlt":[{"subitem_dategranted":"2008-03-24"}]},"item_10006_degree_grantor_9":{"attribute_name":"学位授与機関","attribute_value_mlt":[{"subitem_degreegrantor":[{"subitem_degreegrantor_name":"電気通信大学"}]}]},"item_10006_degree_name_8":{"attribute_name":"学位名","attribute_value_mlt":[{"subitem_degreename":"博士（工学）"}]},"item_10006_description_10":{"attribute_name":"学位授与年度","attribute_value_mlt":[{"subitem_description":"2007","subitem_description_type":"Other"}]},"item_10006_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Recently, the equivalence problem of arbitrary deterministic pushdown automata(dpda’s) has been proved to be solvable by S´enizergues (Theoretical Computer Science,vol.251, pp.1-166, 2001). This is a breakthrough in formal language theory. Forthis distinguished paper, he won the 2002’s G¨odel Prize, which is one of the mostprestigious prizes in theoretical computer science. The period from paper publicationto receive the prize was unprecedentedly short. This is indicative of the importance ofthe equivalence problem of dpda’s. We know that the equivalence checking algorithmplays an important role in learning systems that are formulated as automata andformal grammars. In the future, in the field of theoretical computer science, analyzingthe learning possibility and establishing adaptive learning functions will becomeimportant even further. In this regard, establishing simple and efficient algorithmsfor checking the equivalence is very important.However, the efficiency of most algorithms proposed thus far is not satisfactoryenough, and the proofs of correctness are extremely complicated. Here, the researchgroup of UEC including the author has proposed a technique called “direct branchingalgorithm” for checking the equivalence of a pair of some subclasses of dpda’s,over many years. As compared to other algorithms, our direct branching algorithmsfor checking the equivalence of dpda’s are very simple and direct, and the proofs ofcorrectness are very clear. Further, they have a good potential in analysis for their applicabilityand time complexity of various other dpda problems. As a concrete result,such an approach has been successfully applied to a pair of dpda’s, one of which isreal-time strict. Furthermore, we have shown a certain sufficient condition for checkingthe equivalence of dpda’s that have \"        -transitions. In addition, as research resultsregarding the time complexity using our direct branching algorithm, polynomial-timealgorithms for checking the equivalence of simple dpda’s and real-time strict deterministicrestricted one-counter automata (droca’s) have been given. The former hasjust one state, and the latter has just one stack symbol.On the other hand, in conjunction with research about the equivalence problemof dpda’s, some results about the equivalence problem of deterministic pushdowntransducers (dpdt’s) which are obtained by attaching the output function to dpda’shave also been proposed. In practical use, a dpdt is more important than a dpda,which only judges the acceptance, but the equivalence problem of dpdt’s is extremelycomplicated. However, by using our direct branching algorithms, the equivalenceproblems of dpdt’s are solvable with almost the same complexity level as that ofdpda’s. Our paper, which present a solution for checking the equivalence of dpdt’s, oneof which is real-time strict, is referred by the above G¨odel Prize winning paper as oneof the most important results. Most results about the equivalence problem of dpdt’sexcept ours cannot show a practical execution for simple samples, and they also cannotprovide a concrete evaluation of the time complexity. It is important to research aboutefficient algorithms for checking the equivalence of dpdt’s. In 2007, a polynomial-timealgorithm for checking the equivalence of simple deterministic languages with outputwas published by Bastien et al.In such a background, the following two results are given in this paper. First, afurther extended direct branching algorithm for checking the equivalence of a certainpair of non-real-time deterministic pushdown transducers is shown. Such a class ofdpdt’s includes a pair of dpdt’s, one of which is real-time strict. This result is consideredto be very significant in the further class extension in the equivalence problemof dpdt’s that have \"        -transitions. Second, as an improvement in the maximum timecomplexity, a polynomial-time algorithm for checking the equivalence of real-timestrict deterministic restricted one-counter transducers (droct’s) is shown. This is atypical result that is indicative of the effectiveness of direct branching algorithms.Furthermore, this result is incomparable to the above Bastien et al.’s result.","subitem_description_type":"Abstract"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"清野, 和司","creatorNameLang":"ja"},{"creatorName":"セイノ, カズシ","creatorNameLang":"ja-Kana"},{"creatorName":"Seino, Kazushi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2016-09-16"}],"displaytype":"detail","filename":"9000000303.pdf","filesize":[{"value":"956.9 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"9000000303.pdf","url":"https://uec.repo.nii.ac.jp/record/1208/files/9000000303.pdf"},"version_id":"02e571b2-0092-4410-aa6b-6722ad21ae1e"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"thesis","resourceuri":"http://purl.org/coar/resource_type/c_46ec"}]},"item_title":"直接的分岐アルゴリズムによる決定性プッシュダウン変換器の等価性判定","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"直接的分岐アルゴリズムによる決定性プッシュダウン変換器の等価性判定","subitem_title_language":"ja"},{"subitem_title":"Direct Branching Algorithms for Checking Equivalence of Some Classes of Deterministic Pushdown Transducers","subitem_title_language":"en"}]},"item_type_id":"10006","owner":"3","path":["13"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2010-03-05"},"publish_date":"2010-03-05","publish_status":"0","recid":"1208","relation_version_is_last":true,"title":["直接的分岐アルゴリズムによる決定性プッシュダウン変換器の等価性判定"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2024-02-19T05:27:41.077129+00:00"}