权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Automata, Formal Language and Computation Theory

自动机、形式语言和计算理论

基本信息

批准号：
10044098
负责人：
KATSURA Masashi
金额：
$ 2.56万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B).
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

项目摘要

A deterministic automaton A =(A,X) is said to be directable if there exists a word μ∈ XィイD1*ィエD1 such that |AuィイD1AィエD1| = 1.In this case, the notion of directability can be uniquely defined. On the other hand, the directability of nondeterministic automata can be difined in several nonequivalent ways. We provide the following three notions of directability.A word u ∈ XィイD1*ィエD1 over X is said to be :(1) a D1 -directing word of a D1 -directable automation A if (∃c ∈ A) (∀a ∈A) (auィイD1AィエD1 ={c}),(2) a D2 directing word of a D2 -directable automaton A if (∀a, b∈ A) (auィイD1AィエD1 = buィイD1AィエD1),(3) a D3-directing word of a D3 -directable automaton A if (∃c ∈ A) (∀a∈A) (c∈ auィイD1AィエD1).By DィイD2iィエD2(A) we denote the set of all Di-directing word of A. Notice that the above three notions are equivalent for deterministic automata, I.e.DィイD21ィエD2(A) = DィイD23ィエD2(A). In this case, we denote these languages as D(A), we define the following classes of languages : ∠ィイD2DィエD2 = {D(A)|A : a determin … More istic directable automation}, ∠ィイD2nd(i)ィエD2 ={Di(A) | A : a nondeterministic Di-directable automaton } ∠ィイD2cnd(i)ィエD2 ={Di(A) | A : a complete nondeterministic Di-directable automaton }(I= 1,2,3).Then each of the above classes of languages becomes a subclass of regular languages, More exactly, these classes constitute a lower lattice under inclusion relation, Now we consider the class of all nondeterministic commutative automata. By ∠ィイD2DィエD2, ∠ィイD2nd(I)ィエD2, ∠ィイD2cnd(I)ィエD2, we denote corresponding classes of commutative languages, then these classes constitute a linear ordered set, For the class of deterministic directable automata A = (A, X) with |A| = n, the following Cerny's conjecture is well-known :Let A = (A,X) be a deterministic directable automation with |A| = n.By P(A), we denote the number min {|u| | |AuィイD1AィエD1| = 1}. let d(n) = max{p(A) | A : a deterministic directable automaton with |A| =n}. Then d(n) = (n - 1)ィイD12ィエD1.We have dealt with corresponding problems for the class of nondeterministic directable automata.The above research has been done mainly with B. Irma. Moreover, during the research term, the research related so shuffle operations on posets and languages has been done with M.Katsura and Z.Esik. The research related to the set of all primitive words has been also done with M.Katsura and P.Domosi. Less

一个确定性自动机A =（A，X）被称为是有向的，如果存在一个字μ∈ X D1* D1，使得|Au金属氧化物D1| = 1.在这种情况下，定向性的概念可以被唯一地定义。另一方面，不确定自动机的可定向性可以用几种不同的方法来定义。我们提供了以下三个可定向性的概念。在X上的一个词u ∈ X D1* D1被称为：（1）一个D1 -定向自动机A的D1 -定向字，如果（c ∈ A）（a ∈A）（Au n = D1 A n = D1 ={c}），（2）一个D2有向自动机A的D2有向字，如果（n a，B∈ A）（Au金属D1 A金属D1 =金属D1 A金属D1），（3）D3 -有向自动机A的D3-有向字，如果（n c ∈ A）（n a∈A）（c∈ Au n n D 1 A n n D 1），用D n n n D 2 i n n D 2（A）表示A的所有有向字的集合。注意，上述三个概念对于确定性自动机是等价的，即D D21 D2（A）= D D23 D2（A）。在这种情况下，我们将这些语言表示为D（A），我们定义了以下几类语言：|A：确定 ...更多信息有向自动机}，则D2 ={Di（A）|A：一个非确定的Di-有向自动机} Di（i）Di（A）|答：一个完全的非确定的双向自动机}（I= 1，2，3），则上述每一类语言都成为正则语言的一个子类，更确切地说，这些类在包含关系下构成一个下格。本文用D_（2D）D_（2nd）D_（2nd）D_（2nd），D_（2nd）C_（2nd）D_（2nd），D_（2nd）C_（2nd）C_（2nd）D_（2nd）表示相应的交换语言类，则这些类构成一个线性序集。对于确定有向自动机类A =（A，X），|一|= n，下面的切尔尼猜想是众所周知的：设A =（A，X）是一个确定的有向自动机，|一|通过P（A），我们表示数min {|u|||Au金属氧化物D1| = 1}。设d（n）= max{p（A）|A：一个确定性的有向自动机，|一|=n}。则d（n）=（n - 1）D 12 D 1.本文主要研究了非确定有向自动机类的相应问题，以上研究主要是以B为例进行的.厄玛此外，在本研究期间，M. Kattero和Z. Esik对偏序集和语言上的so shuffle操作进行了研究。与所有原始词的集合相关的研究也已经由M. Kateland和P. Domosi完成。少