1
$\begingroup$

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:

http://engineering.flipboard.com/2014/10/summarization/ (From: http://engineering.flipboard.com/2014/10/summarization/)

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

My application reminds of this: enter image description here

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

(From: http://shadow.cios.org:2222/www/vcceguide/images/full-screen/vcce-menunew-conceptanalysis-1c3b-tripleconceptnetwork-conceptmenusearch.png)

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$
    – Shaull
    Commented Dec 25, 2015 at 20:08
  • $\begingroup$ @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?"). $\endgroup$
    – mavavilj
    Commented Dec 25, 2015 at 20:10
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Dec 25, 2015 at 20:13
  • $\begingroup$ @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". $\endgroup$
    – mavavilj
    Commented Dec 25, 2015 at 20:17
  • $\begingroup$ I'm sorry, but this is too vague for me to be able to help... $\endgroup$
    – Shaull
    Commented Dec 25, 2015 at 20:29

1 Answer 1

Reset to default
7
$\begingroup$

The setting you suggest is not clear enough to determine what kind of an automaton you are looking for.

A short explanation regarding the types of automata:

A weighted automaton is typically an automaton with a weight function on the edges (or states). Then, a run is assigned a weight according to the weight it traverses. There are many different semantics for the value of a run. These include the maximum/minimum weight, the sum, a discounted sum, an average, etc. Finally, nondeterminism is resolved with some semantics. Typically max/min.

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\}$).

Probabilistic automata can be thought of as a sort of weighted automata, but a distinction is usually made (mainly because weighted automata are often defined over a tropical semi-ring). In probabilistic automata, the "weights" (probabilities) are multiplied along a run, and the sum of the (accepting) runs is taken.

If you elaborate or demonstrate the scenario you are thinking of, perhaps I can modify the answer to suggest an appropriate model.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.