To join the email distribution list of the cs colloquia, please visit the list subscription page.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
Simplification of Counter Automata
https://technion.zoom.us/j/6919019730 & Taub 601
Quantitative computational models have become increasingly popular in the past few decades, since they can naturally model distributed systems and enable reasoning about quantitative properties and about infinite configuration spaces. Specific models include Petri nets, Vector Addition Systems (VAS\VASS), Weighted Automata and Counter Nets. Their usefulness lies in the fact that they retain decidability of some important decision problems.
Nonetheless, the complexities of reasoning about these models are typically very high. Thus, it is desirable to simplify these models as much as possible.
Simplification can take many forms, e.g., determinization, dimension reduction, and many more.
In this lecture I give an overview of these models, their decision problems, and our works regarding various types of simplification on them.
Specifically, I will discuss the determinization process of OCNs (one-counter nets), detail how various notions of determinization arise naturally from the intricacies of the model, and prove complexity results for the determinization decision problems that arise. I also introduce and explore the notion of history-determinism - a restriction of determinism with its own merit and relevance.
I will also introduce the notions of dimension-minimality and primality of counter nets, notions tightly linked to the concepts of minimization and simplification, and show that primality is undecidable.
Finally, I will discuss two-way OCNs (2-OCNs) -- a stronger variant of OCNs. I introduce new results of its expressive power under various restrictions, and shed light on interesting links between 2-OCNs and semilinear languages.