Approximating Deterministic Lattice Automata
============================================


Traditional automata accept or reject their input, and are therefore
Boolean. {\em Lattice automata\/} generalize the traditional setting
and map words to values taken from a lattice. In particular, in a
fully-ordered lattice, the elements are $0,1,...,n-1$, ordered by the
standard $\leq$ order. Lattice automata, and in particular lattice
automata defined with respect to fully-ordered lattices, have
interesting theoretical properties as well as applications in formal
methods. {\em Minimal deterministic automata\/} capture the
combinatorial nature and complexity of a formal language. 
Deterministic automata have many applications in practice.
  
In \cite{HK11}, we studied minimization of deterministic lattice
automata. We proved that the problem is in general NP-complete, yet
can be solved in polynomial time in the case the lattices are
fully-ordered. The multi-valued setting makes it possible to combine
reasoning about lattice automata with {\em approximation}. An
approximating automaton may map a word to a range of values that are
close enough, under some pre-defined distance metric, to its exact
value.  We study the problem of finding minimal approximating
deterministic lattice automata defined with respect to fully-ordered
lattices. We consider approximation by absolute distance, where an
exact value $x$ can be mapped to values in the range $[x-t,x+t]$, for
an approximation factor $t$, as well as approximation by separation,
where values are mapped into $t$ classes. We prove that in both cases
the problem is in general NP-complete, but point to special cases that
can be solved in polynomial time.