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.3 Prime DOCAs
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.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.6 Branching Immediate Observation nets
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.7 Equivalence of Cost Register Automata: the quest for decidability
Consider the model introduced in this problem. It is mentioned therein that equivalence is undecidable for that model. We ask what further restrictions we can impose on that model to make equivalence decidable.
If the $\min$ operation is removed, then this is known to lead to decidability [Alur et al.'13]. But as soon as we have $\min$, we don't know of a model with decidable equivalence.
We conjecture that it is decidable is the CRA is ordered; this means that the registers can be ordered, say $x_1, x_2, \ldots, x_n$, such that for all updates, $x_i$ is only updated with registers $x_j$ for $j \geq i$.
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.
19.13 Does a $(\textsf{min,+})$-WA preserve REG by inverse image?
We are interested in functions realized by weighted automata over the semiring $\mathbb N_{\mathsf{ min}}=\langle \mathbb N\cup\left\{ \infty \right\} , \mathsf{ min}, +, \infty,0\rangle$. An $\mathbb N\mathsf{ min}$-weighted automaton $\mathcal A$ over alphabet $\Sigma$ realizes a partial function $\llbracket \mathcal A \rrbracket:\Sigma^*\rightarrow \mathbb N$. We want to decide given such a function if it preserves ``simple'' sets by inverse image. By simple we mean regular languages ($\mathbb N$ is viewed a the set of words over a unary alphabet, hence the regular languages are the semilinear sets). Let us state the decision problem.