NAISTAR
Advanced Search
Japanese | English

naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
テクニカルレポート / Technical Report >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10061/3173

Title: Finite state translation systems and parallel multiple context-free grammars
Authors: Kasami, Tadao
Seki, Hiroyuki
Kaji, Yuichi
カサミ, タダオ
セキ, ヒロユキ
カジ, ユウイチ
嵩, 忠雄
関, 浩之
楫, 勇一
Issue Date: Dec-1993
Publisher: Nara Institute of Science and Technology
Series/Report no.: Information Science Technical Report ~ TR93012
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.
URI: http://hdl.handle.net/10061/3173
URI: http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100009575&oldid=16855
Fulltext: http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100009575&oldid=16855
ISSN: 0919-9527
Text Version: author
Appears in Collections:テクニカルレポート / Technical Report

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback