On curves and surfaces in illumination geometry.
On decidability of skeletal sets [Abstract of thesis]
On deciding some equivalences for concurrent processes
On defining multiple-valued logics for knowledge-based systems communication.
Multiple-valued logics are useful for dealing with uncertainty and imprecision in Knowledge-Based Systems. Different problems can require different logics. Then we need mechanisms to translate the information exchanged between two problems with different logics. In this paper, we introduce the logical foundations of such logics and the communication mechanisms that preserve some deductive properties. We also describe a tool to assist users in the declaration of logics and their communication mechanisms....
On differentiation functions, structure functions, and related languages of context-free grammars
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the equivalence...
On differentiation functions, structure functions, and related languages of context-free grammars
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or k-narrow) iff its differentiation function is bounded by a constant (by k). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of ...
On directable automata
On distributive fixed-point expressions
On Distributive Fixed-Point Expressions
For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size . Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
On DOS languages and DOS mappings.
On dot-depth two
On effective presentations of formal concept lattices.
On effective speed-up and long proofs of trivial theorems in formal theories
On equality sets of morphisms in topological free monoids
On equivalence of two tests for codes.
On existentially first-order definable languages and their relation to NP
On Existentially First-Order Definable Languages and Their Relation to NP
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.
On external-memory planar depth first search.
On extremal properties of the Fibonacci word
We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.
On extremum-searching approximate probabilistic algorithms