WEKO3
アイテム
{"_buckets": {"deposit": "d1e23ad3-3a1b-4aba-8ddf-69736efbbf99"}, "_deposit": {"created_by": 4, "id": "8845", "owners": [4], "pid": {"revision_id": 0, "type": "depid", "value": "8845"}, "status": "published"}, "_oai": {"id": "oai:naist.repo.nii.ac.jp:00008845", "sets": ["39"]}, "author_link": ["22037", "22038", "77"], "item_4_biblio_info_9": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "1993-12", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "TR93012", "bibliographic_titles": [{"bibliographic_title": "Information Science Technical Report", "bibliographic_titleLang": "en"}]}]}, "item_4_description_7": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "Finite state translation systems (fsts\u0027) are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts\u0027 and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts\u0027 equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(n e+1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts\u0027. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts\u0027 with state-bound 2 can generate an NP-complete language.", "subitem_description_language": "en", "subitem_description_type": "Abstract"}]}, "item_4_publisher_10": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Nara Institute of Science and Technology", "subitem_publisher_language": "en"}]}, "item_4_relation_18": {"attribute_name": "部分である", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_language": "en", "subitem_relation_name_text": "Information Science Technical Report"}], "subitem_relation_type": "isPartOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "http://isw3.naist.jp/IS/TechReport/", "subitem_relation_type_select": "URI"}}]}, "item_4_source_id_12": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0919-9527", "subitem_source_identifier_type": "ISSN"}]}, "item_4_text_19": {"attribute_name": "NAIST ID", "attribute_value_mlt": [{"subitem_text_value": "73292336"}]}, "item_4_text_20": {"attribute_name": "電子化ID", "attribute_value_mlt": [{"subitem_text_value": "R000633"}]}, "item_4_version_type_14": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_access_right": {"attribute_name": "アクセス権", "attribute_value_mlt": [{"subitem_access_right": "open access", "subitem_access_right_uri": "http://purl.org/coar/access_right/c_abf2"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Kasami, Tadao", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "22037", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Seki, Hiroyuki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "22038", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Kaji, Yuichi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "77", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "70263431", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://kaken.nii.ac.jp/ja/search/?qm=70263431"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2023-03-06"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "R000633.pdf", "filesize": [{"value": "294.3 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 294300.0, "url": {"label": "fulltext", "objectType": "fulltext", "url": "https://naist.repo.nii.ac.jp/record/8845/files/R000633.pdf"}, "version_id": "8f2bfe75-f181-4efb-9685-96e7dd4d4aa6"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "technical report", "resourceuri": "http://purl.org/coar/resource_type/c_18gh"}]}, "item_title": "Finite state translation systems and parallel multiple context-free grammars", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Finite state translation systems and parallel multiple context-free grammars", "subitem_title_language": "en"}]}, "item_type_id": "4", "owner": "4", "path": ["39"], "permalink_uri": "http://hdl.handle.net/10061/3173", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2006-07-31"}, "publish_date": "2006-07-31", "publish_status": "0", "recid": "8845", "relation": {}, "relation_version_is_last": true, "title": ["Finite state translation systems and parallel multiple context-free grammars"], "weko_shared_id": -1}
Finite state translation systems and parallel multiple context-free grammars
http://hdl.handle.net/10061/3173
http://hdl.handle.net/10061/31737b9a157e-9d46-4af4-a7b8-018ed29bda94
名前 / ファイル | ライセンス | アクション |
---|---|---|
fulltext (294.3 kB)
|
|
Item type | テクニカルレポート / Technical Report(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2006-07-31 | |||||
タイトル | ||||||
タイトル | Finite state translation systems and parallel multiple context-free grammars | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ | technical report | |||||
アクセス権 | ||||||
アクセス権 | open access | |||||
著者 |
Kasami, Tadao
× Kasami, Tadao× Seki, Hiroyuki× Kaji, Yuichi |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(n e+1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language. | |||||
書誌情報 |
en : Information Science Technical Report 号 TR93012, 発行日 1993-12 |
|||||
出版者 | ||||||
出版者 | Nara Institute of Science and Technology | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0919-9527 | |||||
部分である | ||||||
関連タイプ | isPartOf | |||||
識別子タイプ | URI | |||||
関連識別子 | http://isw3.naist.jp/IS/TechReport/ | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
電子化ID |