NOTE This topic/question is purely mathematical, but potentially with some interesting relevance to multi-agent systems in the AI sense.
Suppose, for example, I want a network that once started will run indefinitely, always visiting all of its states before repetition. What is (1) a sufficient condition and (2) a necessary condition for this property?
NOTE For the precise definition of a Finite State Automaton (aka Finite State Machine) see any relevant textbook or the Wikipedia article.
You could start with Cisco website or even Juniper, as they have the market share of company networks. Am I to understand this would be a closed system, in other words no access to the internet? What sort of limitations or particular properties are you look for? I work to design networks from very large - Deautcha Borse AG - German Stock Exchange - to branch in Chicago (as a team member) to mom and pop organizations (by myself all of which were successful).
I look forward to your reply...
Hi Daniel!
Many thanks for your answer. Clearly you design and implement real networks out there in the real world. By contrast, I am a (sort of) pure mathematician interested in precisely defined abstractions. Hence my interest in precise definitions of closed networks of Finite State Automata and studies of their properties.
You may well be inclined to dismiss abstract networks as of no practical importance. I can only offer you the old dictum: “Abstraction is the high road to insight”.
A particular and quite well-known family of design problems go by the name “The Consensus Problem” – essentially how to so design a network that its semi-independent component systems all come to an agreed and good conclusion/recommendation, in spite of sundry complications. See the long Wikipedia article…
Hope this is of some interest to you.
Regards
Jim
��wKfy�
Hi James,
I'm not sure if this is what you are looking for, but there is a wealth of work on how automata can be synthesised given some specification for the system expressed in some suitable formalism, such as temporal logic. Some summaries of this are given in the following:
https://www.react.uni-saarland.de/publications/F16.pdf
https://theory.stanford.edu/people/nikolaj/dimacs96.ps
If you already have an automata, and you want to check that it has some desirable properties --or conversely, does not have some undesirable properties-- then there is an automated algorithmic technique called model checking that can determine this. There are a number of well-established tools for this. If the automata does not exhibit the desired behaviour then the technique can generate a counterexample -- an execution path of the automata along which the undesirable behaviour occurred.
https://dl.acm.org/citation.cfm?id=1373322
https://dl.acm.org/citation.cfm?id=332656
I hope this helps!
Paul
Hi Paul,
Many thanks for your very helpful response to my question. I was only dimly aware that so much work has been done on the design and properties of individual FSAs.
However you do not mention (closed) networks (suitably defined) of FSAs which is my particular interest. Are networks addressed in the sources you give?
Is it perhaps (I wonder) the case that any network of FSAs is provably equivalent to a corresponding individual FSA in some precise sense so that ALL the properties of networks (including those of interest for the purposes of network design) can be derived from the properties of their equivalent individual FSAs?That might be elegant!
Thanks again
Best
Jim
s%
Some further thinking behind my question:
If the well-known “consensus” problem is formulated as getting from any particular set of FSA initial states to the right “consensual” (i.e. all agree) terminal collective decision, then I am confident that the implicit “lookup” table can be implemented/computed even if the computation has to be distributed over many FSMs -- just because any finite computation can be performed on an FSA provided it’s within its size/speed limits. Of course, signals and states have to be suitably and consistently interpreted as part of the network design. But is this viewpoint misconceived? If it's OK, where can I read about it? It must already have been fully worked out?
Another and possibly more interesting question is: can there be consistent Interpretations of signals as sensory input and action output leading to a consistent interpretation that there is a virtual SPATIAL reality SHARED by a subset of the FSA?
Regards
Jim
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs