|
|||||
|
|
On the word problem for syntactic monoids of piecewise testable languages |
|
| Authors: | |
| Institution: | 1.Bolyai Institute,University of Szeged,Szeged,Hungary;2.Department of Algebra and Number Theory,E?tv?s Loránd University,Budapest,Hungary;3.Department of Mathematics and Applications,Central European University,Budapest,Hungary |
| Abstract: | Piecewise testable languages are widely studied area in the theory of automata. We analyze the algebraic properties of these languages via their syntactic monoids. In this paper a normal form is presented for 2- and 3-piecewise testable languages and a log-asymptotic estimate is given for the number of words over these monoids. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |