A generalization of finiteness |
| |
Authors: | J. A. Brzozowski |
| |
Affiliation: | (1) Department of Computer Science, University of Waterloo, N2L 3G1 Ontario, Waterloo, Canada |
| |
Abstract: | ![]() We explore an analogy between the family 1, of finite/cofinite languages and the family 1 of languages whose syntactic monoids are J-trivial. It is shown that (a) J-trivial monoids, (b)L-trivial monoids, (c) R-trivial monoids, and (d) a recently studied family, that we callK, of aperiodic monoids are natural generalization of the families of syntactic semigroups of (a) finite/cofinite languages, (b) definite languages, (c) reverse definite languages, and (d) generalized definite languages, respectively. In the case of alphabets of one and two letters, the languages corresponding to the familyK of monoids are characterized, illustrating the above-mentioned analogy explicitly.This work was done partly at the University of Paris VI and VII under the scientific exchange program between Canada and France, and partly at the Institut für Rechner- und Programmstrukturen, Gesellschaft für Mathematik und Datenverarbeitung mbH. Bonn, Germany. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|