Sub-regular languages explanation

[sethmachine]

Hi,

I came across a hierarchy of languages within the regular language class, but I honestly do not understand the distinction between these types of so-called sub-regular languages. Here is a picture illustrating the division between the two.

As you can see, there are divisions:

(1) the local branch

and

(2) the piecewise branch

which each include two further divisions

locally/piecewise testable and strictly local/piecewise

Does anyone know what these are (i.e. a definition of each kind of sub-regular language given)?

 

[GhostWolf]

I honestly can't understand if you are trying to use this forum as a way to get answers for your homework, or if these questions are genuine, in which case what on earth are you trying to learn...

 

[sethmachine]

Honestly I wish that were the case (implies I would be enrolled in a prestigious computer science program) but nope. I'm actually taking no classes this semester.

Also if I had a TA or professor to consult, I would go them first rather than post on this forum.

When I took theory of computation last spring, I made the mistake of selling back my textbook as I didn't think I'd really ever use it again but then again I don't think this is actually in the Sipser book.

Still looking for an explanation (e.g. something simple that I can bootstrap to understand where this sub-regular division comes from).

I suppose I am trying to learn Computational Learning Theory and Theory of Computation. There is a claim that a certain set of patterns are not only regular, but possibly sub-regular. This claim is very new (circa 2010) and is unproven. I am trying to get into the academic debate so to speak but I have no peers where I am (I've asked for help from fellow students but they are too busy or honestly can't help).

I post on this site because several people have made it known they have quite a background and professionalism in computer science, and the explanations here are always friendly and comprehensive, unlike those that I might find in various academic papers in a field with an extensive literature that I have no inkling about.