Characterization of substitution invariant words coding exchange of three intervals.
Characterizations of certain classes of posets having Gs-lattices of a relatively small size
Characterizations of right dense languages.
Characterizations of stack uniform strict deterministic languages
Characterizations of the Dyck sets
Characterizations of words with many periods.
Characterizing families of cuts that can be represented by axis-parallel rectangles.
Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions....
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The...
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Charge stationnaire d'une file d'attente à rejet. Application au cas indépendant
Charles Babbage (1791-1871) : de l'école algébrique anglaise à la «machine analytique»
Actuellement de plus en plus honoré par les informaticiens à la recherche d'une paternité pour leurs nouvelles machines, Charles Babbage reste un mathématicien peu connu. Il est pourtant à l'origine d'une École Algébrique Anglaise dont les travaux ont su expliciter les caractéristiques des méthodes opératoires et les imposer comme essentielles à la nouvelle algèbre ; parmi les nouveaux «scientists» d'une Angleterre émergeant de sa révolution industrielle dans les années 1830, Babbage, qui est politiquement...
Checking positive definiteness or stability of symmetric interval matrices is NP-hard
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
Chtěli byste být mozkem v baňce?
Circuit lower bounds and linear codes.
Circular splicing and regularity
Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages , called here star languages, which are closed...
Circular splicing and regularity
Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X*, called here star languages, which are closed...
CLAS - A Formal Aid to Data Elements Identification
Classes of Graphs Which Approximate the Complete Euclidean Graph.
Classes of languages proof against regular pumping