Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Combined complexity classes for finite functions
Complexité de l'arboricité linéaire d'un graphe
Complexity of some natural problems in automatic structures.
Complexity of the decidability of one class of formulas in quantifier-free set theory with a set-union operator.
Complexity of the decidability of the unquantified set theory with a rank operator.
Computational complexity in algebraic systems.
Computational complexity of a statistical theoremhood testing procedure for propositional calculus with pseudo-random inputs
Computing the Rabin index of a parity automaton
Computing the Rabin Index of a Parity Automaton
The Rabin index of a rational language of infinite words given by a parity automaton with n states is computable in time O(n2c) where c is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This new acceptance condition can also be...
Craig's interpolation theorem, in computation theory
Si espongono alcuni risultati, provati dall’Autore negli articoli citati nella bibliografia, a proposito della complessità del teorema d’interpolazione di Craig: con ciò si intende la relazione tra la lunghezza (cioè il numero di simboli) della formula e la lunghezza di e , ove è un’implicazione valida, e è un interpolante, come esibito dal teorema di interpolazione stesso. Si intende altresì sottolineare la rilevanza dello studio della complessità dell’interpolazione per far luce su alcuni...