Lecture Notes on Weighted Automata

You may have seen the discussion on finite state automata on the Brilliant Wiki, or your own Theory of Computation course.

Weighted Automata are a generalization of the same concept where we model systems which assign some quantity to each possible trace of actions.

If you wish to learn Weighted Automata, check out the Weighted Automata course by Prof. Aiswarya at Chennai Mathematical Institute.

I am proud to note that I scribed the lecture notes for her class, and they should be self contained and approachable, provided you have some rudimentary background in Theory of Computation.

#ComputerScience

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Are weighted automata the same as markov chains?

Sravanth C. - 12 months ago

Probabilistic Weighted Automata are essentially markov chains. See Lecture 8 in Aiswarya's Course.

But no, they are more general objects.

Agnishom Chattopadhyay - 11 months, 3 weeks ago

I studied Finite State Machines, in my electronics course, which are basically mono-weighted-automata I guess :P I checked the lecture notes, but they mostly went above my head, do you recommend any other good starting point to understand moore and melay type machines or weighted automata in general?

Sravanth C. - 11 months, 3 weeks ago

@Sravanth C. – So, finite state machines typically give you an Yes/No answer: you feed it a string and it tells you "Yes/No". This way, you can view these machines as functions String -> Bool. But, in some cases, an "yes/no" answer is not good enough. One example is that you may want a probability. In which case, you'd have a function of the type String -> [0,1]. So, these kind of objects String -> S are of interest, and are called "quantitative languages". Weighted automata are just Finite state machines used to compute quantitative languages.

I agree that the notes are not as well written as they could be. There are some other notes linked in the course website, but they are only notes, not really books. Unfortunately, weighted automata is kind of a niche subject and is under ongoing development, so I don't think there are any textbooks.

That said, you could consider studying standard Theory of Computing books which include (Dexter Kozen's) books, (Hopcroft-Ullman-Motwani) or (Michael Sipser). I think Sipser's book is a pleasant and gentle read. Another interesting resource is "Principles of Model Checking" which presents somewhat different and more practical material.

Feel free to ask me more questions

Agnishom Chattopadhyay - 11 months, 3 weeks ago

@Agnishom Chattopadhyay – Sure thanks! Do you need understanding of graph theory too? Cuz these markov chains look a lot like graphs..

Sravanth C. - 11 months, 3 weeks ago

@Sravanth C. – You don't need that much understanding of Graph Theory. Some basic idea will do.

Agnishom Chattopadhyay - 5 months, 3 weeks ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$