Narrow Results

Iwama et al. showed that there exists an n-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly 2ⁿ - α states, for all n ≥ 7 and 5 ≤ α ≤ 2n-2, subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any n ≥ 4, there is an n-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has 2^{n - 1} + 2^{k - 1} - 1 states, for 2 < k ≤ n - 1. In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all n ≥ 2, we argue that there are many values of α such that there is no n-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with 2ⁿ - α states, where 0 < α < 2^{n - 1}. For each n ≥ 2, we quantify such values of α precisely.

The expressive power of logics is one of the major research topics in mathematical logic and computer science. One way of comparing the complexities of different formalisms (e.g. knowledge representation formalisms) stems from the perspective of representational succinctness. The concept of covariant–contravariant refinement (CC-refinement, for short) generalizes the concepts of refinement, simulation and bisimulation. We introduce an extension of the standard multi-agent modal $\mu$-calculus system $K^{\mu }$ with CC-refinement operators (${\mathrm{CCRML}}^{\mu }$) and show that ${\mathrm{CCRML}}^{\mu }$ is equivalently expressive to $K^{\mu }$. This paper presents the succinctness results of ${\mathrm{CCRML}}^{\mu }$ compared with $K^{\mu }$ from two viewpoints based on the sets of covariant and contravariant actions. We establish a family of CC-refinement formulas for comparing the succinctness based on the well-known parity symmetric alternating automata, which is often used to describe modal $\mu$-calculus formulas.

Two-way quantum automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any fix m ∈ ℤ⁺, we show that

(1) there is a promise problem A^meq which can be solved by 2QCFA in polynomial expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m + 2, and ;

(2) there exists a language L^mtwin which can be recognized by 2QCFA in exponential expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2^m, and ;

where b is a constant number.