A Morphic Palindrome Grammar and its Program

Programming Aspects: 

A grammar for asymmetric palindromes

This note gives the first grammar for asymmetric palindromes as they had been introduced in previous papers.

Why are 'asymmetric' palindromes of importance?

Every body knows the famous palindromes in phonetic writing systems.

The simplest western example is the name "anna". It reads forwards and backwards the same and it has for both ways of reading the same meaning.

There are competitions about the longest palindrome, and there are even novels written as a palindrome.

But again, their meaning is invariant of the reading direction.

Therefore they are sometimes called symmetric palindromes. But in fact, all palindromes are symmetric.

Now, what is an example for an asymmetric palindrome?

I don't know a single asymmetric palindrome in a linguistic version of what ever length and elaboration.

Chinese example

 
      友朋小吃 （you meng xiaochi : a snack bar named You-Peng
 
      吃小朋友 （chi xiao pengyou  : “Eat little kids”


       http://blog.chinesehour.com/

Hence, this very small palindrome is asymmetric in its meaning, albeit its scripture is symmetric. And, again, I don't know of a single Western example of this kind of palindromes.

Now, I introduced the concept of asymmetric palindrome that are neither linguistic nor numeric or pictographic.

The simple example is the name "Annabelle". Taken as a name it isn't palindromic at all. 

Funny enough, it consists of 3 palindromes: "anna", "b", "elle". But as a composition it isn't a palindrome.

Taken as a pattern of differentiations it is a palindrome. It reads forwards and backwards as the same. 

OK, it is an asymmetric palindrome which reads the same independently of the reading direction albeit it is inscribed differently.

 "Annabelle" gets a palindromic interpretation by the asymmetric morphogram [1,2,2,1,3,4,5,5,4].

ispalindrome[1,2,2,1,3,4,5,5,4];
val it = true : bool

More at:
http://memristors.memristics.com/Morphospheres/Asymmetric%20Palindromes.html
http://the-chinese-challenge.blogspot.co.uk/2012/12/morphosperes-asymmetric-palindromes.html

Towards Grammars and Programming

Programming classical palindromes is straight forwards, easy to access and realized in all programming languages.


http://rosettacode.org/wiki/Palindrome_detection

In general there are 2 approaches to consider:

1. The non-recursive and 

2. The recursive approach.

The non-recursive works with the construct “reverse”, the recursive works over the constructs “head” and “last” of a list.


For the morphogrammatic approach, the descriptive approach has to completed by
 the rules of
   
    a) reversion

    b) repetition and


    c) accretion.

Example



This case  got a presentation in previous papers.
http://memristors.memristics.com/Formal%20Aspects/Formal%20Aspects.html

The (retro-)recursive morphogrammatic approach has to deal additionally with the concept of trito-normal form, tnf, which is the operator to produce a canonical form by  “relabeling by ascending order”.

But more important for the morphogrammatic approach is the use of the variability of the head (first) and last function for lists.

This variability is ruled by the morphoRules of the grammar for morphic palindromes.

Recursive definition of morphic palindromes


Basis: [⌀] and [1] are morphic palindromes
Induction: If for [w] = [w1w2], [w] is a palindrome, so are

Rules

R1: [w] ⟶ w1[w]w2

R2: [w] ⟶ w2[w]w1

R3: [w] ⟶ w3[w]w3

R4: [w] ⟶ w3[w]w4.

Defs

w3 = add(|w1|,1)

w4 = add(|w3|,1)

Closure

No string is a morphic palindrome of ∑(w), unless it follows from this basis and the inductive rules R1 - R4.

With that, inductive proofs of properties of morphoGrammars are enabled.

Hence, [⌀]  ⟶ [1,1], [1,2]                   : R1, R4
          
           [1]  ⟶ [1,1,1], [2,1,2], [2,1,3] : R1, R3, R4
         

The example shows how to apply the rules on the base of the normed palindrome [1,2,3,4]:

Scala Program
The morphic palindrome rules are programmed by the Scala program MorphoGrammar.

This program is not yet producing the list of palindromes of arbitrary length but is functioning as a recursive palindrome tester for the lists defined by the morphoRules.

In a next step the production of the morphic palindromes will be implemented.

Results for odd and even palindromes are collected in the two following tables.

Remarks to the use of the tables
The following tables had been manually produced on the base of normed palindromes in trito-normal form, tnf, as it is used in the ML implementation.

The Scala program for the recursive production of palindromes, MorphoGrammar, is not yet accepting this approach. It is based purely, as it is defined, on non-canonized palindromes.

Hence, a morphogram [1,2,3] is not accepted as a palindrome by the MorphoGrammar program. Written as the list (1,2,3) it is not recognized as a morphogram that is written as [1,2,3].

scala> isPalindrome2(List(1,2,3))
res17: Boolean = false

With the list written in the form as it is produced, i.e. as the lists (2,1,3) or (3,1,2), the morphogram [1,2,3] is accepted by the MorphoGrammar as a palindrome.

scala> isPalindrome2(List(2,1,3))
res2: Boolean = true

Hence, the approach of the tables applies some kind of zigzagging between produced and normed palindromes. The start palindromes are normed, the produced palindromes are a mix of normed stars and not normed productions.

This approach is accepted by the ML implementation but not yet by the Scala program.

More at: 
http://memristics.com/Grammars and Programs/Grammars and Programs.pdf
(contains corrections of the tables)

Table of odd palindromes of size 1 and 3:

                                        

Table of even palindromes of size 2 and 4: