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 = {
}
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