🔒 Locked

FSM Implemented with Graph Data Structure

Started by lrh9 Jun 5, 2012 at 9:39 AM 3 replies 4.2k views

Original Post

Jun 5, 2012 at 9:39 AM

I've been reading about finite state machines, and - as I understand it - they can be represented by graphs. I wonder if FSMs implemented on a graph data structure would have any special or unique practical applications. I have a gut feeling that finding paths between two states and finding predecessors or successors of a given state might have practical applications, but I can't imagine any detailed use cases. I could see finding the shortest path between two states as a way to determine the minimal set of states an actor must traverse when going from one state to another, and I could see predecessors or successors used to enable systems to reason about the previous and next states of a system based on the current state. Thoughts?

nigo

Jun 5, 2012 at 6:22 PM

A FSM graph is the same thing than a chunk of code, where your transition rules are the IFs, your cycles are your FORs & WHILEs and nodes are procedural chunks of code, or basic blocks (look it up).

The similarities are most obvious when you look at code to parse computer language grammars, like say, a java parser. A parser generated by yacc/bison would generate a traditional table based FSM while a recursively descent parser generated by, say, CoCo/R or a human, would look like traditional code.

Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

Alpha_ProgDes

Jun 5, 2012 at 6:37 PM

Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.

[/quote]

ApochPiQ

Jun 5, 2012 at 6:51 PM

Could you represent a practical FSM as a graph data structure? Sure. But why would you want to?

Most FSMs in practice are just simple transition logic around a lot of interesting state logic. There's not much purpose to building a "framework" there unless you want to make a visual FSM editing tool for designers or something similar; even that has limited usefulness in my experience, because designing the states and transitions is the borderline-trivial part of doing FSM-based AI. The interesting part is implementing the state logic and doing the correct reasoning to invoke the transitions.

Just looking at a pretty graph structure doesn't really give you that much insight into what a FSM implementation is all about.

nigo

Jun 5, 2012 at 7:24 PM

There is no way a Lisp program would achieve intelligence without human intervention and I am still waiting after so many decades.

Rule evaluation != reasoning.

[quote name='nigo' timestamp='1338920546' post='4946539']Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.

I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.

[/quote]
[/quote]

Your point being?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.