Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Languages with membership determined by single letter factors
Higgins P., Alwan S. Theoretical Computer Science680  15-24,2017.Type:Article
Date Reviewed: Mar 8 2018

This paper continues a previous one [1] by the authors, Higgins and Alwan, expanding on the notion of scan languages that require a word to be read completely before determining whether the word belongs to the language. This applies to every word, not just to some.

I was unable to obtain a copy of the first paper, but I found a 2014 slide show online [2] presenting results from both papers. Several examples given there will illustrate the basic notions for readers. Consider these languages over an alphabet with at least two letters A = {a,b, . . .}: L1 = aA*A*a, L2 = A*a, L3 = aA*, L4 = aA*bbA*a, L5 = (A2)*. These require complete reading (assuming L3 is read from the right). They are exemplars of the authors’ five whole scan properties, ordered in increasing strength: factor, prefix and suffix, weak scan, and full scan (equivalent to their strong scan property). The last is described for a language L over A as:

(∀ u,vA*)(∃ x,x′ ∈ A*)(uxvL & uxvA*\L).

For regular L, there are deeper connections with semigroups: each of the five scanning properties can be characterized in terms of Green’s relations on the minimal ideal of the finite syntactic monoid of L.

After referring to these properties appearing in [1,2], the authors introduce the letter scan property, which is the same as full scan except for the requirement that x,x′ are single letters: x,x′ ∈ A. This explains the title of the paper.

Basic properties and recursive constructions of letter scan (LS) languages are explored. Regular LS languages L are characterized by their right Brzozowski derivatives Lv-1 (vA*).

Next the alphabet is restricted to two letters, A = {a,b}. Let

An = {wA*: |w| = n} (n ≥ 0),

and let Ln = AnL for languages LA*. Define

En = {wAn: a occurs an even number of times in w}.

Then, it is proved that LA* is LS if and only if Ln ∈ {En, An\En} for all n ≥ 0. A binary sequence sL is determined by the characteristic function of the even cases for an LS L. The whole lead bit is 1 just in case the empty string belongs to L. The key result is that L is regular if and only if sL is rational (ultimately periodic as a sequence).

This is a beautifully written paper with elegance and clarity. Especially becoming are the finite automata recognizing regular LS languages on two letters visualized as adhesive tape rolls, where the roll is the periodic segments, and the unrolled piece is the initial segment, with the folded pointy end handling the empty string. There is a surprise appearance of a Moebius cylinder rather than a right cylinder of tape when the periodic piece is “balanced”: it factors as a string followed by its bit-complement.

There are a few typographical errors, but they don’t affect the rigor. Here are some relevant examples. Page 16, line 1b, should read “the subsets Ln of L″. Page 17, lines 7 and 8, should be L1,i = {ε} and “L1,i satisfies (1).” Page 18, Remark 2.2.11, line 4, should read “meet the neighbourhood.” On page 19, lines 2 and 3, think of brackets around “for some ... scan language” to give a clear scope. Page 20, line 5, should have Ln = On. Page 21, line 3, should read

((∀n ∈ ℕ0) (el+r+n = el+n) or (∀n ∈ ℕ0)(el+r+n = el+n)),

and line 1b should read “members of QL.” On page 22, case 1B, omit “identify the” at the end of that line.

On pages 18 and 19, occurrences of “undirected” and “free of loops” require contextual thinking. Most notation is explained. Some is not, but it can be understood from context or prior art.

It would help to specify, to the extent feasible, the different ways in which the six (and more) scan properties affect the “scan.”

One possible confusion is worth comment. Note the privileged a in the last results for the LS language L. Of course, it is symmetric with b, and the results privileging b are automatic. The point is that the same analysis for b occurs in L as well. This is not an omission, because sL determines the situation for even b by flipping the nth bit when n is odd. So there are no additional words of interest depending on b.

Reviewer:  Benjamin Wells Review #: CR145902 (1805-0232)
1) Higgins, P. M.; Alwan, S. Languages that require full scanning of words to determine membership. J. Autom. Lang. Comb. 18, 2(2013), 71–95.
2) Higgins, P. M.; Alwan, S. Languages that require full scanning of words to determine membership. Slide show. April 15, 2014. http://maths.manchester.ac.uk/~mkambites/events/nbsan/nbsan17_higgins.pdf.
Bookmark and Share
  Featured Reviewer  
 
Automata (F.1.1 ... )
 
 
Formal Languages (F.4.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Automata": Date
The congruence theory of closure properties of regular tree languages
Tirri S. Theoretical Computer Science 76(2-3): 261-271, 2001. Type: Article
Jun 1 1991
Distribution and synchronized automata
Petit A. Theoretical Computer Science 76(2-3): 285-308, 2001. Type: Article
Feb 1 1992
Efficient simulation of finite automata by neural nets
Alon N., Dewdney A., Ott T. Journal of the ACM 38(2): 495-514, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy