Regular PapersNo Access

A KLEENE THEOREM FOR BISEMIGROUP AND BINOID LANGUAGES

ZSOLT GAZDAG

Faculty of Informatics, Eötvös Loránd University, P.O.B. 120, 1518 Budapest, Hungary

Search for more papers by this author

and

ZOLTÁN L. NÉMETH

Inst. of Informatics, University of Szeged, P.O.B. 652, 6701 Szeged, Hungary

Supported by the Austrian-Hungarian Action Fund, project nr. 68öu2.

Search for more papers by this author

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

Abstract

A bisemigroup is a set with two associative operations. Subsets of free bisemigroups are called bisemigroup languages. Recognizable, regular and MSO-definable bisemigroup languages have been studied earlier, and these classes are known to be equal. In this paper we prove a Kleene theorem for bisemigroup languages, namely we show that the class of recognizable bisemigroup languages is the least class which contains the finite languages and closed under the operations of union, horizontal and vertical product, horizontal and vertical iteration, ξ-substitution and a restricted version of the the ξ-iteration. We extend our result to binoid languages, i.e., to subsets of free algebras, where the two associative operations share a common identity element.

Keywords:

References

M. Bojańczyk, Forest expressions, proc. CSL 2007, LNCS 4646 (Springer-Verlag, 2007) pp. 146–160. Google Scholar
M. Bojańczyk and I. Walukiewicz, Logic and Automata: History and Perspectives, eds. J. Flum, E. Grädel and Th. Wilke (Amsterdam University Press, 2008) pp. 107–132. Google Scholar
I. Dolinka, Disc. Appl. Math. 146, 43 (2005). Crossref, Web of Science, Google Scholar
I. Dolinka, Theoret. Comp. Sci. 372, 1 (2007). Crossref, Web of Science, Google Scholar
Z. Ésik and Z. L. Németh, J. of Autom. Lang. Comb. 9, 3 (2004). Google Scholar
K. Hashiguchi, S. Ichihara and S. Jimbo, J. Autom. Lang. Comb. 5, 219 (2000). Web of Science, Google Scholar
K. Hashiguchi, Y. Wada and S. Jimbo, Theoret. Comput. Sci. 304, 291 (2003), DOI: 10.1016/S0304-3975(03)00137-3. Crossref, Web of Science, Google Scholar
K. Hashiguchi, Y. Sakakibara and S. Jimbo, Theoret. Comput. Sci. 312, 251 (2004), DOI: 10.1016/j.tcs.2003.09.005. Crossref, Web of Science, Google Scholar
K. Lodaya and P. Weil, Kleene iteration for parallelism, proc. FST & TCS'98, LNCS 1530 (Springer-Verlag, 1998) pp. 355–366. Google Scholar
K. Lodaya and P. Weil, Theoret. Comput. Sci. 237, 347 (2000), DOI: 10.1016/S0304-3975(00)00031-1. Crossref, Web of Science, Google Scholar
K. Lodaya and P. Weil, Inform. and Comput. 171, 269 (2001), DOI: 10.1006/inco.2001.3077. Crossref, Web of Science, Google Scholar
Z. L. Németh, Acta Cybern. 16, 567 (2004). Google Scholar
Z. L. Németh, Acta Cybern. 18, 765 (2006). Google Scholar
Z. L. Németh. Higher dimensional automata. PhD Thesis, University of Szeged, 2007 , http://www.inf.u-szeged.hu/~zlnemeth/publications/publ.xml . Google Scholar
Z. L. Németh, On the regularity of binoid languages: a comparative approach, preproc: 1st Int. Conf. on Language and Automata Theory and Appl., LATA'07 pp. 449–460. Google Scholar
P. Weil, Algebraic recognizability of languages, proc. MFCS 2004, LNCS 3153 (Springer-Verlag, 2004) pp. 149–175. Google Scholar