1 Introduction↩︎

Connecting and comparing algorithmic problems over different algebraic structures is a well-known challenge. Consider the complexity classes \(\mathrm{NL}\) and \(\oplus\mathrm{L}\) corresponding to language recognition by logarithmic-space Turing machines. \(\mathrm{NL}\) machines accept a word if there is a positive number of accepting runs while \(\oplus\mathrm{L}\) machines accept if there is an odd number of accepting runs. It is still not known whether the inclusion \(\mathrm{NL} \subseteq \oplus \mathrm{L}\) (or its converse) holds; see [1], [2]. A complete problem for NL is the acceptance problem for nondeterministic finite automata, that is, given an NFA \(A\) and a word \(w\), decide whether \(A\) accepts \(w\). Similarly, a \(\oplus\)L-complete problem is the acceptance problem for weighted automata over the two-element field [3].

Weighted automata over the two-element field are also known in the literature as symmetric difference automata (\(\oplus\)-NFA) [4], or XOR-nondeterministic finite automata (XNFA) [5], or Mod \(2\) Multiplicity Automata (M2MA, for regular languages over infinite words) [6]. In this paper we use the term ‘XNFA’. A logspace reduction from NFA Acceptance to XNFA Acceptance would show that \(\mathrm{NL} \subseteq \oplus \mathrm{L}\). In a similar spirit, it is not known how the time complexities of these two problems compare (as we discuss below in sections 1.1 and 2).

XNFA are a variant of standard finite automata in which an input word is accepted if and only if the number of accepting runs is odd [7], [8]. Like nondeterministic and deterministic finite automata, XNFA recognise exactly the class of regular languages. Much like NFA, XNFA are exponentially more succinct than deterministic automata [7]; they are incomparable with standard NFA in terms of succinctness. As weighted automata over a field, XNFA also enjoy properties stemming from the algebraic structure. Their complementation requires little effort, and the number of states can be minimised in cubic time [3], [9]; whilst minimising NFA is PSPACE-hard [10]. Angluin-style learning using only polynomially many queries in the size of the minimal automaton is possible for XNFA, while this is not the case for NFA [11].

Our work is part of a quest to understand the impact of the underlying algebraic structure on the computational complexity of algorithmic problems. The two-element field and the Boolean semiring are the simplest examples of a field and an idempotent semiring, respectively. How does this structure influence algorithmic properties of weighted automata?

We take the ‘fine-grained lens’: while all these problems (except NFA equivalence) can be solved efficiently, we are interested in optimising the degrees in polynomial time bounds, i.e., \(k\) in \(O(|A|^k)\) where \(|A|\) is the size of description of the automaton \(A\). Fine-grained complexity aims to match upper bounds on the running time of algorithms with lower bounds, conditional on a small number of common complexity assumptions.

1.1 The acceptance problem↩︎

Acceptance is perhaps the most basic problem that one can pose about automata. If \(A\) is an NFA, the textbook algorithm for it determines, for each prefix of the input word \(w\), which states can be reached on that prefix. The running time is \(O(|A| \cdot |w|)\), where \(|A|\) is the sum of the numbers of states and transitions of \(A\) and \(|w|\) is the length of \(w\). Essentially the same algorithm can be used for XNFA acceptance as well.

Is the running time optimal?

Interestingly, it is unknown whether substantially faster algorithms may be designed for NFA and XNFA Acceptance. Bringmann et al. [12] have recently hypothesised that, for NFA, there is no algorithm with running time \((|A| \cdot |w|)^{1-\varepsilon}\) for any real \(\varepsilon > 0\). This NFA acceptance hypothesis does not appear to be a consequence of standard complexity assumptions, fine-grained or not [12]. The NFA acceptance hypothesis really concerns dense NFA; i.e., those with many more transitions than states. Indeed, for sparse NFA (having \(n\) states and \(O(n)\) transitions) a faster than \((n \cdot |w|)^{1-\varepsilon}\)-time algorithm would contradict the well-established Orthogonal Vectors Hypothesis and thus also the Strong Exponential Time Hypothesis (SETH) on the complexity of Boolean satisfiability, SAT (see, e.g., [13]). This conditional lower bound is matched by the textbook algorithm.

