Some properties of cellular automata with equicontinuity points
Some properties of decomposition ordering, a simplification ordering to prove termination of rewriting systems
Some Properties of the Combinational Measure of Complexity of Binary Words
Some Provably Hard Crossing Number Problems.
Some remarks on multihead automata
Some remarks on the extension of a finite set of stochastic automata
Some remarks on the stability problem for linear space automata and semicontinuity of cut point languages
Some results on cellular automata
We want to discuss some properties of one-dimensional, radius 1, CUCAs (we denote by CUCA a Computationally Universal Cellular Automaton; see later on for the definitions). In particular, on one hand we want to keep small the number of states (the first example of «small» CUCA is due to Smith III [13]; it requires 18 states); on the other hand we are interested into automata, possibly requiring a high number of states, whose transition law is «as simple as possible»; e.g. totalistic automata (the...
Some results on complexity of μ-calculus evaluation in the black-box model
We consider μ-calculus formulas in a normal form: after a prefix of fixed-point quantifiers follows a quantifier-free expression. We are interested in the problem of evaluating (model checking) such formulas in a powerset lattice. We assume that the quantifier-free part of the expression can be any monotone function given by a black-box – we may only ask for its value for given arguments. As a first result we prove that when the lattice is fixed, the problem becomes polynomial (the assumption about...
Some results on C-varieties
In an earlier paper, the second author generalized Eilenberg's variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman's theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form (a1a2...ak)+, where a1,...,ak are distinct letters. Next,...
Some results on finite maximal codes
Some results on the dot-depth hierarchy.
Some results on -varieties
In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form , where are distinct letters. Next, we generalize the notions...
Some theorems on labelled bracketings used in transformational grammars
Somme des chiffres et transcendance
SOUR graphs for efficient completion.
Sous-monoides et codes avec des mots infinis.
Space classes, intersection of languages and bounded erasing homomorphisms
Space-efficient parallel merging
Special Issue: AAMP VIII AND ISCAMI 2011