Mikołaj Bojańczyk

**Monoids are equivalent to automata**

A language is called *-recognisable* if there is some homomorphism of -monoids

such that has finite universe, and which recognizes in the sense that membership is uniquely determined by . The following theorem shows that in the special (but not all that special) case of languages that contain only -words, this notion coincides with the notion of -regularity.

**Theorem. ***A language is -recognisable if and only if it is -regular*.

**Proof. **For define to be the finite nonempty words that are mapped by to , and define to be the -words that are mapped by to . It is easy to see that each language is a regular language of finite words, because it is recognised by a finite monoid, namely the monoid obtained from by ignoring products for infinite words. Furthermore, using the Ramsey theorem in the same way as in the previous lemma, we conclude that is equal to the -regular language

with the union ranging over elements which satisfy . Every set of -words recognised by is a finite union of languages of the form , and therefore the left-to-right implication follows by closure of -regular languages under finite union.

For the right-to-left implication, suppose that is recongised by a nondeterministic Büchi automaton with states . Define

defined as follows. The empty word gets mapped to . Infinite words are mapped to , namely an infinite word is mapped to the set of those states such that the word admits an accepting run that begins with . Finite words are mapped to in the same way as in the proof of complementation for Büchi automata. It is not difficult to see that this mapping is compositional, and therefore its image can be equipped with the structure of an -monoid which makes it into a homomorphism.

COMMENTS

Jasemin

May 1, 2019

http://autokreditnet.club/autokredit-vergleich.html

Jimbo

April 25, 2019

low income car insurance Provo UT

Tommy

April 19, 2019

http://immobilienkreditbiz.club/baufinanzierung-vergleich.html

Cindy

April 9, 2019

günstigster online-kredit

Leatrice

April 8, 2019

http://endlessgeek.com/

Nodin

April 7, 2019

http://www.kreditsofort.club/

Sagi

April 6, 2019

grøn viagra pille

Mitch

April 5, 2019

billige viagra gele

Joyce

April 5, 2019

viagra generic wiki

Gerrie

April 4, 2019

alternativ til viagra golf

Rennifer

April 4, 2019

køb viagra dansk

Kacy

April 2, 2019

prisen på viagra alkohol

Nettie

March 29, 2019

privatkredit

Arjay

March 19, 2019

affordable auto insurance New Albany IN

Boston

February 22, 2019

low income auto insurance Endicott NY

Kyanna

February 22, 2019

best auto insurance in Simi Valley CA

Andi

February 15, 2019

payless auto insurance Santa Ana CA

Lettice

January 23, 2019

günstiger kredit

Raynes

January 3, 2019

http://baufinanzierung.pw/baufinanzierungsrechner.html

Hester

January 2, 2019

http://privatkreditcom.info/

Janesa

January 1, 2019

kredit beantragen

Roberta

December 28, 2018

autokredit rechner

Hetty

December 20, 2018

auto insurance quotes Chesapeake VA

Malerie

December 15, 2018

http://www.autokreditnet.club/

Bayle

December 14, 2018

http://www.baufinanzierung.pw/

Brandi

November 30, 2018

cheap non owners insurance Waynesburg PA

Barbie

November 19, 2018

http://immobilienkreditbiz.club/baufinanzierung-rechner.html

Johannah

November 13, 2018

Shoot, so that's that one susopsep.

Cash

November 11, 2018

privatkredit-rechner

andre dovi

August 9, 2017

http://www.motogp.com

Roxanna

May 9, 2017

online fifa 15 coin generator

Cassandra

May 9, 2017

coc hack for mac

Cindy

April 23, 2017

http://www.crystallakecameraclub.org/bbozvu.html

Josie

April 23, 2017

http://www.janganstop.com/aoquavde.html

Denisha

March 22, 2017

coolstuffinc promo code

Regina

March 20, 2017

auto acceptance insurance Jesup GA

Tangela

March 16, 2017

list of car insurances in Forest Hills NY

Kailin

February 22, 2017

http://meinebestefinanzierung.info/test-kredit/test-kredit-ohne/stiftung-ware-test-kredit-ohne-forum/