Languages recognized by programs over the two-element monoid
type: Item
instance of: scholarly article
title: Languages recognized by programs over the two-element monoid
zbMATH Open document ID: 0668.20045
DOI: 10.1007/BF02573245
author: Gerard Lallement
published in: Semigroup Forum
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/134968
review text: A program \(P_ n\) over a finite monoid M is a sequence of instructions \(v_ 1,...,v_ m\) consisting of pairs \(v_ r=(i_ r,f_ r)\), where \(f_ r\) is a function from a finite alphabet A to M and \(i_ r\) is an integer, \(1<i_ r<n\). A program yields a mapping from \(A^ n\) to M in a natural way. A language L in \(A^*\) is recognizable by programs if for every n there is a program \(P_ n\) and a subset \(F_ n\) of M such that \(L\cap A^ n=P_ n^{-1}(F_ n)\). In the present paper the recognizability of the languages in binary alphabet are studied with respect to the two element monoid.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4093766
zbMATH Keywords: finite monoid
zbMATH Keywords: recognizable by programs
zbMATH Keywords: languages in binary alphabet
reviewed by: Tero Harju
MaRDI profile type: Publication
Recommended article: Recognisable Languages over Monads
Recommended article: Recognizable languages in concurrency monoids
Recommended article: Recognizable languages in divisibility monoids
Recommended article: Q4934333
Recommended article: A kleene theorem for recognizable languages over concurrency monoids
Recommended article: Languages and monoids with disjunctive identity
Recommended article: Monadic second-order definable text languages
Recommended article: Classes of two-dimensional languages and recognizability conditions
Recommended article: Q4831712
Recommended article: Q4001349
description: scientific article; zbMATH DE number 4093766