Languages recognized by programs over the two-element monoid (Q1118041): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q258068 |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Tero J.Harju / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 03:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Languages recognized by programs over the two-element monoid |
scientific article |
Statements
Languages recognized by programs over the two-element monoid (English)
0 references
1989
0 references
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.
0 references
finite monoid
0 references
recognizable by programs
0 references
languages in binary alphabet
0 references