The state of the art raises a question: is XNFA Acceptance similarly hard?

Our approach: Analysis by ambiguity.

We consider the acceptance problems under assumptions on the ambiguity of automata, i.e., possible number of runs relative to the length of the input word. Classes of unambiguous, finitely-ambiguous, and polynomially ambiguous weighted automata are well-known and can be characterised in terms of structure of the transition graph [14]. The ‘ambiguity class’ can be decided in polynomial time [14], and fine-grained complexity bounds have been obtained recently [15]. Analysis by ambiguity is an established tool in the research on weighted automata, used to obtain (un)decidability and complexity results [16]–[18] as well as language-theoretic properties [19].

Our contributions.

For acceptance problems, we show two results.

1. The value problem for weighted automata of bounded ambiguity can be decided faster than in time \(\Theta(|\delta| \cdot |w|)\), where \(\delta\) is the set of transitions.

More precisely, if for every word \(A\) has at most \(k\) accepting runs on it, the standard algorithm for the value problem has a running time of \(O(k |Q| \cdot |w| + |\delta|)\), assuming unit-cost arithmetic in the underlying algebraic structure. An important special case is \(k = O(1)\), referred to as finite ambiguity. While we phrase this result more generally in terms of the value problem of weighted automata, it naturally specialises to both NFA and XNFA. We highlight the special case of unambiguous finite automata (see, e.g., [20]), in which there is at most one accepting run for every \(w \in \Sigma^*\). Every unambiguous automaton can be seen both as an NFA and as an XNFA; and every language recognised by an XNFA or NFA has an unambiguous automaton too (albeit possibly an exponentially bigger one, by determinisation). For \(A\) unambiguous, our running time of \(O(|Q| \cdot |w| + |\delta|)\) solves an open problem posed by Kiefer and Ryzhikov [21] on the complexity of multiplying matrices from zero-one matrix monoids.

2. There is a randomised reduction from NFA acceptance to XNFA acceptance, under the assumption of polynomial ambiguity.

Let \(A\) be an NFA for which there exists a polynomial \(p \colon \mathbb{N} \to \mathbb{N}\) such that every word \(w \in \Sigma^*\) has at most \(p(|w|)\) accepting runs. We give a randomised algorithm that takes such an NFA \(A\) and a word \(w\) and produces XNFA \(A_1, \ldots, A_k\), \(k = \Theta(\log |w|)\), such that, with probability at least \(1/2\), \(A\) accepts \(w\) iff at least one of \(A_i\) accepts \(w\). Moreover, the reduction has only one-sided error: if \(A\) rejects \(w\), then all of \(A_i\) reject \(w\) as well. The reduction is fast enough to yield the following conclusion: if there is an algorithm for XNFA acceptance running in time \(O((|\delta| \cdot |w|)^{1-\varepsilon})\) for some \(\varepsilon>0\), then there is a randomized algorithm for polynomially ambiguous NFA acceptance running in time \(O(|\delta| + |w| + (|\delta| \cdot |w|)^{1-\varepsilon})\), up to polylogarithmic factors.

As we discuss below, prior work suggests that NFA Acceptance may already be hard for polynomially ambiguous automata. By our reduction, XNFA Acceptance cannot be easier. The reduction raises the question of whether parity acceptance can circumvent existing complexity obstacles: can we build on this reduction to refute the NFA Acceptance hypothesis? We leave open the existence of faster algorithms for unrestricted (X)NFA acceptance.

1.2 The emptiness and equivalence problems↩︎

