Branching Immediate Observation (BIO) nets are a subclass of Petri nets defined by their transitions, which are of the form $|{}^\bullet t - t^{\bullet}| \le 1$. This multiset subtraction means that all input places of $t$ with arc weight $k$ are also output places of $t$ with arc weight $k$, except for one which may have input arc weight $k$ and output arc weight $k-1$. BIO nets generalize Basic Parallel Processes (BPP) nets and Immediate Observation (IO) nets - a token can “branch” into any number of tokens as in BPP, but may need to “observe” that another token is in a certain place to proceed with its transition as in IO.
20.6 Branching Immediate Observation nets
20.5 Regular antichain subset of the iteration of a regular language
This problem comes from a typing problem (non structural subtype assignment).
Given a regular language R, does there exist a regular language U such that:
- U is an antichain for the prefix ordering
- $\forall u \in U, \exists r \in R, r < u < r^\omega$
- $\exists u \in U, r \in R, r < u < r^\omega \wedge |r^{-1}u| > ||U||$
where $||U||$ is the number of states of the minimal automaton recognizing $U$, and $r^\omega$ is the infinite iteration of $r$.
I conjecture that such language does not exist, though I don't find an approach to attack it. If such a language does exist, it would be interesting to know if there can be an infinite number of words such that the third point holds or not.
20.4 Populations of Markov decision processes, what we know and an open question
We present the model of populations of Markov decision processes, discuss our recent result on this model, and show an intriguing open question.
20.3 Prime DOCAs
A Deterministic One-Counter Automaton (DOCA) is a DPDA with single letter stack alphabet. They can be used to define (context-free, word) languages by reaching an accepting state and counter 0.
20.2 Deterministic separability of nondeterministic timed languages
- Input: two timed languages $L$, $M$ represented as nondeterministic timed automata.
- Question: decide whether there exists a deterministic timed automaton recognising a timed language $S$ which separates $L$, $M$, in the sense that $L$ is included in $S$ and $S$ is disjoint from $M$.
The version of the problem when we fix in advance the number of clocks of the separating deterministic timed automaton is decidable. The open problem is then when the number of clocks is not fixed (and thus quantified existentially).
20.1 Universality of letter-bounded CFLs
- Input: a context-free grammar for a language $L \subseteq a_1^* \dots a_n^*$ ($n$ is part of the input)
- Question: Is $L = a_1^* \dots a_n^*$?
What is the complexity of the problem?
19.17 Existence of a universal amplifier of selection
Moran Birth-death processes are stochastic processes defined as follows. Consider a connected graph $G$ and a parameter $r \in \mathbb{R}$ strictly greater than $1$. We start with a partition of the vertices of $G$ into two types: mutant vertices, that have fitness $r$, and resident vertices, that have fitness $1$. At each step, a random vertex is chosen with probability proportional to its fitness, and spreads its type to an adjacent vertex chosen uniformly at random.
19.16 Weak validation of tree-languages by extended automata
The weak validation problem is an open problem stated in 2007 by Segoufin and Sirangelo. The problem is about checking if a regular langage of trees, seen as a languages of word (with an XML encoding), can be validated by a finite automaton with the assumption that the input is a correct tree encoding. More formally, let $T$ be the set of words encoding correct trees, $K$ be a regular language of tree with $\text{XML}(K)$ the associate languages of words. Can we decide if there exists a regular langage of words $L$ such that $L\cap T =\text{XML}(K)$.
19.15 The busy beaver problem for population protocols
Population protocols are a model of distributed computation by indistinguishable agents, close to VASs. We consider population protocols with one input state. These protocols compute predicates $\mathbb{N} \rightarrow \{0,1\}$. (For definitions see https://arxiv.org/abs/1801.00742)
For every $n \geq 1$, let $f(n)$ be the largest number such that some protocol with at most $n$ states computes the predicate $x < f(n)$.
19.14 Continuous reachability in ordered data VAS
Data VAS is a finite set of finitely supported functions from ordered data set $\mathbb{D}$ to $\mathbb{Z}^k$, where k is a dimension. A configuration/marking is a finitely supported function from $\mathbb{D}$ to $\mathbb{N}^k$.
From a configuration $m$ there is a step to $m'$ if there is a vector $x\in \text{VAS}$ and $\pi$ an ordered preserving bijection (permutation) form $\mathbb{D}$ to $\mathbb{D}$ such that $m+x\circ \pi=m'$. The reachability relation is a transitive closure of the step relation. The reachability problem is undecidable, that is why we are looking for different relaxation of it.