Module Pbword


module Pbword: sig .. end
Naive implementation of ultimately Periodic Binary Words.
Author(s): Louis Mandel, Florence Plateau


Data structures


type word = bool list 
Finite word: u ::= epsilon | 0u | 1v.

type periodic_binary_word = {
   u : word;
   v : word;
}
Ultimately Periodic Binary Words: p ::= u(v).
val one : periodic_binary_word
The ultimately periodic binary word (1).

Functions on ultimately periodic binary words


val size : 'a list -> int
Size of a finite word u: |u|.
val nbones : bool list -> int
Number of 1s a finite word u: |u|_1.
val iof : periodic_binary_word -> int -> int
Index of the jth 1 of an ultimately periodic binary word p: I_p(j).
val increase_prefix : periodic_binary_word -> int -> periodic_binary_word
Increase prefix size of n bits: u(vv') = uv(v'v) with |v| = n.
val repeat_periodic_pattern : periodic_binary_word -> int -> periodic_binary_word
Repeat periodic pattern: u(v) = u(v^k).
val rate : periodic_binary_word -> int * int
Computation of the rate of an ultimately periodic binary word: rate p = |p.v|_1 / |p.v|.
val (|><|) : periodic_binary_word -> periodic_binary_word -> bool
The synchronizability test of two ultimately periodic binary words: p_1 |><| p_2 <=> rate p1 = rate p2.
val prece : periodic_binary_word -> periodic_binary_word -> bool
The precedence test of two ultimately periodic binary words: p_1 <= p_2 <=> I_{p_1}(j) <= I_{p_2}(j), for all 1 <= j <= h with h = max (|p_1.u|_1,|p_2.u|_1) + lcm (|p_1.v|_1,|p_2.v|_1).
val (<:) : periodic_binary_word -> periodic_binary_word -> bool
The adaptability test of two ultimately periodic binary words: p_1 <: p_2.
val on : periodic_binary_word ->
periodic_binary_word -> periodic_binary_word
Computation of the on operator: u_3(v_3) = u_1(v_1) on u_2(v_2) with |u_3| = max (|u_1|, I_{p_1}(|u_2|)), |v_3| = (lcm (|v_1|_1, |v_2|) / |v_1|_1) * |v_1| and for all 1 <= i <= |u_3|, u_3[i] = (p_1 on p_2)[i] and for all 1 <= i <= |v_3|, v_3[i] = (p_1 on p_2)[|u_3| + i]

Printing functions


val fprint_bool : Format.formatter -> bool -> unit
val fprint_word : Format.formatter -> bool list -> unit
val fprint_pbw : Format.formatter -> periodic_binary_word -> unit