The independence of certain operations on semiAFLs
The insertion encoding of permutations.
The intersection problem for alphabetic vector monoids
The intrinsic complexity of parametric elimination methods.
The inverse semigroup of a sumordered semiring.
The Ising transducer
The laterality problem for non-erasing Turing machines on is completely solved
The lattice of subautomata of an automaton: A survey.
The lattice of varieties of fibered automata
The class of all fibered automata is a variety of two-sorted algebras. This paper provides a full description of the lattice of varieties of fibred automata.
The limiting common distribution of two leaf heights in a random binary tree
The local catenativity of DOL-sequences in free commutative monoids is decidable in the binary case
The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
The NP-completeness of automorphic colorings
Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
The number of automata, boundedly determined functions and hereditary properties of automata
The Number of Non-Isomorphic Hamiltonian Circuits in an -Dimensional Cube
The observational predicate calculus and complexity of computations (Preliminary communication)
The onset of necrosis in a 3D cellular automaton model of EMT6 multi-cellular spheroids
A 3-dimensional (3D) extension to a previously reported scaled 2-dimensional Cellular Automaton (CA) model of avascular multi-cellular spheroid growth is presented and analysed for the EMT6/Ro cell line. The model outputs are found to compare favourably with reported experimentally obtained data for in vitro spheroids of the same cell line. Necrosis (unprogrammed central cell death) is observed to be delayed when compared with the experimental data. Furthermore, it is found that necrosis arises...
The Orthogonal Convex Skull Problem.
The partial inverse minimum cut problem with L1-norm is strongly NP-hard
The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional bound...
The passing of a rational expression to a nondeterministic finite automaton. (Passage d'une expression rationnelle à un automate fini non-déterministe.)