Codes et motifs
Codes infinitaires et automates non-ambigus
Codes, languages and MOL schemes
Cohesiveness in promise problems
Promise problems have been introduced in 1985 by S. Even e.a. as a generalization of decision problems. Using a very general approach we study solvability and unsolvability conditions for promise problems of set and language families. We show, that cores of unsolvability are completely determined by partitions of cohesive sets. We prove the existence of cores in unsolvable promise problems assuming certain closure properties for the given set family. Connections to immune sets and complexity cores...
Combinatorial interpretations of a generalization of the Genocchi numbers.
Comparing Complexity Functions of a Language and Its Extendable Part
Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Comparison of basic language generating devices (non-deterministic systems)
Compatibility relations on codes and free monoids
A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....
Complément à l'étude des suites de Thue-Morse généralisées
Complete characterization of context-sensitive languages
Complete subgraphs of bipartite graphs and applications to trace languages
Complexity arguments in algebraic language theory
Complexity of boundary graph languages
Complexity of E0L structural equivalence
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Composed figures of pixels and inverse monoid. (Figures composées de pixels et monoïde inversif.)
Compositional representation of rational functions