自动机状态复杂度及模型研究
|
摘要
理论计算机科学在很多不同领域有其根源:生物学家研究神经网的模型,电气工程师发展交换理论用以作为硬件设计的工具,数学家对逻辑学基础进行的研究,语言学家研究表达自然语言语法的模型,都可以看作是理论计算机科学的研究范畴。自动机理论是计算机科学的基础,其应用已渗透到计算机科学的几乎各个领域和其他的一些学科,例如交换理论、模式匹配与模式识别、语音处理、手写体识别、光学字符识别、密码算法、数据压缩、操作系统分析。
有限状态机器(包括有限状态自动机及有限状态转换机)被应用于计算机科学的许多领域,最近又出现了将有限状态机器用于计算语言学各个方面的潮流,包括字典编码、文本处理及语音处理。在有限状态自动机的应用中,非常重要的一个问题是存储空间的问题,这就是有限状态自动机状态复杂度研究所考虑的问题。实际上,有限状态自动机状态复杂度的研究早已开始,然而在上世纪九十年代以前由于没有合适的有效工具用来实现自动机的操作,因此在这一领域的研究结果其少。但是自从近二十年来,出现了一些用来操作自动机的计算机辅助软件,使得可以用计算机来完成自动机上的操作,这大大推动了对自动机状态复杂度的研究。同时有限状态自动机在许多不同领域有着越来越多的新应用而且在这些新应用中自动机的尺寸通常都非常大,在这种情况下自动机状态复杂度的研究既有着非常重要的理论意义也有着显著的实用价值。另一方面,由于传统计算模型在某些方面的限制不足以描述指定的问题,有必要引入新的计算模型或者研究现有模型的新特性,一个很好的例子是上下文无关文法和语言就不可能表达自然语言中的所有现象,因此本文也试图引入一种新的自动机模型及研究现有工具的语言计算能力。
本文研究了形式语言与自动机理论中的几个基本问题。对有限自动机上几个复合操作的状态复杂度进行了研究;通过定义从一个代数结构到完全分配型网格的模糊函数的方法引入了模糊树自动机模型。
本文的主要贡献在于研究了以下几个方面的问题:
1.研究了有限状态自动机上一些基本操作与逆转进行复合运算的状态复杂度,在现有操作自动机的辅助软件grail+的基础上用构造性的方法证明了这些复合操作的状态复杂度,证明了这些操作状态复杂度上界的同时还给出了极坏情况下的实例,这对于大尺寸自动机的成功应用具有非常重要的意义。
2.证明了有限状态自动机上星操作和一些基本操作进行复合运算的状态复杂度上界,然而目前为止还未能得到这些复合操作能达到这些上界的极坏情况实例,这有待于在今后的工作中进一步进行研究。
3.在回顾现有自动机理论的基础上,引入了模糊树自动机的模型。通过定义从一个任意∑代数到一个完全分配型网格的映射的方法定义了模糊函数(即模糊集)的代数,在模糊函数的代数中定义了布尔操作,从而使得模糊集函数的代数也具有网格的结构。同时,还定义了有理模糊集,证明了一个模糊集为等式模糊集当且仅当其为有理模糊集。通过将树自动机的转移函数模糊化定义了模糊树自动机模型,给出了克林定理关于模糊可识别集的表达形式。
在本文的最后给出了今后研究工作的方向和重点。
Theoretical computer science had its beginnings in a number of diverse fields: biologists studying models for neuron nets, electrical engineers developing switching theory as a tool to hardware design, mathematicians working on the foundations of logic, and linguists investigating grammars for natural languages. Automata theory is the foundation of computer science. Its applications have spread to almost all areas of computer science and many other disciplines, such as switching theory, pattern recognition, speech processing, hand writing recognition, optical character recognition, encryption algorithm, data compression, indexing and operation system analysis(Petri-net).
Finite-state devices, which include finite-state automata and finite-state transducers, are in wide use in many areas of computer science. Recently, there has been a resurgence of the use of finite-state devices in all aspects of computational linguistics, including dictionary encoding, text processing, and speech processing.
In the applications of finite automata, it is very necessary to know the storing space of automata. This is the issue of state complexity research. In fact, the state complexity research started very early, however before 1990's there were not so many research results in this area since there were no efficient tools for automata implementation. Since the last two decades, some computer software for implementing automata came into being. It fosters state complexity research. Meanwhile, finite automata have more and more new applications in different areas and usually the sizes of automata in new applications are large. State complexity research has big significance from both theoretical point of view and practical point of view. On the other hand, new models of computation should be introduced due to some purpose such as the traditional models are not so powerful in some aspects. There is a good example that context-free grammars and languages are not enough to express all the phenomenon in natural language. Thus we try to induce new automata models and examine the computational power of existing tools in this dissertation.
In this dissertation, we intend to investigate several basic problems in formal language and automata theory. The state complexities of some combined operations are obtained. We introduce the fuzzy tree automata system by giving the fuzzy function from an algebra to a completely distributive lattice.
The main achievements of this dissertation are as follows:
1. State complexities of some combined operations, some basic operations combined with reversal, are investigated. We obtain the state complexities of these combined operations by constructive method based on automata implementation software grail+. Both the upper bounds and worst-case examples are given. It has great significance to the application of large size automata.
2. Upper bounds of the number of states for the minimal automata for star combined with some basic operations are obtained. However, we haven't figured out worst-case examples for these cases. This means that whether these upper bounds are tight, there is no answer so far.
3. Based on the surveying of automata theory including finite automata, tree automata and weighted automata, we define algebra of fuzzy functions by mapping arbitraryΣ-algebras to completely distributive lattices. Also, we define rational fuzzy sets. We prove that a fuzzy set is equational if and only if it is rational. Given fuzzy transitions to a tree automaton, we obtain the definition of fuzzy tree automata. The representation of Kleene's theorem for fuzzy recognizable set is obtained.
The outline of future work is presented at the end of this dissertation.
有限状态机器(包括有限状态自动机及有限状态转换机)被应用于计算机科学的许多领域,最近又出现了将有限状态机器用于计算语言学各个方面的潮流,包括字典编码、文本处理及语音处理。在有限状态自动机的应用中,非常重要的一个问题是存储空间的问题,这就是有限状态自动机状态复杂度研究所考虑的问题。实际上,有限状态自动机状态复杂度的研究早已开始,然而在上世纪九十年代以前由于没有合适的有效工具用来实现自动机的操作,因此在这一领域的研究结果其少。但是自从近二十年来,出现了一些用来操作自动机的计算机辅助软件,使得可以用计算机来完成自动机上的操作,这大大推动了对自动机状态复杂度的研究。同时有限状态自动机在许多不同领域有着越来越多的新应用而且在这些新应用中自动机的尺寸通常都非常大,在这种情况下自动机状态复杂度的研究既有着非常重要的理论意义也有着显著的实用价值。另一方面,由于传统计算模型在某些方面的限制不足以描述指定的问题,有必要引入新的计算模型或者研究现有模型的新特性,一个很好的例子是上下文无关文法和语言就不可能表达自然语言中的所有现象,因此本文也试图引入一种新的自动机模型及研究现有工具的语言计算能力。
本文研究了形式语言与自动机理论中的几个基本问题。对有限自动机上几个复合操作的状态复杂度进行了研究;通过定义从一个代数结构到完全分配型网格的模糊函数的方法引入了模糊树自动机模型。
本文的主要贡献在于研究了以下几个方面的问题:
1.研究了有限状态自动机上一些基本操作与逆转进行复合运算的状态复杂度,在现有操作自动机的辅助软件grail+的基础上用构造性的方法证明了这些复合操作的状态复杂度,证明了这些操作状态复杂度上界的同时还给出了极坏情况下的实例,这对于大尺寸自动机的成功应用具有非常重要的意义。
2.证明了有限状态自动机上星操作和一些基本操作进行复合运算的状态复杂度上界,然而目前为止还未能得到这些复合操作能达到这些上界的极坏情况实例,这有待于在今后的工作中进一步进行研究。
3.在回顾现有自动机理论的基础上,引入了模糊树自动机的模型。通过定义从一个任意∑代数到一个完全分配型网格的映射的方法定义了模糊函数(即模糊集)的代数,在模糊函数的代数中定义了布尔操作,从而使得模糊集函数的代数也具有网格的结构。同时,还定义了有理模糊集,证明了一个模糊集为等式模糊集当且仅当其为有理模糊集。通过将树自动机的转移函数模糊化定义了模糊树自动机模型,给出了克林定理关于模糊可识别集的表达形式。
在本文的最后给出了今后研究工作的方向和重点。
Theoretical computer science had its beginnings in a number of diverse fields: biologists studying models for neuron nets, electrical engineers developing switching theory as a tool to hardware design, mathematicians working on the foundations of logic, and linguists investigating grammars for natural languages. Automata theory is the foundation of computer science. Its applications have spread to almost all areas of computer science and many other disciplines, such as switching theory, pattern recognition, speech processing, hand writing recognition, optical character recognition, encryption algorithm, data compression, indexing and operation system analysis(Petri-net).
Finite-state devices, which include finite-state automata and finite-state transducers, are in wide use in many areas of computer science. Recently, there has been a resurgence of the use of finite-state devices in all aspects of computational linguistics, including dictionary encoding, text processing, and speech processing.
In the applications of finite automata, it is very necessary to know the storing space of automata. This is the issue of state complexity research. In fact, the state complexity research started very early, however before 1990's there were not so many research results in this area since there were no efficient tools for automata implementation. Since the last two decades, some computer software for implementing automata came into being. It fosters state complexity research. Meanwhile, finite automata have more and more new applications in different areas and usually the sizes of automata in new applications are large. State complexity research has big significance from both theoretical point of view and practical point of view. On the other hand, new models of computation should be introduced due to some purpose such as the traditional models are not so powerful in some aspects. There is a good example that context-free grammars and languages are not enough to express all the phenomenon in natural language. Thus we try to induce new automata models and examine the computational power of existing tools in this dissertation.
In this dissertation, we intend to investigate several basic problems in formal language and automata theory. The state complexities of some combined operations are obtained. We introduce the fuzzy tree automata system by giving the fuzzy function from an algebra to a completely distributive lattice.
The main achievements of this dissertation are as follows:
1. State complexities of some combined operations, some basic operations combined with reversal, are investigated. We obtain the state complexities of these combined operations by constructive method based on automata implementation software grail+. Both the upper bounds and worst-case examples are given. It has great significance to the application of large size automata.
2. Upper bounds of the number of states for the minimal automata for star combined with some basic operations are obtained. However, we haven't figured out worst-case examples for these cases. This means that whether these upper bounds are tight, there is no answer so far.
3. Based on the surveying of automata theory including finite automata, tree automata and weighted automata, we define algebra of fuzzy functions by mapping arbitraryΣ-algebras to completely distributive lattices. Also, we define rational fuzzy sets. We prove that a fuzzy set is equational if and only if it is rational. Given fuzzy transitions to a tree automaton, we obtain the definition of fuzzy tree automata. The representation of Kleene's theorem for fuzzy recognizable set is obtained.
The outline of future work is presented at the end of this dissertation.
引文
[1]Culik Ⅱ Karel,Kari Jarkko.Digital images and formal languages.In:G.Rozenberg and A.Salomaa.Handbook of Formal Languages,Berlin:Springer,1997.599-616
[2]Karttunen Lauri.Finite-State transducers in natural language processing.Lecture Notes in Computer Science,Springer,2001,2088:34-46
[3]Mohri Mehryar.Finite-State Transducers in Language and Speech Processing.Computational Linguistics,1997,23:269-311
[4]Roche Emmanuel,Schabes Yves.Introduction to Finite-State Devices in Natural Language Processing.Technical Report,MIT Press,1996
[5]Rozenberg Grzegorz,Salomaa Arto(Eds.).Handbook of Formal Languages,Vol 1,2,3,Berlin:Springer-Verlag,1997
[6]Kelley Dean.Automata and Formal Languages—An Introduction,Englewood Cliffs:Prentice-Hall,1995
[7]Aho Alfred V.,Hopcroft John E.,Ullman Jeffrey D..The design and analysis of computer algorithms.Massachusetts:Addison Wesley,1974
[8]Hopcroft John E..An n log n algorithm for minimizing states in a finite automaton.In:Z.Kohavi.Theory of Machines and Computations,New York:Academic Press,1971.189-196
[9]Leiss Ernst L..Succinct representation of regular languages by boolean automata.Theoretical Computer Science,1981,13:323-330
[10]Leiss Ernst L..Succinct representation of regular languages by boolean automata Ⅱ.Theoretical Computer Science,1985,38:133-136
[11]Mohri Mehryar.Minimization Algorithms for Sequential Transducers.Theoretical Computer Science,2000,234:177-201
[12]van de Snepscheut Jan L.A..What Computing Is All About.New York:Springer-Verlag,1993
[13]Turing Alan.Computing machinery and intelligence.Mind 1950,59:433-460
[14]Colin P.Williams and Scott H.Clearwater.Ultimate Zero and One,Springer-Verlag,New York,2000
[15]Cohen Daniel I.A..Introduction to Computer Theory.New York:Wiley,1991
[16]Garey Michael R.,Johnson David S..Computers and Intractability:A Guide to the Thoery of NP-completeness.New York:W.H.Freeman and Company,1979
[17]Ginsburg Seymour.Algebraic and automata-theoretic properties offormal languages.Amsterdam:North-Holland,1975
[18]Kuich Werner,Salomaa Arto.Semirings,Automata,Languages.Berlin:Springer-Verlag,1986
[19]Mehryar Mohri,Fernando Pereira,Michael Riley.Weighted finite-state transducers in speech recognition.Computer Speech & Language,2002,16:69-88
[20]Dassow J(u|¨)rgen,Mitrana Victor.Finite automata over free generated groups.Intern.Journal of Algebra and Computation,2000,10(6):725-737
[21]Ito Masami,Martin-Vide Carlos,Mitrana Victor.Group weighted finite transducers.Acta Inf.,2001,38(2):117-129
[22]Mitrana Victor,Stiebe Ralf.Extended finite automata over groups,Discrete Appl.Math.,2001,108(3):247-260.
[23]Mateescu Alexandru,Salomaa Arto,Yu Sheng.Lexical analysis with a simple finite fuzzy automata model.Journal of Universal Computing,1995,1(5):292-311
[24]Rabin Michael,Scott Davis.Finite automata and their decision problems.IBM J.Res.Dev,1959,3:114-125
[25]Martin-Vide Carlos,Mitrana Victor,Paun Gheorghe(eds.).Formal Languages and Applications.Berlin:Springer-Verlag,2004
[26]Zadeh Lotfi A..Fuzzy sets.Inform,and Control,1965,8:338-353
[27]Mordeson John N.,Malik Davender S..Fuzzy Automata and Languages.Boca Raton:Chapman &Hall/CRC,2002
[28]Konstantinidis Stavros,Santean Nicolae,Yu Sheng.Fuzzification of Rational and Recognizable Sets.(Technical report,Western Ontario),April,2005.
[29]Harrison Michael A..Introduction to Formal Language Theory.Philippines:Addison-Wesley Publishing Company,1978
[30]Hopcroft John E.,Ullman Jeffrey D..Introduction to Automata Theory,Languages,and Computation.Massachusetts:Addison-Wesley Publishing Company,1979
[31]Salomaa Arto.Formal Languages.New York:Academic Press,1973
[32]Davey Brian A.,Priestley Hilary A..Introduction to Lattices and Order.Cambridge:Cambridge University Press,1990
[33]Howie John M..Automata and Languages.Oxford:Oxford University Press,1991
[34]Salomaa Arto.Jewels of Formal Language Theory.Rockville,Maryland:Computer Science Press,1981
[35]Salomaa Arto.Computation and Automata.Canlbridge:Cambridge University Press,1985
[36]Aho Alfred V.,Ullman Jeffrey D..The Theory of Parsing,Translation,and Compiling(Vol.1).Englewood Cliffs:Prentice-Hall,1972
[37]Brzozowski John A.,Seger Carl J.H..Asynchronous Circuits.New York:Springer-Verlog,1995
[38]Brzozowski John A.,Simon hnre.Characterization of locally- testable events.Discrete Mathematics,1973,4:243-271
[39]Knuth Donald E.,Morris James M.,Pratt Vaughan R..Fast pattern matching in strings.STAM Journal on Computing,1997,6(2):323-350
[40]Dickert Volker,Rozenberg Grzegorz(eds.).The Book of Traces.Singapore:World Scientific,1995
[41]Guo Li,Salomaa Kai,Yu Sheng.Synchronization Expressions and Languages.Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing,1994:257-264
[42]Culik Ⅱ Karel,Dube Simant.Rational and Affine Expressions for Image Description.Discrete Applied Mathematics,1993,41:85-120
[43]Culik Ⅱ Karel,Dube Simant.Affine Automata and Related Techniques for Generation of Complex Images.Theoretical Computer Science,1993,116:373-398
[44]Culik Ⅱ Karel,Karl Jarkko.Image Compression Using Weighted Finite Automata.Computer and Graphics,1993,17(3):305-313
[45]Culik Ⅱ Karel,Harju Tero.Splicing Semigroups of Dominoes and DNA.Discrete Applied Mathematics,1991,31:261-277
[46]Head Tom.Formal Language Theory and DNA:An analysis of the generative capacity of specific recombinant behaviors.Bull.Math.Biol,1987,49(6):737-759
[47]Linz Peter.An Introduction to Formal Languages and Automata(3~(rd) ed.).Massachusetts:Jones and Bartlett Publishers,2001
[48]Br(u|¨)ggemann-Klein Anne.Regular expressions into finite automata.Theoretical Computer Science,1993,120:197-213
[49]Brzozowski John A..Developments in the theory of regular languages.Information Processing 80.In:S.H.Lavington.Proceedings of IFIP Congress 80,Holland:North-Holland,1980.29-40
[50]Brzozowski John A..Open problems about regular languages,Formal Language Theory—Perspectives and open problems.In:R.V.Book.New York:Academic Press,1980.23-47
[51]Chang Chia-H.,Paige Robert.From Regular Expressions to DFA's Using Compressed NFA's.Proceedings of the Third Symposium on Combinatorial Pattern Matching,1992:90-110
[52]Yu Sheng.Finite Automata(Technical Report,Tarragona),March,2001,26-30
[53]Ehrenfeucht Andrzej,Parikh Rohit,and Rozenberg Grzegorz.Pumping Lemmas for Regular Sets.SIAM Journal on Computing,1981,10(3):536-541
[54]Berstel Jean.Transductions and Context-Free Languages.Teubner:Stuttgart,1979
[55]Choffrut Christian.Minimizing subsequential transducers:a survey.Theoretical Computer Science,2003,292:131-143
[56]Mohri Mehryar,Percira Fernando,Riley Michael.A rational design for a weighted finite-state transducer library.Lecture Notes in Computer Science,1997,1436:144-158
[57]Gecseg Ferenc,Steinby Magnus.Tree Automata.Budapest:Akademiai Kiado,1984
[58]Balcazar J.L.,Diaz J.,Gabarro J..Structured Complexity Ⅰ,Ⅱ,EATCS Monagraphs on Theoretical Computer Science,vol.11 and 22,Brauer,Rozenberg,and Salomaa(eds),Springer-Verlag,1988and 1990
[59]Iwama Kazuo,Kambayashi Yahiko,Takaki Kazuya.Tight bounds on the number of states of DFAs that arc equivalent to n-state NFAs.Theoretical Computer Science,2000,237:485-494
[60]Jiang Tao,Ravikumar Bala.A note on the space complexity of some decision problems for finite antomata.Information Processing Letters,1991,40:25-31
[61]Jiang Tao,Ravikumar Bala,Minimal NFA Problems are Hard.SIAM Journal on Computing,1993,22:1117-1141
[62]Yu Sheng,Zhuang Qingyu,Salomaa Kai.The state complexities of some basic operations on regular languages.Theoretical Computer Science,1994,125:315-328
[63]Campeanu Cezar,Culik Karel,Salomaa Kai et al.State Complexity of Basic Operations on Finite Languages.Proceedngs of the Fourth International Workshop on Implementing Automata Ⅷ 1-11,LNCS 1999,2214:60-70
[64]Campeanu Cezar,Salomaa Kai,Yu Sheng.Tight lower bound for the state complexity of shuffle of regular languages.Journal of Automata,Languages and Combinatorics,2002,7(3):303-310
[65]Campeanu Cezar,Salomaa Kai,Yu Sheng.State Complexity of Regular Languages:Finite Versus Infinite(Chapter 5).In:Calude Christian,Paun Gheorghe.Finite vs Infinite-Contributions to an Eternal Dilemma.Berlin:Springer,2000.53-73
[66]Pighizzini Giovanni,Shallit Jeffrey.Unary language operations,state complexly- and Jacobsthal's function.International Journal of Foundations of Computer Science,2002,13(1):145-159
[67]Holzer Markus,Kutrib Martin.State complexity of basic operations on nondctcrministic finite antomata.Proceedings of International Conference on Implementation and Application of Automata 2002(CIAA 2002),Berlin:Springer LNCS 2608:148-157
[68]Birget Jean C..Partial orders on words,minimal elements of regular languages,and state complexity.Theoretical Computer Science 1993,119:267-291
[69]Holzer Markus,Kutrib Martin.Unary language operations and their nondeterministic state complexity.Developments in Language Theory(DLT 2002),Berlin:Springer LNCS 2450:162-172
[70]Holzer Markus,Salomaa Kai,Yu Sheng.On the state complexity of k-entry deterministic finite automata.Journal of Automata,Languages and Combinatorics,2001,6(4):453-466
[71]Jiraskova Galina.State complexity of some operations on regular languages.Proceedings of 5th Workshop on Descriptional Complexity of Formal Systems,2003:114-125
[72]Jiraskova Galina.State complexity' of some operations on binary rcgular languages.Theoretical Computer Science,to appear.
[73]Jirasek Jozef,Jiraskova Galina,Szabari Alexander.State Complexity of Concatenation and Complementation of Regular Languages.International Journal of Foundations of Computer Science,2005,16:511-529
[74]Jiraskova Galina,Okhotin Alexander.State complexity of cyclic shift.Proceedings of DCFS 2005Italy:Como,2005.182-193
[75]Nicaud Cyril.Average State Complexity of Operations on Unary Automata.MFCS'99,LNCS,1999,1672:231-240
[76]Salomaa Arto,Wood Derick,Yu Sheng.On the state complexity of reversals of regular languages.Theoretical Computer Science 2004,320:293-313
[77]Gao Yuan,Salomaa Kai,Yu Shcng.State complexity of catenation and reversal combined with star.DCFS 2006:153-164
[78]Salomaa Kai,Salomaa Arto,Yu Sheng.State complexity of combined operations.Throretical Computer Science,to appear.
[79]Sheng Yu.Regular languages.In:Rozenberg Grzegorz,Salomaa Arto.Handbook of Formal Languages.Berlin:Springer,1997.41-110
[80]Yu Sheng.State Complexity:recent results and open problems,Fundamenta Informaticae 2005,64(1-4):471-481
[81]Leiss Ernst.Language equations over a one-letter alphabet with union,concatenation and star:a complete solution.Theoretical Computer Science,1994,131:311-330
[82]Salomaa Kai,Yu Sheng.NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets.Journal of Automata,Languages and Combinatorics,1997,2(3):177-186
[83]Domaratzki Michael.State complexity and proportional removals.Journal of Automata,Languages and Combinatorics,2002,7:455-468
[84]Eilenberg Samuel.Automata,Languages,and Machines,Vol.A.New York:Academic Press,1974
[85]Kleene Stephen C..Representation of events in negate nets and finite automata.In:Automata Studies,Washington:Princeton University Press,1956:3-42
[86]B(u|¨)chi Richard.On a decision method of restricted second-order arithmetic.In:Prec.1960 Int.Congress for Logic,Stanford University Press,1962:1-12
[87]Perrin Dominique,Pin Jean E..Infinite Words,Pure and Applied Mathematics Vol 141,Elsevier,2004.
[88]Berstel Jean,Reutenauer Christophe.Rational Series and their Languages,EATCS Monographs on Theoretical Computer Science.Berlin:Springer-Verlag,1988
[89]Sch(u|¨)tzenberger Marcel P..On the definition of a family of automata.Information and Control,1961,4:245-270
[90]Kuich Werner,Rahonis George.Fuzzy regular languages over finite and infinite words.Fuzzy Sets and Systems,to appear
[91]Bozapalidis Symeon.Effective construction of the syntactic algebra of a recognizable series on trees.Acta Inform.,1991,28:351-363
[92]Batten Jos C.M.,Weijland Peter.Process Algebra.Cambridge:Cambridge University Press,1990.
[93]Bekic Hans.Definable operations in general algebras,and the theory of automata and flowcharts.Tech.Report IBM Vienna,1967.Also available in:Lecture Notes in Computer Science,1994,177:30-55
[94]Gr(a|¨)tzer George.Universal Algebra.Berlin:Springer-Verlag,1979
[95]Esik Zoltan,Weil Pascal.Algebraic recognizability of regular tree languages.Theoretical Computer Science,2005,340:291-321
[96]Cohn Paul M..Universal Algebra(2nd ed),Mathematics and its Applications.Mass.:Reidel Publishing Co.,Dordrecht-Boston,1981
[97]Niwinski Damian.Equational μ-calculus.In:Computation theory(Zaborow,1984),LNCS 208,Springer,1985.169-176
[98]Niwinski Damian.On fixed-point clones(extended abstract).In:Automata,Languages and Programming,LNCS 226,Springer,1986.464-473
[99]Bloom Stephen L.,Esik Zoltan.Iteration Theories.Berlin:Springer,1993
[100]Bozapalidis Symeon.Equational elements in additive algebras.Theory Comput.Syst.,1999,32:1-33
[101]Mezei Janos Z.,Wright Jesse B..Algebraic automata and context-free sets.Injormation and Control,1967,11:3-29
[102]Berstel Jean,Reutenaner Christophe.Recognizable formal power series on trees.Theoret.Comput.Sci.,1982,18:115-148
[103]Esik Zoltan,Kuich Werner.Formal tree series,In:Weighted automata:theory and applications (Dresden,2002).J.Autom.Lang Comb.,2003,8(2):219-285
[104]Inagaki Yasuyoshi,Fukumura Teruo.On the description of fuzzy meaning of context-free language.In:Fuzzy sets and their applications to cognitive and decision processes(Proc.U.S.-Japan Serm.,Univ.Calif.,Berkeley,Calif.,1974),New York:Academic Press,1975.301-328
[105]Bloom Stephen L.,Esik Zoltan.An extension theorem with an application to formal tree series.Weighted automata:theory and applications(Dresden,2002).J.Autom.Lang Comb.,2003,8(2):145-185
[2]Karttunen Lauri.Finite-State transducers in natural language processing.Lecture Notes in Computer Science,Springer,2001,2088:34-46
[3]Mohri Mehryar.Finite-State Transducers in Language and Speech Processing.Computational Linguistics,1997,23:269-311
[4]Roche Emmanuel,Schabes Yves.Introduction to Finite-State Devices in Natural Language Processing.Technical Report,MIT Press,1996
[5]Rozenberg Grzegorz,Salomaa Arto(Eds.).Handbook of Formal Languages,Vol 1,2,3,Berlin:Springer-Verlag,1997
[6]Kelley Dean.Automata and Formal Languages—An Introduction,Englewood Cliffs:Prentice-Hall,1995
[7]Aho Alfred V.,Hopcroft John E.,Ullman Jeffrey D..The design and analysis of computer algorithms.Massachusetts:Addison Wesley,1974
[8]Hopcroft John E..An n log n algorithm for minimizing states in a finite automaton.In:Z.Kohavi.Theory of Machines and Computations,New York:Academic Press,1971.189-196
[9]Leiss Ernst L..Succinct representation of regular languages by boolean automata.Theoretical Computer Science,1981,13:323-330
[10]Leiss Ernst L..Succinct representation of regular languages by boolean automata Ⅱ.Theoretical Computer Science,1985,38:133-136
[11]Mohri Mehryar.Minimization Algorithms for Sequential Transducers.Theoretical Computer Science,2000,234:177-201
[12]van de Snepscheut Jan L.A..What Computing Is All About.New York:Springer-Verlag,1993
[13]Turing Alan.Computing machinery and intelligence.Mind 1950,59:433-460
[14]Colin P.Williams and Scott H.Clearwater.Ultimate Zero and One,Springer-Verlag,New York,2000
[15]Cohen Daniel I.A..Introduction to Computer Theory.New York:Wiley,1991
[16]Garey Michael R.,Johnson David S..Computers and Intractability:A Guide to the Thoery of NP-completeness.New York:W.H.Freeman and Company,1979
[17]Ginsburg Seymour.Algebraic and automata-theoretic properties offormal languages.Amsterdam:North-Holland,1975
[18]Kuich Werner,Salomaa Arto.Semirings,Automata,Languages.Berlin:Springer-Verlag,1986
[19]Mehryar Mohri,Fernando Pereira,Michael Riley.Weighted finite-state transducers in speech recognition.Computer Speech & Language,2002,16:69-88
[20]Dassow J(u|¨)rgen,Mitrana Victor.Finite automata over free generated groups.Intern.Journal of Algebra and Computation,2000,10(6):725-737
[21]Ito Masami,Martin-Vide Carlos,Mitrana Victor.Group weighted finite transducers.Acta Inf.,2001,38(2):117-129
[22]Mitrana Victor,Stiebe Ralf.Extended finite automata over groups,Discrete Appl.Math.,2001,108(3):247-260.
[23]Mateescu Alexandru,Salomaa Arto,Yu Sheng.Lexical analysis with a simple finite fuzzy automata model.Journal of Universal Computing,1995,1(5):292-311
[24]Rabin Michael,Scott Davis.Finite automata and their decision problems.IBM J.Res.Dev,1959,3:114-125
[25]Martin-Vide Carlos,Mitrana Victor,Paun Gheorghe(eds.).Formal Languages and Applications.Berlin:Springer-Verlag,2004
[26]Zadeh Lotfi A..Fuzzy sets.Inform,and Control,1965,8:338-353
[27]Mordeson John N.,Malik Davender S..Fuzzy Automata and Languages.Boca Raton:Chapman &Hall/CRC,2002
[28]Konstantinidis Stavros,Santean Nicolae,Yu Sheng.Fuzzification of Rational and Recognizable Sets.(Technical report,Western Ontario),April,2005.
[29]Harrison Michael A..Introduction to Formal Language Theory.Philippines:Addison-Wesley Publishing Company,1978
[30]Hopcroft John E.,Ullman Jeffrey D..Introduction to Automata Theory,Languages,and Computation.Massachusetts:Addison-Wesley Publishing Company,1979
[31]Salomaa Arto.Formal Languages.New York:Academic Press,1973
[32]Davey Brian A.,Priestley Hilary A..Introduction to Lattices and Order.Cambridge:Cambridge University Press,1990
[33]Howie John M..Automata and Languages.Oxford:Oxford University Press,1991
[34]Salomaa Arto.Jewels of Formal Language Theory.Rockville,Maryland:Computer Science Press,1981
[35]Salomaa Arto.Computation and Automata.Canlbridge:Cambridge University Press,1985
[36]Aho Alfred V.,Ullman Jeffrey D..The Theory of Parsing,Translation,and Compiling(Vol.1).Englewood Cliffs:Prentice-Hall,1972
[37]Brzozowski John A.,Seger Carl J.H..Asynchronous Circuits.New York:Springer-Verlog,1995
[38]Brzozowski John A.,Simon hnre.Characterization of locally- testable events.Discrete Mathematics,1973,4:243-271
[39]Knuth Donald E.,Morris James M.,Pratt Vaughan R..Fast pattern matching in strings.STAM Journal on Computing,1997,6(2):323-350
[40]Dickert Volker,Rozenberg Grzegorz(eds.).The Book of Traces.Singapore:World Scientific,1995
[41]Guo Li,Salomaa Kai,Yu Sheng.Synchronization Expressions and Languages.Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing,1994:257-264
[42]Culik Ⅱ Karel,Dube Simant.Rational and Affine Expressions for Image Description.Discrete Applied Mathematics,1993,41:85-120
[43]Culik Ⅱ Karel,Dube Simant.Affine Automata and Related Techniques for Generation of Complex Images.Theoretical Computer Science,1993,116:373-398
[44]Culik Ⅱ Karel,Karl Jarkko.Image Compression Using Weighted Finite Automata.Computer and Graphics,1993,17(3):305-313
[45]Culik Ⅱ Karel,Harju Tero.Splicing Semigroups of Dominoes and DNA.Discrete Applied Mathematics,1991,31:261-277
[46]Head Tom.Formal Language Theory and DNA:An analysis of the generative capacity of specific recombinant behaviors.Bull.Math.Biol,1987,49(6):737-759
[47]Linz Peter.An Introduction to Formal Languages and Automata(3~(rd) ed.).Massachusetts:Jones and Bartlett Publishers,2001
[48]Br(u|¨)ggemann-Klein Anne.Regular expressions into finite automata.Theoretical Computer Science,1993,120:197-213
[49]Brzozowski John A..Developments in the theory of regular languages.Information Processing 80.In:S.H.Lavington.Proceedings of IFIP Congress 80,Holland:North-Holland,1980.29-40
[50]Brzozowski John A..Open problems about regular languages,Formal Language Theory—Perspectives and open problems.In:R.V.Book.New York:Academic Press,1980.23-47
[51]Chang Chia-H.,Paige Robert.From Regular Expressions to DFA's Using Compressed NFA's.Proceedings of the Third Symposium on Combinatorial Pattern Matching,1992:90-110
[52]Yu Sheng.Finite Automata(Technical Report,Tarragona),March,2001,26-30
[53]Ehrenfeucht Andrzej,Parikh Rohit,and Rozenberg Grzegorz.Pumping Lemmas for Regular Sets.SIAM Journal on Computing,1981,10(3):536-541
[54]Berstel Jean.Transductions and Context-Free Languages.Teubner:Stuttgart,1979
[55]Choffrut Christian.Minimizing subsequential transducers:a survey.Theoretical Computer Science,2003,292:131-143
[56]Mohri Mehryar,Percira Fernando,Riley Michael.A rational design for a weighted finite-state transducer library.Lecture Notes in Computer Science,1997,1436:144-158
[57]Gecseg Ferenc,Steinby Magnus.Tree Automata.Budapest:Akademiai Kiado,1984
[58]Balcazar J.L.,Diaz J.,Gabarro J..Structured Complexity Ⅰ,Ⅱ,EATCS Monagraphs on Theoretical Computer Science,vol.11 and 22,Brauer,Rozenberg,and Salomaa(eds),Springer-Verlag,1988and 1990
[59]Iwama Kazuo,Kambayashi Yahiko,Takaki Kazuya.Tight bounds on the number of states of DFAs that arc equivalent to n-state NFAs.Theoretical Computer Science,2000,237:485-494
[60]Jiang Tao,Ravikumar Bala.A note on the space complexity of some decision problems for finite antomata.Information Processing Letters,1991,40:25-31
[61]Jiang Tao,Ravikumar Bala,Minimal NFA Problems are Hard.SIAM Journal on Computing,1993,22:1117-1141
[62]Yu Sheng,Zhuang Qingyu,Salomaa Kai.The state complexities of some basic operations on regular languages.Theoretical Computer Science,1994,125:315-328
[63]Campeanu Cezar,Culik Karel,Salomaa Kai et al.State Complexity of Basic Operations on Finite Languages.Proceedngs of the Fourth International Workshop on Implementing Automata Ⅷ 1-11,LNCS 1999,2214:60-70
[64]Campeanu Cezar,Salomaa Kai,Yu Sheng.Tight lower bound for the state complexity of shuffle of regular languages.Journal of Automata,Languages and Combinatorics,2002,7(3):303-310
[65]Campeanu Cezar,Salomaa Kai,Yu Sheng.State Complexity of Regular Languages:Finite Versus Infinite(Chapter 5).In:Calude Christian,Paun Gheorghe.Finite vs Infinite-Contributions to an Eternal Dilemma.Berlin:Springer,2000.53-73
[66]Pighizzini Giovanni,Shallit Jeffrey.Unary language operations,state complexly- and Jacobsthal's function.International Journal of Foundations of Computer Science,2002,13(1):145-159
[67]Holzer Markus,Kutrib Martin.State complexity of basic operations on nondctcrministic finite antomata.Proceedings of International Conference on Implementation and Application of Automata 2002(CIAA 2002),Berlin:Springer LNCS 2608:148-157
[68]Birget Jean C..Partial orders on words,minimal elements of regular languages,and state complexity.Theoretical Computer Science 1993,119:267-291
[69]Holzer Markus,Kutrib Martin.Unary language operations and their nondeterministic state complexity.Developments in Language Theory(DLT 2002),Berlin:Springer LNCS 2450:162-172
[70]Holzer Markus,Salomaa Kai,Yu Sheng.On the state complexity of k-entry deterministic finite automata.Journal of Automata,Languages and Combinatorics,2001,6(4):453-466
[71]Jiraskova Galina.State complexity of some operations on regular languages.Proceedings of 5th Workshop on Descriptional Complexity of Formal Systems,2003:114-125
[72]Jiraskova Galina.State complexity' of some operations on binary rcgular languages.Theoretical Computer Science,to appear.
[73]Jirasek Jozef,Jiraskova Galina,Szabari Alexander.State Complexity of Concatenation and Complementation of Regular Languages.International Journal of Foundations of Computer Science,2005,16:511-529
[74]Jiraskova Galina,Okhotin Alexander.State complexity of cyclic shift.Proceedings of DCFS 2005Italy:Como,2005.182-193
[75]Nicaud Cyril.Average State Complexity of Operations on Unary Automata.MFCS'99,LNCS,1999,1672:231-240
[76]Salomaa Arto,Wood Derick,Yu Sheng.On the state complexity of reversals of regular languages.Theoretical Computer Science 2004,320:293-313
[77]Gao Yuan,Salomaa Kai,Yu Shcng.State complexity of catenation and reversal combined with star.DCFS 2006:153-164
[78]Salomaa Kai,Salomaa Arto,Yu Sheng.State complexity of combined operations.Throretical Computer Science,to appear.
[79]Sheng Yu.Regular languages.In:Rozenberg Grzegorz,Salomaa Arto.Handbook of Formal Languages.Berlin:Springer,1997.41-110
[80]Yu Sheng.State Complexity:recent results and open problems,Fundamenta Informaticae 2005,64(1-4):471-481
[81]Leiss Ernst.Language equations over a one-letter alphabet with union,concatenation and star:a complete solution.Theoretical Computer Science,1994,131:311-330
[82]Salomaa Kai,Yu Sheng.NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets.Journal of Automata,Languages and Combinatorics,1997,2(3):177-186
[83]Domaratzki Michael.State complexity and proportional removals.Journal of Automata,Languages and Combinatorics,2002,7:455-468
[84]Eilenberg Samuel.Automata,Languages,and Machines,Vol.A.New York:Academic Press,1974
[85]Kleene Stephen C..Representation of events in negate nets and finite automata.In:Automata Studies,Washington:Princeton University Press,1956:3-42
[86]B(u|¨)chi Richard.On a decision method of restricted second-order arithmetic.In:Prec.1960 Int.Congress for Logic,Stanford University Press,1962:1-12
[87]Perrin Dominique,Pin Jean E..Infinite Words,Pure and Applied Mathematics Vol 141,Elsevier,2004.
[88]Berstel Jean,Reutenauer Christophe.Rational Series and their Languages,EATCS Monographs on Theoretical Computer Science.Berlin:Springer-Verlag,1988
[89]Sch(u|¨)tzenberger Marcel P..On the definition of a family of automata.Information and Control,1961,4:245-270
[90]Kuich Werner,Rahonis George.Fuzzy regular languages over finite and infinite words.Fuzzy Sets and Systems,to appear
[91]Bozapalidis Symeon.Effective construction of the syntactic algebra of a recognizable series on trees.Acta Inform.,1991,28:351-363
[92]Batten Jos C.M.,Weijland Peter.Process Algebra.Cambridge:Cambridge University Press,1990.
[93]Bekic Hans.Definable operations in general algebras,and the theory of automata and flowcharts.Tech.Report IBM Vienna,1967.Also available in:Lecture Notes in Computer Science,1994,177:30-55
[94]Gr(a|¨)tzer George.Universal Algebra.Berlin:Springer-Verlag,1979
[95]Esik Zoltan,Weil Pascal.Algebraic recognizability of regular tree languages.Theoretical Computer Science,2005,340:291-321
[96]Cohn Paul M..Universal Algebra(2nd ed),Mathematics and its Applications.Mass.:Reidel Publishing Co.,Dordrecht-Boston,1981
[97]Niwinski Damian.Equational μ-calculus.In:Computation theory(Zaborow,1984),LNCS 208,Springer,1985.169-176
[98]Niwinski Damian.On fixed-point clones(extended abstract).In:Automata,Languages and Programming,LNCS 226,Springer,1986.464-473
[99]Bloom Stephen L.,Esik Zoltan.Iteration Theories.Berlin:Springer,1993
[100]Bozapalidis Symeon.Equational elements in additive algebras.Theory Comput.Syst.,1999,32:1-33
[101]Mezei Janos Z.,Wright Jesse B..Algebraic automata and context-free sets.Injormation and Control,1967,11:3-29
[102]Berstel Jean,Reutenaner Christophe.Recognizable formal power series on trees.Theoret.Comput.Sci.,1982,18:115-148
[103]Esik Zoltan,Kuich Werner.Formal tree series,In:Weighted automata:theory and applications (Dresden,2002).J.Autom.Lang Comb.,2003,8(2):219-285
[104]Inagaki Yasuyoshi,Fukumura Teruo.On the description of fuzzy meaning of context-free language.In:Fuzzy sets and their applications to cognitive and decision processes(Proc.U.S.-Japan Serm.,Univ.Calif.,Berkeley,Calif.,1974),New York:Academic Press,1975.301-328
[105]Bloom Stephen L.,Esik Zoltan.An extension theorem with an application to formal tree series.Weighted automata:theory and applications(Dresden,2002).J.Autom.Lang Comb.,2003,8(2):145-185