Nonuniform complexity classes specified by lower and upper bounds
Normal forms for phrase-structure grammars
Normal forms for unary probabilistic automata
We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...
Normal forms for unary probabilistic automata
We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the probabilistic case of Chrobak normal form, obtained...
Normal forms for unary probabilistic automata
We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...
Normal Subgroup of Product of Groups
In [6] it was formalized that the direct product of a family of groups gives a new group. In this article, we formalize that for all j ∈ I, the group G = Πi∈IGi has a normal subgroup isomorphic to Gj. Moreover, we show some relations between a family of groups and its direct product.
Normalization of edit sequences for text synchronization
It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...
Normalization of edit sequences for text synchronization
It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will...
Normalization of place/transition-systems preserves net behaviour
Note on compatible well orders on a free monoid.
Note on decipherability of three-word codes.
Note on Stochastic Transformers
Note on studying change point of LRD traffic based on Li's detection of DDoS flood attacking.
Note on symmetric alteration of knots of B-spline curves.
Note on the complexity of Las Vegas automata problems
We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....
Note on the number of sequences with given complexity.
Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family of cyclic languages, where . In particular, we show that, for any , the number of states necessary and sufficient for accepting the unary language with isolated cut point on one-way probabilistic finite automata is , with being the factorization of . To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on...
Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is , with being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages...
Note on universal algorithms for learning theory
We study the universal estimator for the regression problem in learning theory considered by Binev et al. This new approach allows us to improve their results.
Note sur la non-principalité de certaines FAL