The number of automata, boundedly determined functions and hereditary properties of automata
The Number of Non-Isomorphic Hamiltonian Circuits in an -Dimensional Cube
The passing of a rational expression to a nondeterministic finite automaton. (Passage d'une expression rationnelle à un automate fini non-déterministe.)
The problems of complexity of almost context-free languages [Abstract of thesis]
The pseudovariety is hyperdecidable
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 relation of two patterns with comparable languages patterns
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 separability of formal languages
The strong independence of substitution and homomorphic replication
The structure of index sets and reduced indexed grammars
The topological structure of adherences of regular languages
The topologies of sofic subshifts have computable Pierce invariants
The unsolvability of the emptiness problem of the two deterministic finite transducer mappings
The varieties of languages corresponding to the varieties of finite band monoids.
The -calculus alternation-depth hierarchy is strict on binary trees
The μ-calculus alternation-depth hierarchy is strict on binary trees
In this paper we give a simple proof that the alternation-depth hierarchy of the μ-calculus for binary trees is strict. The witnesses for this strictness are the automata that determine whether there is a winning strategy for the parity game played on a tree.
Théorie des magmoïdes
Théorie des magmoïdes (I)
Theory of computing systems