|
|
|
篇目详细内容 |
|
【篇名】 |
On the computation of quotients and factors of regular languages |
|
【刊名】 |
Frontiers of Computer Science in China |
|
【刊名缩写】 |
Front. Comput. Sci. China |
|
【ISSN】 |
1673-7350 |
|
【EISSN】 |
1673-7466 |
|
【DOI】 |
10.1007/s11704-010-0154-8 |
|
【出版社】 |
Higher Education Press and Springer-Verlag Berlin
Heidelberg |
|
【出版年】 |
2010 |
|
【卷期】 |
4
卷2期 |
|
【页码】 |
173-184
页,共
12
页 |
|
【作者】 |
Mircea MARIN;
Temur KUTSIA;
|
|
【关键词】 |
regular language; language factorization; language quotient |
【摘要】 |
|
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. |
|
