We give in this paper a purely syntactical definitionof input and output types of system ${\cal F}$ . We define thesyntactical data types as input and output types. We show that anytype with positive quantifiers is a syntactical data type and that an inputtype is an output type. We give some restrictions on the∀-elimination rule in order to prove that an output type is aninput type.

We prove in this paper that the types of system ${\cal F}$ inhabited uniquely by λI-terms (the I-types) have apositive quantifier. We give also consequences of this result and someexamples.

We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version of NC-PCA, and prove that a reversible NC-PCA is computation-universal. It is proved by showing that a reversible two-counter machine, which has been known to be universal, can be simulated by a reversible NC-PCA.

Beame, Cook and Hoover were the first to exhibita log-depth, polynomial size circuit family for integerdivision. However, the family was not logspace-uniform.In this paper we describe log-depth, polynomialsize, logspace-uniform, i.e., NC 1 circuit family forinteger division. In particular, by a well-known result this showsthat division is in logspace. We also refine the methodof the paper to show that division is in dlogtime-uniformNC 1.

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.

We study hardness of approximating several minimaximal and maximinimal NP-optimizationproblems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted completedigraph. MINLOP is APX-hard but its unweighted version is polynomial timesolvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization ofMINLOP and requires to find a minimum cardinality maximal acyclic subdigraphof a given digraph, is, however, APX-hard. Using results of Håstad concerning hardness of approximating independence number of a graph we then prove similar results concerning MAX-MIN-VC (respectively, MAX-MIN-FVS) which requires to find a maximum cardinality minimal vertex cover in a given graph (respectively,a maximum cardinality minimal feedback vertex set in a given digraph). We alsoprove APX-hardness of these and several related problems on various degree bounded graphs and digraphs.