The PCP theorem
The problems of complexity of almost context-free languages [Abstract of thesis]
The pseudovariety is hyperdecidable
The pseudovariety of semigroups of triangular matrices over a finite field
We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.
The pseudovariety of semigroups of triangular matrices over a finite field
We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.
The range of non-linear natural polynomials cannot be context-free
Suppose that some polynomial with rational coefficients takes only natural values at natural numbers, i. e., . We show that the base- representation of is a context-free language if and only if is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
The reduction of binary trees by means of an input-restricted deque
The relation of two patterns with comparable languages patterns
The role of rudimentary relations in complexity theory
The second machine class 2, an encyclopedic view on the parallel computation thesis
The second-order monadic theory of the free inverse monoid is undecidable. (La théorie monadique du second ordre du monoïde inversif libre est indécidable.)
The semigroup of a strongly connected automaton.
The separability of formal languages
The server specification for information retrieval of bibliographic data.
The shape of a category up to directed homotopy.
The size of triangulations supporting a given link.
The star clustering algorithm for static and dynamic information organization.
The strong independence of substitution and homomorphic replication
The Structure and complexity of interactive zero-knowledge proofs
The structure of index sets and reduced indexed grammars