No Access

ON FREE SPECTRA OF VARIETIES OF LOCALLY THRESHOLD TESTABLE SEMIGROUPS

IGOR DOLINKA

Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia

https://doi.org/10.1142/S0218196712500555Cited by:0 (Source: Crossref)

Abstract

A semigroup S is said to be ℓ-threshold k-testable if it satisfies all identities u = v where u, v is an arbitrary pair of words over a finite alphabet Σ such that they simultaneously belong or fail to belong to any ℓ-threshold k-testable (regular) language. We give an asymptotic formula for the free spectrum of the variety of all ℓ-threshold k-testable semigroups, thereby providing an asymptotic upper bound on the size of an arbitrary finitely generated locally threshold testable semigroup. The combinatorial interpretation of this task yields an enumeration problem for particular edge labelings of de Bruijn graphs.

Keywords:

AMSC: 20M07, 08A40, 05A16, 05C20, 05C40

References

J. Bang-Jensen and G. Z. Gutin , Digraphs: Theory, Algorithms and Applications , 2nd edn. ( Springer-Verlag , New York , 2010 ) . Google Scholar
D. Beauquier and J.-E. Pin, Factors of Words, Proc. 16th EATCS Colloquium on Automata, Languages and Programming372, Lecture Notes in Computer Science (Springer-Verlag, Berlin, 1989) pp. 63–79. Google Scholar
J. A. Brzozowski and I. Simon, Discrete Math. 4, 243 (1973). Crossref, Google Scholar
S. Burris and H. P. Sankappanavar , A Course in Universal Algebra , Graduate Texts in Mathematics ( Springer-Verlag , New York , 1981 ) . Crossref, Google Scholar
N. G. de Bruijn, Nederl. Akad. Wetensch. Proc. 49, 758 (1946). Google Scholar
C. Delorme and J.-P. Tillich, Eur. J. Combin. 19, 307 (1998). Crossref, Web of Science, Google Scholar
I. Dolinka, Glasgow Math. J. 53, 623 (2011). Crossref, Web of Science, Google Scholar
I. J. Good, J. London Math. Soc. 21, 167 (1946). Web of Science, Google Scholar
G. Grätzer and A. Kisielewicz, Universal Algebra and Quasigroup Theory (Heldermann Verlag, Berlin, 1992) pp. 57–88. Google Scholar
K. Kátai-Urbán and Cs. Szabó, Glasgow Math. J. 49, 93 (2007). Crossref, Web of Science, Google Scholar
R. McNaughton and S. Papert , Counter-Free Automata ( MIT Press , Cambridge, MA , 1971 ) . Google Scholar
J.-E. Pin, Semigroups, Formal Languages and Groups, NATO Advanced Study Institute, ed. J. Fountain (Kluwer, Dordrecht, 1995) pp. 1–32. Crossref, Google Scholar
J. Ruiz, S. España and P. Garcia, Locally threshold testable languages in strict sense: Application to the inference problem, Proc. Fourth Int. Colloquiuim on Grammatical Inference1433, Lecture Notes in Computer Science (Springer-Verlag, Berlin, 1998) pp. 150–161. Google Scholar
S. W. Seif, J. Pure Appl. Algebra 212, 1162 (2008). Crossref, Web of Science, Google Scholar
A. N. Trahtman, Piecewise and local threshold testability of DFA, 13th Int. Symp. Fundamentals of Computation Theory2138, Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2001) pp. 347–358. Google Scholar
A. N. Trahtman, Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back, eds. C. Martin-Vide and V. Mitrana (Taylor & Francis, London, 2003) pp. 347–356. Crossref, Google Scholar
A. N. Trahtman, Theoret. Comput. Sci. 328, 151 (2004). Crossref, Web of Science, Google Scholar
E. Vidal, F. Casacuberta and P. Garcia, Speech Recognition and Coding (Springer-Verlag, Berlin, 1995) pp. 175–191. Google Scholar