Graphomata

Graphomata Semantics and Encoding

Data Model

M = (G(V,E), R) where
    0 ∉ V
    E ⊆ V×V\{(v,v)|v∈V}
    R : {0,1,…,7} → V∪{0}
    R(0) = 0

Commands

C = {Nr}∪{Ls,t}∪{Us,t}∪{Wr}∪{Js,t}∪{Ts,t} where
    r,s,t ∈ {0,1,…,7}
    T : ℳ×C ⇀ ℳ mapping (M,c)↦M' and
    F : ℳ×C ⇀ {0,1} mapping (M,c)↦f defined according to
CommandDefined for
Result (M')
Result (f)
Nrr≠0
(G'(V',E), R') where v ∉ V∪{0} R'(r)=v R'(s)=R(s) ∀s≠r and V'=V∪{v} if ∃u∊V (R(r),u)∈E or (u,R(r))∈E or ∃s≠r R(s)=R(r) V'=V∪{v}\{R(r)} otherwise
0
Ls,tR(s),R(t)≠0
R(s)≠R(t)
(R(s),R(t))∉E
(G'(V,E'), R) where E'=E∪{(R(s),R(t))}
Us,t(R(s),R(t))∈E
(G'(V,E'), R) where E'=E\{(R(s),R(t))}
Wrr≠0
R(r)≠0
(G'(V',E), R') where R'(r)=u where (R(r),u)∈E if ∃u∊V (R(r),u)∈E R'(r)=0 otherwise and R'(s)=R(s) ∀s≠r and V'=V if ∃u∊V (R(r),u)∈E or (u,R(r))∈E or ∃s≠r R(s)=R(r) V'=V\{R(r)} otherwise
Js,ts≠0
(G'(V',E), R') where R'(s)=R(t) R'(r)=R(r) ∀r≠s and V'=V if s=t or ∃u∊V (R(s),u)∈E or (u,R(s))∈E or ∃r≠s R(r)=R(s) V'=V\{R(s)} otherwise
Ts,t
(G(V,E), R)
0 if R(s)=R(t) 1 if R(s)≠R(t)

Program

P = ((c0,c1,…,cn-1), N, N') where
    ∀i ci∈C
    N : {0,1,…,n-1} → {-1,0,1,…,n-1}
    N': {0,1,…,n-1} ⇀ {-1,0,1,…,n-1} defined over {i|∃s,t ci=Ts,t}

Program State

(M, I) where
    M = (G(V,E), R)
    I ∈ {-1,0,1,…,n-1}

* Initially, I=min(0,n-1).

Transition Function

(M, I) ↦ (M', I') where
    M' = T(M,cI)
and
    I' = N(I)   if F(M,cI)=0
    I' = N'(I)  if F(M,cI)=1

* Program halts when I=-1.

Encoding Grammar

program → sequence
sequence → unconditional sequence
         | conditional t-sequence f-sequence
         | ordinal
         | -1
unconditional → N-or-W r-register
              | L-or-U-or-J s-register t-register
conditional → T s-register t-register
N-or-W → N | W
L-or-U-or-J → L | U | J
register → a | b | … | h
ordinal → number i where 0≤i≤k-1 and k = number of commands encoded thus far

Command Encoding

c∈C is encoded with a sequence of 2-3 characters, starting with
    N  if c=Nr
    L  if c=Ls,t
    U  if c=Us,t
    W  if c=Wr
    J  if c=Js,t
    T  if c=Ts,t
and followed by one (r) or two (s then t)
    a  if r=1, s=1 or t=1
    b  if r=2, s=2 or t=2
    ⋮
    g  if r=7, s=7 or t=7
    h  if r=0, s=0 or t=0

Program Encoding

P = ((c0,c1,…,cn-1), N, N') is encoded as follows:

procedure EncodeProgram(c, N, N')
    A := []
    procedure EncodeSequence(i)
        if i=-1 then
            EncodeNumber(-1)
        else if exists A[k] such that A[k]=i then
            EncodeNumber(k)
        else
            EncodeCommand(c[i])
            k := |A| ; A[k] := i
            EncodeSequence(N(i))
            if exist s,t such that c[i]=Ts,t then EncodeSequence(N'(i))
        end if
    end procedure
    EncodeSequence(min(0,n-1))
end procedure

* Array subscripts start at 0.
* P is canonical iff after encoding, A[i]=i for 0≤i≤n-1. Every program P
  has an equivalent program PC that is canonical. Programs P and P' are
  equivalent iff PC=P'C.

Program Parsing

An encoded program can be parsed into a canonical program
P = ((c0,c1,…,cn-1), N, N') as follows:

procedure ParseProgram(Lexer, c, N, N')
    function ParseSequence()
        let k := |c|
        token := Lexer.NextToken()
        if -1≤token≤k-1 then
            return token
        else
            c[k] := ParseCommand(token)
            N(k) := ParseSequence()
            if exist s,t such that c[k]=Ts,t then N'(k) := ParseSequence()
            return k
        end if
    end function
    c := []
    ParseSequence()
end procedure

* Array subscripts start at 0.
* Lexer treats comments surrounded by square brackets […] as whitespace;
  nesting is not supported.

Example Program 1

P = ((N1,N2,L1,2,N2), N, N') where
    N(0) = 1
    N(1) = 2
    N(2) = 3
    N(3) = -1
    N'(i) is undefined  ∀i

* Encoding: Na Nb Lab Nb -1
* P is canonical.

Initial state: ((G(V,E), R), I) where
    V = ∅
    E = ∅
    R(r) = 0  ∀r
    I = 0

Terminal state: ((G'(V',E'), R'), I') where
    V' = {v1,v2,v3}
    E' = {(v1,v2)}
    R'(1) = v1
    R'(2) = v3
    R'(r) = 0  ∀r≠1,2
    I' = -1

Example Program 2 (Control Flow)

P = ((J2,1,W1,T1,0,U2,1), N, N') where
    N(0) = 1
    N(1) = 2
    N(2) = -1
    N(3) = 0
    N'(2) = 3
    N'(i) is undefined  ∀i≠2

* Encoding: Jba Wa Tah -1 Uba 0
* Indented encoding:
      Jba Wa Tah
          -1
          Uba 0
* P is canonical.

Initial state: ((G(V,E), R), I) where
    V = {v1,v2,…,vm}
    E' = {(v1,v2),(v2,v3),…,(vm-1,vm)}
    R(1) = v1
    R(r) = 0  ∀r≠1
    I = 0

Terminal state: ((G'(V',E'), R'), I') where
    V' = {vm}
    E' = ∅
    R'(2) = vm
    R'(r) = 0  ∀r≠2
    I' = -1

Example Program 3 (Nondeterminism)

P = ((W1), N, N') where
    N(0) = -1
    N'(0) is undefined

* Encoding: Wa -1
* P is canonical.

Initial state: ((G(V,E), R), I) where
    V = {v1,v2,v3}
    E' = {(v1,v2),(v1,v3)}
    R(1) = v1
    R(r) = 0  ∀r≠1
    I = 0

Terminal state: ((G'(V,E), R'), I') where
    G' = G
    Either R'(1) = v2 or R'(1) = v3
    R'(r) = 0  ∀r≠1
    I' = -1