The equivalence problem, that is, whether two automata recognise the same language, is a natural algorithmic problem. Its computational complexity varies depending on the model of computation. For NFA it is PSPACE-complete [22] but for XNFA, thanks to the ring structure on \(\{0,1\}\), it is easily reduced to the emptiness problem: whether a single given automaton accepts at least one word. Emptiness can be decided efficiently, in cubic time [3], [5]. More generally, emptiness and equivalence for weighted automata over fields can be decided in polynomial time [3], [23], [24]. Over the field of rational numbers, equivalence is in RNC and NC [25], [26], and is in fact C\(_{=}\)L-complete [27]. Several sources describe algorithms that decide emptiness using \(O(|\Sigma| \, |Q|^3)\) field operations and thus equivalence with \(O(|\Sigma| \, (|Q_1| + |Q_2|)^3)\) operations; see, e.g., [24].

Is the cubic dependency of the running time on \(\boldsymbol{|Q|}\) optimal?

It is open even for \(|\Sigma| = O(1)\) whether, for XNFA, the dependency on \(|Q|\) can be made subcubic. With randomness, running time \(O(|Q| \cdot |\delta|)\) can be achieved [26], which is subcubic for sparse but not dense automata. We have not been able to find a lower bound for this problem. We ask, however, what are suitable sources of hardness for a hypothetical lower bound.

Our contribution.

We show the following result.

3. Reductions from the Strong Exponential Time Hypothesis (SETH) are unlikely to prove the optimality of cubic algorithms for XNFA emptiness and equivalence.

Reductions from SETH are a standard tool for conditional lower bounds [13]. We show, more precisely, that a reduction with the required properties would contradict NSETH, the nondeterministic version of SETH [28]. A refutation of NSETH would give a better-than-\(2^n\) proof system for propositional tautologies as well as establish new circuit lower bounds [28]. In fact, we prove a slightly more general statement, namely that reductions from SETH are unlikely to prove the optimality of current cubic algorithms for zero-ness and equivalence for weighted automata over fields.

To obtain this result, we describe efficient certification schemes for XNFA (and weighted automata) emptiness and non-emptiness. Informally, this means that a knowledgeable prover can come up with a suitable certificate (or ‘proof’) that the language of XNFA is empty or non-empty. (For NFA non-emptiness, for example, a certificate can be an accepting run; but this does not work for XNFA.) Crucially, the verification of a certificate may be more efficient than solving the problem from scratch. We describe how to certify both emptiness and non-emptiness of XNFA so that a suitable verifier can check the certificates in time \(O(|\Sigma| \, |Q|^\omega)\), where \(\omega \leq 2.38\) is the matrix multiplication exponent. This shows XNFA emptiness solvable in nondeterministic time \(O(|\Sigma| \, |Q|^\omega)\) as well as co-nondeterministic time \(O(|\Sigma| \, |Q|^\omega)\). By known results [28], it follows that any reduction from SETH for a lower bound stronger than \(\Omega(|\Sigma| \, |Q|^\omega)\) would contradict NSETH.

For the XNFA equivalence problem, our results extend directly from the emptiness problem. As mentioned above, the certification schemes also apply to the standard (non)emptiness and (non)equivalence problems for weighted automata over other fields.

2 Related work and discussion↩︎

Fine-grained reductions showing conditional lower bounds for automata-theoretic problems have been known for over two decades [29]. Several years ago Potechin and Shallit [30] showed that, for every real \(\alpha \ge 2\), if there is an algorithm that decides in time \(O(n^\alpha)\) whether an NFA with \(4 n\) states accepts a word of length \(n+2\), then there is also an algorithm with the same running time that decides if an \(n\)-vertex undirected graph contains a triangle. For the latter problem, called triangle detection, the best algorithms run in essentially the same time as best matrix multiplication algorithms, \(O(n^\omega)\).

The appearance of the matrix multiplication exponent \(\omega\) is not coincidental. As observed by Bringmann et al. [12], other existing reductions in the literature show that any (hypothetical) faster algorithms for NFA Acceptance would need to employ fast matrix multiplication. In a nutshell, this is established by a reduction from the \(k\)-Clique problem; for brevity we refer to it as “Bringmann et al.’s reduction”. Bringmann et al.’s reduction, as well as Potechin and Shallit’s reduction, can be seen as evidence for the above-mentioned NFA acceptance hypothesis. The hypothesis itself, in effect, postulates that fast matrix multiplication techniques cannot offer substantial running time improvements for NFA Acceptance.

