# What is a weighted or probabilistic automaton?

I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank).

Therefore, I'm looking to implement an automaton, which I think should handle "value hierarchies". What I mean is that each "next possible state" should have a value that determines how "relevant" it is relative to the state from which are to be moved to it.

Is this called a weighted automaton?
Or a probabilistic automaton?

This is what I want:

To be able to have the states that can be "moved to" have different "relevancy values".

My application reminds of this:

(notice the "sub contexts" centered at the blue texts)

I think it's an automaton that (in my program) would be going through those "sub contexts" (moving from blue text to blue text, based on user input). But what kind of automaton?

• What is the semantics you're looking for? Do you want to rank runs according to relevance? Do you have nondeterminism? (there isn't an alphabet in your figure). – Shaull Dec 25 '15 at 20:08
• @Shauli This is supposed to be deterministic (produces always the same computation). I don't understand the question regarding semantics. I merely want to balance the edges or nodes and have the automata "read" them. The automata should be able to create runs to all nodes, i.e. all paths should be "explorable", but the one which is explored will depend on the selections the user makes "in the previous node" (I'll be asking for "which relevancy you want?"). – mavavilj Dec 25 '15 at 20:10
• If it's deterministic, there should be some alphabet. For example, where do you go from node 1? (there are several options). Do you just take the one with the highest value? Also, are these edges even directed? On first glance, this doesn't seem like an automaton at all. More like a weighted undirected graph. – Shaull Dec 25 '15 at 20:13
• @Shauli It's sort of difficult to conceptualise, but as of now I think that the starting point will be a weighted graph like the above. Then there will be some "automaton" performing "context switches" on the graph. Context switching means "switching between subsets of the graph", which I think is an "automaton". – mavavilj Dec 25 '15 at 20:17
• I'm sorry, but this is too vague for me to be able to help... – Shaull Dec 25 '15 at 20:29

The important thing is that a weighted automaton defines a function $f:\Sigma^*\to \mathbb{R}$, instead of a Boolean language (which can be thought of as a function $g:\Sigma^*\to \{0,1\}$).