Copyright (C) 2004  Bryant Lee

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.


README
-------------

FDense v3.67
Written by: Bryant Lee (blee3@wam.umd.edu)
9/01/05
last modified: 1/18/06

This document describes how to use the FDense program.  For information on how to compile from source code, see COMPILE.txt.

Run FDense
-------------

The FDense program determines what words of length m, if any, do not appear in points that are jointly periodic in f and the k-shift.

To run, type:
FDense < INPUT_FILE

The easiest way to explain how the program works is to use an example.  Suppose we use the following input file:

Input1.txt
-------------
output after each
no group
out/FP_9_02_2005_
2
10; 11; [14,16]
6 
BEGIN DEFINITIONS
func1 = t(4, 0001 1101 1110 0010)
M = x[0] + x[1]
A = x[0] + x[1] * x[2]
BEGIN COMMANDS
M#A
func1

Explanation of the input
--------------------------------

Line 1: Output mode.  There are only two valid inputs for line 1, either "output after each" or "output at end".  If "output at end" is chosen, then the program does not produce output files until the runs for all values of K are complete.  If "output after each" is chosen, then the program generates output files at the end of each run for a different value of K.  This is helpful when using a long range of K values where some of the larger values may cause the program to crash (due to running out of memory), which results in no output at all in the "output at end" mode.  However, it wastes a little time because outputting after each K value is redundant.

Line 2: Group mode.  There only valid inputs for this line are "group" and "no group".  If "group" is chosen, then a special abbreviated form of the output is created.  See Output section for more details.

Line 3: Prefix for output files.  When the program finishes, output will be written into several different files.  In the example, all the output files will be written into the subdirectory "out" and will start with the prefix FP_9_02_2005_.

Line 4: N = Number of symbols in the shift.

Line 5: Values for K, the shift period.  Specify ranges of values using [a,b] notation or specify single values as a number.  Different sets of values are separated by ';'.  The use of whitespace on this line is not important.

Line 6: m = the length of the m-words to check for.

Line 7: "BEGIN DEFINITIONS."  This signifies that on the following lines you will define functions (give them names).  This line is not case sensitive: "BeGiN DeFiNiTiOnS" is equally valid.

The definitions section is used to name functions so that the names can be used in the command section.  Defining a function does not mean that FDense will analyze that function. You must give the command to analyze a function in the command section.

Lines 8 - 10: The first function is named "func1."  A function can be named with any single word (i.e., a string of characters with no spaces).  The = signifies that the function on the RHS is named by the LHS.  This function, "func1," is specified in lookup table syntax.  The 't' signifies that the function is specified as a table.  The first value in parenthesis is the span of the function and the second value is the table itself.  The rules for specifying lookup tables are explained in "Lookup table syntax" below.

The second and third functions are specified as polynomials.  Certain rules apply to specifying functions as polynomials: see the section "Polynomial syntax" below.

NOTE: Using a lookup table is many times faster than calculating a polynomial (in tests, one function was 25 times faster as a table than as a polynomial).  However, one can optimize functions specified as polynomials to make them as fast as a lookup table.  See the section "Optimizing polynomial functions" below.

Line 11: "BEGIN COMMANDS."  This signifies that you are done defining functions and will now give commands on the following lines.

The commands tell the program which functions it should analyze.  In the command section, you specify functions and compositions by using the names you defined in the definitions section.  You cannot write polynomials or lookup tables themselves in the command section.  The program generates two output files for each function/composition in the command section (see "Output" section).

Lines 12 - 13: The # character signifies composition.  Hence, the line "M#A" tells the program to analyze the composition  (A(x)).  Compositions can be arbitrarily long; you can compose 3, 4, 5, or as many functions as you would like.  Both functions that were specified as polynomials and lookup tables can be used in compositions.  The next line "func1" tells the program to analyze the function "func1."

Output
----------

If the "no group" mode is chosen:

Running the program on Input1.txt generates two files in the subdirectory "out": FP_9_02_05_M#A.txt and FP_9_02_05_func1.txt.  If files already exist with these names, they are overwritten.  Note that the subdirectory "out" must already exist for this to work.  FPeriod will not create directories.