[obs:triangle-to-xnfa] above suggests that, for instance for the regime \(|Q| = \Theta(|w|)\), algorithms for XNFA Acceptance faster than matrix multiplication are unlikely to exist.

Intuitively, our reduction from polynomially ambiguous NFA Acceptance to XNFA Acceptance increases the conjectured hardness level: from \(n^\omega\) (based on triangle detection) to \(n^3\) (based on NFA Acceptance hypothesis on words of length \(\Theta(|Q|)\)). Arguably, a catch is that we assume that the NFA has polynomial ambiguity. However, this assumption is far from trivialising the problem.

(E.g., hard instances in [30] have \(O(|w|^3)\) accepting runs for every \(w\); and \(|Q| = \Theta(|w|)\).)

Generally, even randomised faster algorithms for the acceptance problems are of much interest. The state of the art for NFA Acceptance is an \(|Q|^2 \cdot |w| / 2^{\Omega(\sqrt{\log |Q|})}\)-time algorithm, assuming \(|\Sigma|=O(1)\): reduce [12] the problem to online matrix-vector multiplication in dimension \(n\), for which the naive algorithm achieves time \(O(n^3)\) but a randomised one running in time \(n^3 / 2^{\Omega(\sqrt{\log n})}\) exists [32]. For every \(c > 0\), function \(2^{c \sqrt{\log n}}\) grows faster than \((\log n)^k\) for all \(k > 0\) but slower than \(n^\varepsilon\) for all \(\varepsilon > 0\). No similar improvement over \(n^3\) is known for XNFA Acceptance, and in particular faster online matrix-vector multiplication techniques are not available over the field of two elements [32].

The value problem for weighted automata, a natural generalisation of acceptance, is provably hard for the min-plus semiring [33]; the argument is not known to extend to NFA.

We have already briefly mentioned Kiefer et al.’s results [26], deciding equivalence of weighted automata over \((\mathbb{Q}, +, \times)\) in randomised polylogarithmic parallel time. As in the case of our reduction from NFA acceptance to XNFA acceptance, randomness is used by one of their algorithms for polynomial identity testing, relying on the DeMillo–Lipton–Schwartz–Zippel lemma (a non-zero polynomial over a large enough field rarely evaluates to zero at a random point). The objectives are different, however: an equivalence checker determines if two automata assign the same weight to every word, whereas our reduction looks for some accepting run in a single NFA on a given word, by checking if the parity (XOR sum) of path-weights is non-zero.

Our reduction from NFA acceptance to XNFA acceptance under the polynomial ambiguity assumption goes against a possible intuition that ‘rings are easy while semirings are hard’ for weighted automata. In support of this intuition, contrast polynomial-time algorithms for the equivalence problem on weighted automata over the ring of rationals [3], [23]–[26] with the PSPACE-completeness of equivalence for NFA [22]. Over the max-plus semiring, again with weights from \(\mathbb{Q}\), equivalence is undecidable [34], [35]. But, by our results, the acceptance problem is no more difficult (possibly easier) for polynomially ambiguous automata over the Boolean semiring (classical NFA) than for the field of two elements (XNFA).

It is also interesting to compare our results with those on the NL- and \(\oplus\mathrm{L}\)-complete problems of deciding the value of an entry in the product of multiple matrices over the Boolean semiring and over \(\mathrm{GF}(2)\), respectively; see the papers [1], [2] mentioned above.

3 Preliminaries↩︎

We begin by defining the general model of a weighted automaton.

Using this general framework, we define NFA and XNFA by specifying the underlying semiring and the interpretation of the resulting weight.

