Given two regular languages \(L_1\) and \(L_2\), we can define the left language quotient operations as \(L_2\backslash_lL_1 := \{ v \ \vert \ \exists u, uv \in L_1 \land u \in L_2 \}\). The Brzozowski derivative is a special case of the left quotient by a singleton language: \(\{c\}\backslash_lL_1 := \{ v \ \vert \ cv \in L_1 \}\).\[\\\] This leads to the following question: is there a purely inductive definition of the left quotient operation on regular expressions? i.e. a function \(f : RE \times RE \to RE\) s.t. \(\mathcal{L}(f(R_2,R_1))=\mathcal{L}(R_2)\backslash_l\mathcal{L}(R_1)\).
25.28 A Streaming Machine Model for Polyregular Functions
The class of polyregular functions corresponds to the class of functions accepted by reversible, two-way pebble transducers. As the name suggests, the lengths of the generated outputs are polynomial in the lengths of the input, unlike regular, rational and sequential functions, where the output length is linear in the length of the input. Regular functions are known to be captured by deterministic two-way transducers. There is an attractive, one-way machine for regular functions, namely, deterministic "copyless" streaming string transducers (SST). Like two-way transducers, SSTs are closed under composition.
25.27 Increasing-unbounded Simple Components
A one-counter MDP (OC-MDP) \(M\) is an MDP where each transition is labeled by an integer which is added to the counter whenever the transition is taken. A counterless MD strategy (cMD) \(\sigma\) on \(M\) is a function assigning to each state a single action. Applying \(\sigma\) to \(M\) yields a one-counter Markov chain \(M_\sigma\). We call a sub-OC-MDP of \(N\) a simple component of \(M\) if \(N\) is exactly a BSCC of \(M_\sigma\) for some cMD strategy \(\sigma\). Given a simple component \(N\), let \(p\) be some state of \(N\) and let \(X\) be a random variable encoding the change of the counter of a run on \(N\) initiated in \(p\) and till \(p\) is revisited for the first time. Let E(X) denote the expected value of \(X\).\(\\\)
We define the following (note it can be shown these are invariant to the choice of \(p\)):\(\\\)
- \(N\) is bounded if \(P(X=E(X))=1\),\(\\\)
- \(N\) is unbounded if \(P(X=E(X))<1\).\(\\\)
and:\(\\\)
- \(N\) is increasing if \(E(X)>0\),\(\\\)
- \(N\) is zero if \(E(X)=0\),\(\\\)
- \(N\) is decreasing if \(E(X)<0\).\(\\\)
For example a simple random walk (+-1 with equal probability) would have a single zero-unbounded simple component.\[\\\]
The question is:
Given a OC-MDP \(M\), what is the complexity of deciding whether \(M\) contains an increasing-unbounded simple component? What is the complexity of this problem for the subclass of OC-MDPs that contain no decreasing simple components?
25.26 Memory requirements of subgame perfect equilibria in reachability games
A subgame perfect equilibrium (SPE) is a formalisation of rational behaviour in multiplayer games that is a special case of Nash equilibria (NEs). An NE is a strategy profile such that no player has any incentive (with respect to their objective) to unilaterally deviate from their strategy in the profile. An SPE is a strategy profile that is an NE in every subgame, i.e., such that, if we initialise the play with any history of the game, then no player has an incentive to deviate.\[\\\]
Brihaye et al. (Inf. Comp. 2021) have shown that in \(n\)-player reachability games on finite arenas with \(m\) vertices, a memory of size at most \(m^3\cdot n\cdot 2^{3n}\) for each player suffices to construct an SPE whose outcome satisfies the objectives of a subset of players whenever such an SPE exists. This bound implies that their argument for finite-memory does not generalise to infinite arenas. This suggests the following related problems:\(\\\)
- Do finite-memory SPEs always exist in reachability games on infinite arenas?\(\\\)
- Given an SPE of a reachability game, does there exist a finite-memory SPE that enforces the same objectives?\(\\\)
- Can we provide memory bounds that are independent of the arena size for SPEs (satisfying a given subset of objectives) in reachability games?
25.25 Do probabilities matter for resolving nondeterminism?
Consider a nondeterministic parity automaton \(A = (Q, \Sigma, \Delta, q_0, \Omega),\) where: \(Q\) is a finite set of states, \(\Sigma\) is the input alphabet, \(\Delta \subseteq Q \times \Sigma \times Q\) is the transition relation, \( q_0 \in Q\) is the initial state, and \(\Omega : Q \to \mathbb{N}\) is the parity acceptance condition. We say that a probabilistic automaton \(P\) is obtained from a memoryless resolver for \(A\) if, for each state \(s \in Q\) and input symbol \(a \in \Sigma\), the nondeterministic set of successors \[\{ t \in Q \mid (s, a, t) \in \Delta \} \] is replaced by a probability distribution \(D_s^a\) over that set. The resulting probabilistic automaton \(P\) retains the same state set \(Q\), alphabet \(\Sigma\), and initial state \(q_0\), but transitions are decided by the probability distributions \( \{ D_s^a \}_{s \in Q, a \in \Sigma}, \) which define the probability of moving from state \(s\) to state \(t\) upon reading symbol \(a\).\(\\\)
25.24 Classes of languages with objective-independent memory
We start from the following fact: Given a two-player game arena \(G\) labelled with an alphabet \(\Sigma\), and an objective \(W \subseteq \Sigma^\omega\) for Player 1, if \(W\) is closed by subwords then if Player 1 has a winning strategy, she has one using memory \(\leq |G|!\). The remarkable thing is that this memory does not depend on \(W\), just on \(G\).\(\\\)
We say that a class of languages \(\mathcal{C}\) has the \(\textit{objective-independent memory property}\) if there is a function \(f\) such that for all arena \(G\) and \(W \in C\), if Player 1 has a winning strategy for \(W\) in \(G\) then she has one using memory \(\leq f(|G|)\). This property is useful in distributed synthesis. As we saw above, the class of subword-closed languages has this property, with \(f\) the factorial function.\(\\\)
The problem is to characterise classes of languages with this property, or at least identify some non-trivial examples. A first step could be to show that for all \(k\), the class \(C_k\) of languages recognised by automata with SCCs of size at most \(k\) has this property, and identify some classes that have that property but are not subsumed by some \(C_k\).
25.23 Complexity of deciding conjugacy of rational relations
The conjugacy problem for rational relations can be stated as follows:\(\\\)
\(\textbf{Input:}\) A rational relation defined by a letter-to-letter finite state transducer \(\mathcal{T}\), that is, a finite state automaton whose transitions are labeled by pairs of letters \((a,b)\) (rather than by single letters).\(\\\)
\(\textbf{Question:}\) Is it true that for every accepting run of \(\mathcal{T}\), the concatenation \(a_1a_2\cdots a_n\) of the first components of the labels is a \(\textit{cyclic shift}\) of the concatenation \(b_1b_2\cdots b_n\) of the second components? That is, does there exist \(1 \leq j \leq n\) such that: 1) \(a_i = b_{i+j}\) for all \(1 \leq i \leq n-j\), and 2) \(a_i = b_{i+j-n}\) for all \(n-j < i \leq n\).\(\\\)
25.22 Fine-grained complexity of omega-automata inclusion
The inclusion problem asks whether the language of an automaton \(A\) is included in that of an automaton \(B\). If the automaton \(B\) is deterministic, this problem can be solved in almost quadratic time by a product construction, and this bound is optimal: a \(o(n^2)\) algorithm would contradict ETH (Wehar 2016). For automata over infinite words, the problem is still in PTIME (in NL in fact), but its exact complexity is unknown. \[\\\]
\(\textbf{Goal:}\) Find upper and lower bounds on \(k\) such that the inclusion of deterministic parity automata can(not) be checked in time \(O(n^k)\).
25.21 Simulation decidability in Gap-order Constraint Systems
A Gap-order Constraint System (GCS) is a finite automaton with counters \((c_1,\dots c_n)\) where every transition bears conditions of the form \(x-y\geq n\) where \(n\) is a non-negative constant, and \(x,y\in \{c_1,\dots,c_n,c'_1,\dots,c'_n\}\cup\mathbb{N}\) where \(c_i\) denotes the value of counter \(c_i\) before the transition, and \(c'_i\) the value of \(c_i\) after the transition. For instance, a condition \(c'_1-c_1\geq 1\) on a transition means that it increases counter \(c_1\) by \(1\) or more. A condition \(c_1-0\geq 0 \wedge 0-c_1\geq 0\) means a transition requires \(c_1\) to be \(0\).\[\\\]
The problem that interests us is the simulation problem:\(\\\) Input: Two transition systems, one belonging to player Spoiler, the other to player Duplicator. Each time Spoiler makes a move on her GCS, Duplicator makes an equivalent move on his GCS. If the games goes on forever, Duplicator wins. If one player cannot make a move, the other player wins.\(\\\) Output: Does Duplicator have a winning strategy?\[\\\]
25.20 On an equivalence between finitely many tokens and one invisible token
Consider a safety automaton \(A\), i.e., an automaton over infinite words where all but one rejecting sink state is accepting. For simplicity, we assume that \(A\) has a single initial state. We will describe two game-based conditions for \(A\), which we conjecture to be equivalent. Both of these games involve a letter-picking adversary Letitia and a transition-picking protagonist Terence.
Condition 1. Explorability
For every positive natural number \(k\), the \(k\)-explorability game of \(A\) proceeds in infinitely many rounds and involves \(k\) distinguishable tokens, which are all initially placed at the initial state of \(A\). In round \(i\) of the \(k\)-explorability game, where each of the \(k\) tokens are each at some state of \(A\), the following sequence of moves are played.
- Letitia selects a letter \(a\)
- For each token, Terence selects an outgoing transition on \(a\) from the current state of that token, and then moves that token to the tail of that transition.
- The game then proceeds to round \((i+1)\).