In class on 27 Feb we mentioned Buchi's Theorem (proved at the link), that a language is regular iff it can be

defined by a formula in second-order monadic logic.

The proof that languages are first-order definable if and only if they are star-free regular is on the Descriptive Complexity page.

The proof that languages are regular if and only if they are recognized by finite monoids is on the Algebra page.

-- BarrinG - 2012-05-03

Copyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback