Characteristic formulae for timed automata
Characteristic Formulae for Timed Automata
This paper offers characteristic formula constructions in the real-time logic Lν for several behavioural relations between (states of) timed automata. The behavioural relations studied in this work are timed (bi)similarity, timed ready simulation, faster-than bisimilarity and timed trace inclusion. The characteristic formulae delivered by our constructions have size which is linear in that of the timed automaton they logically describe. This also applies to the characteristic formula for...
Characteristic sets of a system of equivalence relations
Characterization of rational and algebraic power series
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...