From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Infinite Finite State Automata (was: Re: Nonterminating computations)
Date: 11 Oct 1992 16:39:08 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4

(Describing a non-terminating system):
In article <LOWRY.92Sep29102749@rotor.watson.ibm.com> lowry@watson.ibm.com (Andy Lowry) writes:
>So here's a question: What, if anything, can/should computer theorists
>do to address the needs of this sort of system?

That's obvious.  You described a finite state automaton with no final state.
An infinite finite state automaton, if you will.  So that's what you would
represent it by.

(Actually, what you really have is a Markov Process in which transitions to
the real Final State have low probability)

A finite state automaton would be represented, say, by its state diagram, for
instance:

           a           b
     [0] ------> [1] -----> [[2]]
                     <-----
                        c

where states bracketed in [[ ]] are final states, and [0] the start state.

This could be represented in equational form as:

                [0] = a [1]
                [1] = b [2]
                [2] = c [1] + 1

where 1 is defined such that 1 x = x = x 1 (1 = "empty string").

Normally you would talk about the regular expression "equivalent" to the
finite state automaton above, namely a b (c b)*.  This expression can also be
considered as the "solution" to the system of equations above.  However, it's
not just any solution.  In order to guarantee UNIQUENESS, you need something
along the lines of a LEAST FIXED POINT property, which will guarantee that
the unique solution to systems like that above is also the "smallest".

If you remove this restriction then you're allowing infinite strings to be
solutions to the system above, for example a b c b c b c b ...

Now if you change the automaton above so that [2] is no longer a final state,
then you have an "infinite" finite state automaton.  But now the system of
equations above will read:

                         [0] = a [1]
                         [1] = b [2]
                         [2] = c [1]

and now the "least fixed point" solution to the system is [0] = [1] = [2] = 0.
So now it's no longer just a nice idea to remove the least fixed point
restriction, it's necessary if you want to be able to talk about non-trivial
solutions for infinite FSA.

So that's whats needs to be "fixed".

As a result you're now talking about infinite regular expressions.  I think
that all solutions to systems like those above can be expressed in closed form
using the operators:

                     a b -- Concatenation
                     a + b -- Alteration
                     0, 1 -- the Identities
                     a* ---- the Star operator
                     a# ---- the Infinite Repitition operator.

For instance, 1/3 = 0.(3)#, and 1/7 = 0.(142857)# in decimal, using this
notation.  Call these Infinite Regular Expressions.  So basically, then, I'm
making a conjecture:

        Infinite Regular Expressions are equivalent to Infinite FSA.

   Another point of relevance.  You have to somehow restrict the meaning of
the ()# operator, because otherwise, the set:

                            (0 | 1)#.

would denote every single infinite sequence of 0's and 1's, which there is
an uncountable number of.  This set is provably not computeable.  So one way
to define ()# is as follows:

    A# = { computeable sequences a0, a1, a2, ... with the a's taken from A }

But now (0 | 1)# is essentially a compact way of denoting the Universal Turing
Machine itself.
Newsgroups: comp.theory