Equivalently, we can define an NFA as a tuple \((Q, \Sigma, \delta, I, F)\), where the transition relation \(\delta \subseteq Q \times \Sigma \times Q\) replaces \(\Delta\), and \(I\) and \(F\) are subsets of \(Q\) corresponding to the non-zero elements of \(\lambda\) and \(\gamma\), respectively. Whenever there is a path in the underlying labelled graph \((Q, \Sigma, \delta)\) from a state \(q\) to a state \(q'\), we say \(q'\) is reachable from \(q\) and \(q\) co-reachable from \(q'\). An automaton is trim when every state is reachable from \(I\) and co-reachable from \(F\).

An accepting run of \(A\) on a word \(w\) is a path \(\rho\) in the underlying labelled graph \((Q, \Sigma, \delta)\) that starts at an initial state \(i \in I\), ends in a final state \(f \in F\), and whose edge labels yield \(w\) when concatenated. A word \(w\) is accepted if \(A(w) = 1\), which corresponds to the existence of at least one accepting run of \(A\) on \(w\).

Similarly to NFA, we can define an XNFA as a tuple \((Q, \Sigma, \delta, I, F)\), and an accepting run of \(A\) on a word \(w\) is a \(w\)-labelled path from \(I\) to \(F\). An XNFA \(A\) accepts a word \(w\) if \(A(w) = 1\), or equivalently, if the number of accepting runs of \(A\) on \(w\) is odd.

If an NFA(or XNFA) is not polynomially ambiguous, then \(d_A(w_i)\) is \(2^{\Omega(|w_i|)}\) for some infinite sequence of words \((w_i)_{i\in\bN}\) [14].

When NFA or XNFA transition matrices are sparse (i.e., most entries are zero), representing them as full \(Q \times Q\) matrices is inefficient. In an NFA or XNFA, representing the set \(\set{q \nonscript\:\vert\nonscript\:\mathopen{}\PackageWarning{Radeks Macro}{Command suchthat used outside of matching PairedDelimiter was used on input line \the\inputlineno.}(p, \sigma,q)\in\delta}\), for all \(p \in Q\) and \(\sigma \in \Sigma\) as a single-linked list is standard and convenient for sparse automata.

4 Analysis of the dynamic programming algorithm for Acceptance and Value problems↩︎

The Acceptance problems for NFA and XNFA are special cases of the value problem for weighted automata: given a weighted automaton \(A\) and a word \(w\), compute \(A(w)\) (see 1). In this section, we show that, when the automaton \(A\) is \(k\)-ambiguous, the value problem can be decided faster than in the general case.

We describe a standard dynamic programming algorithm that computes the value of \(A\) on \(w\). We prove that, when \(A\) has a bounded number of runs to each final state on \(w\), this algorithm does not make as many transition traversals as in the worst case. As a consequence, under the assumption of \(k\)-ambiguity, this algorithm is guaranteed to run faster than the standard bound of \(O((|Q|+ |\delta|)\, |w|)\).

Let \(I\) be the initial set, i.e., the set of all states that have non-zero entries in \(\lambda\), and \(F\) be the final set, i.e., the set of all states with non-zero entries in \(\gamma\).

Note that a \(k\)-ambiguous automaton always has the property that, for every word \(w\) and final state \(f \in F\), there are at most \(k\) runs from \(I\) to \(f\) on \(w\). In terms of the usual degree of ambiguity of the automaton, 1 gives us the following bound:

As an immediate consequence, the acceptance problem for finitely ambiguous NFA and XNFA is decidable faster than in time \(O(|\delta||w|)\) too.

Whenever \(k \, |Q| = o(|\delta|)\), this improves on the naive NFA acceptance bound of \(O(|w|\, |\delta|)\). By setting \(k=1\), 1 decides if an unambiguous automaton \(A\) accepts \(w\) in \(O( |w| \, |Q| + |\delta|)\) time.

A consequence of our tighter bound for unambiguous NFA Acceptance is the following bound on the complexity of 0–1 matrix multiplication if the product is known to be a 0–1 matrix too. This resolves an open problem posed by Kiefer and Ryzhikov [21]:

5 Reducing polynomially ambiguous NFA Acceptance to XNFA Acceptance↩︎

In this section, we encode NFA acceptance of \(w\) as the question of whether a weighted automaton over a field \(\mathrm{GF}(2^k)\) computes a non-zero value on the input \(w\). We then translate this question into XNFA acceptance. To achieve this, we apply the Schwartz-Zippel Lemma for polynomial rings over fields (2).

Let \(\function{\mathbb{F}}_{}{}\) be a field. By \(\function{\mathbb{F}}_{}{}[x_1, \ldots, x_m]\) we denote the ring of (multivariate) polynomials with variables \(x_1, \ldots, x_m\) and coefficients from \(\function{\mathbb{F}}_{}{}\).

In order to apply the Schwartz-Zippel Lemma, we first turn an arbitrary NFA\(A\) into a weighted automaton, denoted \(A_{\function{\mathbb{F}}_{}{}[\vec{x}]}\), over a suitable ring of polynomials. In more detail, take \(\vec{x} = (x_1, \ldots, x_{|\delta|})\), one variable \(x_t\) per transition \(t\). For a field \(\function{\mathbb{F}}_{}{}\), the weighted automaton \(A_{\function{\mathbb{F}}_{}{}[\vec{x}]}\) over the ring \(\function{\mathbb{F}}_{}{}[\vec{x}]\) is obtained from \(A\) by using \(x_t\) as the weight of transition \(t\), for all \(t \in Q \times \Sigma \times Q\). By \(A_{\function{\mathbb{F}}_{}{}[\vec{x}]}(w)\) we denote the multivariate polynomial (over the variables \(\vec{x}\)) obtained when evaluating this weighted automaton on \(w\).

We next establish a relationship between the acceptance of a word \(w\) by \(A\) and the corresponding value \(A_{\function{\mathbb{F}}_{}{}[\vec{x}]}(w)\), under the assumption that \(A\) is polynomially ambiguous.

For a word \(u = t_1 t_2 \cdots t_l \in T^*\), over the alphabet \(T\), its Parikh image \(P_u\colon T \to \bN\) is the function that returns the number of times each symbol (in \(T\)) appears in \(u\). Given that at the cost of adding one state to \(Q\), we may assume that we have a single initial state. In the next result, we assume that, without loss of generality, there is exactly one initial state.

A polynomial \(p \in \function{\mathbb{F}}_{}{}[x_1, \ldots, x_m]\) is non-zero if it contains at least one monomial (term), and it represents a non-zero function if there exists some \(a = (a_1, \ldots, a_m) \in \function{\mathbb{F}}_{}{}^m\) such that \(p(a) \ne 0\). A non-zero multivariate polynomial of degree \(d\) over \(\function{\mathbb{F}}_{}{}\) is guaranteed to be a non-zero function if \(|\function{\mathbb{F}}_{}{}| > d\); see, e.g., [36].

Recall that if \(A\) is exponentially ambiguous, then it contains a useful state that has two cycles on the same input (see [14]). These cycles can be permuted. This justifies the ‘polynomially ambiguous’ assumption in [lem:syntax].

Next, we recall the Schwartz-Zippel lemma in the form required in this section. We write \(\Pr[\ldots]\) to denote the probability of an event.

By abuse of notation, we denote by \(A_{\function{\mathbb{F}}_{}{}}\) the weighted automaton over \(\function{\mathbb{F}}_{}{}\), obtained by taking \(A_{\function{\mathbb{F}}_{}{}[\vec{x}]}\) and replacing each variable weight \(x_t\) with a random value from \(\function{\mathbb{F}}_{}{}\). Next, we consider the relationship between whether \(A\) accepts \(w\) or not and the value of \(A_{\function{\mathbb{F}}_{}{}}(w)\).

In our setting, the field \(\function{\mathbb{F}}_{}{}\) will be a finite field of cardinality \(2^k\), for some value of \(k\): Galois field \(\mathrm{GF}(2^k)\). Next, we consider how to go from a weighted automaton over \(\mathrm{GF}(2^k)\) to XNFA. Fix a basis of \(\mathrm{GF}(2^k)\) as a \(k\)-dimensional vector space over \(\mathrm{GF}(2)\). Multiplication by any fixed element from \(\mathrm{GF}(2^k)\) is a \(\mathrm{GF}(2)\)-linear map and can therefore be represented by a \(k\times k\) matrix over \(\mathrm{GF}(2)\).

To extend the parity acceptance concept to \(k\)-dimensional field representations, we define a generalised weighted automaton model, which we refer to as \(k\)-XNFA. Although the definition can be used on any semiring, we only use it on \(\mathrm{GF}(2)\), and thus we refer to these weighted automata as \(k\)-XNFA.

Every \(1\)-XNFA is, trivially, an XNFA. We refer to the acceptance condition of a \(k\)-XNFA as the generalised parity acceptance condition. We show how to simulate a weighted automaton over \(\mathrm{GF}(2^k)\) by a \(k\)-XNFA, with a small overhead on the state and transition count.

The construction is based on the isomorphism \(\mathrm{GF}(2^k) \cong \mathrm{GF}(2)^k\) as vector spaces over \(\mathrm{GF}(2)\). The \(k\)-XNFA\(B\) simulates the evaluation of \(A_{\function{\mathbb{F}}_{}{}}\) by replacing each state of a weighted automaton over \(\mathrm{GF}(2^k)\) with a vector of \(k\) states. Each transition with weight \(r\) is replaced by the corresponding linear update (matrix multiplication over \(\mathrm{GF}(2)\)) implementing \(g\mapsto r\cdot g\) in \(\mathrm{GF}(2^k)\). The details of the construction are relegated to the appendix.

A \(k\)-XNFA can be split into \(k\) ordinary XNFA with essentially no overhead:

Directly from the second part of the previous theorem, we obtain the following results:

6 Certificates for Emptiness and Equivalence for weighted automata over fields↩︎

In this section, we describe certification schemes for the (non)emptiness and (non)equivalence problems for weighted automata over fields. Intuitively, given a decision problem \(D\) and an instance \(x\), a certificate is a string that can be used to prove that \(D\) accepts \(x\). We say that we can certify a decision problem \(D\) in time \(T(n)\) if there exists a deterministic algorithm (verifier) that takes as input pairs \((x,c)\) where \(x\) is an instance of \(D\) and \(c\) is any string. The verifier must have the following properties:

(1) If \(x\) is accepted by \(D\), there must exist a string \(c\) (certificate) of size \(|c| \leq T(|x|)\) such that the verifier accepts (\(x,c\)) in \(T(|x|)\) time.

(2) If \(x\) is rejected by \(D\) then, for all strings \(c\), the verifier must reject \((x,c)\) in time \(T(|x|)\).

This is the same as saying there is a nondeterministic \(T(n)\)-time algorithm for \(D\), viewing \(c\) as the ‘guess’ and the verifier as the ‘check’ of the nondeterministic algorithm.

For a field \(\mathbb{F}\) or semiring \(\mathbb{K}\), we denote by \(\mathrm{op}(\mathbb{F})\) or \(\mathrm{op}(\mathbb{K})\), respectively, the time required to perform arithmetic operations in it.

Our certificate schemes build on existing algorithms for deciding emptiness and equivalence. In order to certify (non)emptiness of weighted automata, our first ingredient is the certificate scheme for the NFA acceptance problem from [12]. This scheme generalises to certifying whether the value of a weighted automata over a semiring \(\mathbb{K}\) on a word is zero or not, as follows.

¿tbl:tab:section6? summarises the complexity of certification for evaluation of weighted automata, and the emptiness, non-emptiness, and equivalence problems for weighted automata over fields. We also highlight the special cases of NFA and XNFA for the same. The bounds for NFA emptiness and non-emptiness certification (marked with a \(^\dagger\) in the table) are folklore.

This approach specialises naturally to certifying whether an XNFA accepts a given word \(w\).

For our next result, we use a standard upper bound on the length of the shortest word with non-zero value by a weighted automaton over a field; see, e.g., [3], [24], [42].

This allows us to certify the equivalence of weighted automata over fields, by constructing the weighted automaton for the difference.

All of these certification schemes specialise to the case of XNFA emptiness (or equivalence). Using the above approach, we can even certify whether a given XNFA accepts every word, i.e., (non)universality, by checking equivalence with an XNFA that accepts every word.

These subcubic certificate schemes have a consequence in fine-grained complexity. As a direct consequence of 3 and 4 (and 6) and Theorem 5.1 by Carmosino et al. [28], we have:

The formal version of this statement can be found in the appendix. NSETH being false would mean there is a nondeterministic algorithm deciding propositional tautologies in time \(\function{\mathrm{O}}{2^{n (1-\delta)}}\) for some \(\delta > 0\), where \(n\) is the number of variables.

7 Open problems↩︎

We leave it open whether our randomised reduction can be made deterministic (error-less) or many-one, instead of making \(k\) oracle calls to XNFA Acceptance. Finding a fine-grained reduction in the other direction is also of interest. We do not know of problems that are provably hard for XNFA, but not for NFA. Minimal XNFA and minimal DFAs are linked: if we determinise a minimal XNFA, then we obtain the corresponding minimal DFA [4].

Our work raises the question whether parity acceptance can circumvent existing complexity obstacles. Is it possible to use our reduction to refute the NFA Acceptance hypothesis [12], or is XNFA acceptance equally hard in a fine-grained sense? In the case \(|\Sigma| = 1\), both NFA and XNFA acceptance can be solved in time \(O(|Q|^\omega \log|w|)\), see [30].

Without the assumption of polynomial ambiguity, NFA Acceptance still reduces to the non-zeroness of a polynomial, but the variables must no longer be commuting. The obstacle to overcome (or avoid) here is the high running time (on this polynomial) of state-of-the-art methods for non-commutative polynomial identity testing.

8 Reduction from NFA Acceptance to XNFA Acceptance↩︎

Here we detail the construction of a \(k\)-XNFA that simulates the evaluation of a weighted automaton over \(\mathrm{GF(2^k)}\).

In particular, \(B\) accepts \(w\) (under the generalised parity acceptance condition) if and only if \(A_{\function{\mathbb{F}}_{}{}}(w) \ne 0\).

Next, we decompose the \(k\)-XNFA we created into \(k\) XNFA.

As a direct consequence of 2, we have the following:

By the reduction presented in 2, we can also conclude the following:

9 Certificates for acceptance and emptiness↩︎

The subcubic certificate schemes we provide have a consequence in fine-grained complexity. We recall the following two popular fine-grained complexity hypotheses:

Here and below, \(n\) is the number of Boolean variables in the formula.

The following hypothesis strengthens SETH even further.

Theorem 5.1 by Carmosino et al. [28] states that if a problem \(\Pi\) has a certificate scheme that runs in a time bound \(T\), i.e. if \(\Pi \in \mathsf{NTIME}(T) \cap \mathrm{co\text{-}\mathsf{NTIME}(T)}\), then a SETH based lower bound that shows hardness stronger than \(T\) would contradict NSETH. The idea is that by composing such a reduction from SAT to \(\Pi\) with the certification scheme, one could obtain a faster nondeterministic algorithm for deciding if a Boolean formula is a tautology.

We have a certificate scheme (a nondeterministic and co-nondeterministic algorithm) for XNFA emptiness (and equivalence) that runs in \(O(|\Sigma|n^{\omega})\). Hence, we obtain the following corollary as a direct consequence of 3 and 4 (and 6) and Theorem 5.1 by Carmosino et al. [28]:

That is, if we could prove hardness above \(\Omega(|\Sigma|n^{\omega} \cdot \mathrm{op}(\mathbb{F}))\) for weighted automaton emptiness (or equivalence) subject to SETH, then NSETH fails.

Intuitively, NSETH being false would mean there is a proof system for \(n\)-variable propositional tautologies which has complexity \(\function{\mathrm{O}}{2^{n (1-\delta)}}\) for some fixed \(\delta > 0\). Further consequences of NSETH failure are discussed in [28].

References↩︎