Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci Chin    2010, Vol. 4 Issue (2) : 173-184    https://doi.org/10.1007/s11704-010-0154-8
RESEARCH ARTICLE
On the computation of quotients and factors of regular languages
Mircea MARIN1(), Temur KUTSIA2
1. Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba 305-8573, Japan; 2. Research Institute for Symbolic Computation, Johannes Kepler University, A-4040 Linz, Austria
 Download: PDF(213 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Quotients and factors are important notions in the design of various computational procedures for regular languages and for the analysis of their logical properties. We propose a new representation of regular languages, by linear systems of language equations, which is suitable for the following computations: language reversal, left quotients and factors, right quotients and factors, and factor matrices. We present algorithms for the computation of all these notions, and indicate an application of the factor matrix to the computation of solutions of a particular language reconstruction problem. The advantage of these algorithms is that they all operate only on linear systems of language equations, while the design of the same algorithms for other representations often require translation to other representations.

Keywords regular language      language factorization      language quotient     
Corresponding Author(s): MARIN Mircea,Email:mmarin@score.cs.tsukuba.ac.jp   
Issue Date: 05 June 2010
 Cite this article:   
Temur KUTSIA,Mircea MARIN. On the computation of quotients and factors of regular languages[J]. Front Comput Sci Chin, 2010, 4(2): 173-184.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-010-0154-8
https://academic.hep.com.cn/fcs/EN/Y2010/V4/I2/173
1 Brzozowski J A. Derivatives of regular expressions. Journal of the Association for Computing Machinery , 1964, 11(4): 481–494
2 Antimirov V M. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science , 1996, 155: 291–319
doi: 10.1016/0304-3975(95)00182-4
3 Conway J H. Regular Algebra and Finite Machines. Mathematics series. Chapman and Hall , 1971
4 Suzuki T, Okui S. Product derivatives of regular expressions. ISPJ Online Transactions , 2008, 1: 53–65
doi: 10.2197/ipsjtrans.1.53
5 Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages, and Computation. Series in Computer Science . Addison-Wesley Publishing Company, Inc., 1979
6 Kozen D C. Automata and Computability. Undergraduate Texts in Computer Science. Springer-Verlag, New York, Inc., 1997
7 Berstel J. Transductions and Context-Free Languages. B.G. Teubner Stuttgart , 1979
8 Mateescu A, Salomaa A, Yu S. On the decomposition of finite languages. In: Rozenberg G, Thomas W, eds. Developments in Language Theory: Foundations, Applications, Perspectives. World Scientific , 2000, 22–31
9 Mateescu A, Salomaa A, Yu S. Factorizations of languages and commutativity conditions. Acta Cybernetica , 2002, 15(3): 339–351
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed