科研之友
微信
新浪微博
Facebook
分享链接
摘要
Rational relations are binary relations of finite words that are realised by non deterministic finite state transducers (NFT). A multi-sequential relation is a rational relation which is equal to a finite union of (graphs) of partial sequential functions, i.e. functions realised by input-deterministic transducers.
The particular case of multi-sequential functions was studied by Choffrut and Schiitzenberger who proved that given a rational function (as a transducer), it is decidable whether it is multi-sequential. Their procedure is based on an effective characterisation of unambiguous transducers that do not define multi-sequential functions, that we call the fork property.
In this paper, we show that the fork property also characterises the class of transducers that do not define multi-sequential relations. Moreover, we prove that the fork property can be decided in PTIME. This leads to a PTIME procedure which, given a transducer, decides whether it defines a multi-sequential relation.
- 出版日期2018-2