It happens that M#A = func1, so the results for both sets of files is the same.  A summary is given telling whether, for each K, the jointly periodic points are m-dense or not.  Afterwards all the m-words not appearing in the jointly periodic points in the union of all K are outputted, or if there are no such m-words, then "m-dense" is outputted.

The list is always in lexicographic order and truncated, meaning that if all the words with a certain prefix are in the list, then only the prefix is given.  For example 0--- -- signifies that all words beginning with 0 are in the list.

If the "group" mode is chosen:

A file called FP_9_02_05_group.txt is created.  This file lists for which maps and for which K values the jointly periodic points are m-dense.

Polynomial syntax
-------------------------
The operators +, -, *, and ^ may be used.  No parentheses are allowed, so strict order of operations must be followed.  Often this means that you must simplify by hand a function you wish to express.  The coordinates of the x terms are relative (and can be positive or negative).  When calculating image[i], the term x[j] refers to the absolute coordinate x[i + j] (e.g., when calculating image[2], the term x[-5] refers to the absolute coordinate x[-3]).  Positive integer constants are allowed.  Do not use negative constants; instead, change an addition (+) to a subtraction (-).  There is one exception to this rule: you may use a negative constant if it is the very first thing in the function (in this case you could not create a subtraction).  When writing multiplication, be sure to use *.  You cannot juxtapose terms/constants to imply multiplication.  The use of white space is not important.

Examples of valid polynomials:
a = x[0] + x[1] * x[2]
b = x[-9] ^ 5 + x[2] * x[3] * 3 + x[5] * x[102] + x[17] + x[-300] * 3
c = - x[99]

Examples of invalid polynomials:
d = x[0] * -1
e = (x[0] + x[1]) * x[2]
f = x[0]x[1]

Lookup table syntax
---------------------------
Suppose we want to specify the function f = x[0] + x[1]*x[2] as a table.  First, note that the function is of span 3.  Enumerate the values of the function for values of x[0], x[1], and x[2], going through them in lexicographic order as demonstrated below.  Notice that incrementing starts at x[2] rather than x[0].

       0 1 2 3 4 5 6 7
x[0]   0 0 0 0 1 1 1 1
x[1]   0 0 1 1 0 0 1 1
x[2]   0 1 0 1 0 1 0 1
f      0 0 0 1 1 1 1 0

Then the lookup table is "t(3, 0001 1110)".  The use of whitespace is not important.

Commenting out
---------------------------
Lines in the definitions section (after "BEGIN DEFINITIONS" and before "BEGIN COMMANDS") and the commands section (after "BEGIN COMMANDS") can be commented out by preceding them with "//". Commented out lines are completely ignored.  In the example Input1.txt, if the last line was replaced with "//func1", the program would not analyze func1.

Optimizing polynomial functions
---------------------------
Optimizing a polynomial function can be a good way of making the program run faster.  To optimize a polynomial function, precede the definition of the function with "OPT" (case-insensitive). In the example Input1.txt, one could replace the definition of A with "opt A = x[0] + x[1] * x[2]".  FDense optimizes the polynomial by precomputing the value of the function for all possible input x[i] values and storing the results in a table.  This allows the function to be evaluated very quickly later on.

It is almost always a good idea to optimize polynomial functions, but there are instances when optimization is inadvisable.  Consider the function "opt func2 = x[0] + x[1] + . . . + x[99] + x[100]". This function has 100 distinct x[i]'s.  Supposing FDense was run with N = 2, precomputing the function would require storing 2^100 values, far more than the capacity of any computer in existence.  As a rule of thumb, precomputing and storing up to a million values is probably fine as this would require memory in the range of megabytes or dozens of megabytes.  Much more than that is not advised.  Also be aware that only the number of distinct x[i]'s is important and not the span.  For example, "func3 = x[-1000] + x[1000] + x[1000]^2" has only 2 terms and is easily optimized.

NOTE: preceding the definition of a lookup table function with "OPT" does nothing.
