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...
Disjunction in modal description logics.
Efficient simulation of synchronous systems by multi-speed systems
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number...
Efficient simulation of synchronous systems by multi-speed systems
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the...
Efficient weighted expressions conversion
J. Hromkovic et al. have given an elegant method to convert a regular expression of size into an -free nondeterministic finite automaton having states and transitions. This method has been implemented efficiently in time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in time.
Efficient weighted expressions conversion
J. Hromkovic et al. have given an elegant method to convert a regular expression of size n into an ε-free nondeterministic finite automaton having O(n) states and O(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(n)) time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in O(nlog2(n)) time.
Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen.
Extensions of -subsets to -subsets - existence versus constructability
Finite alogorithmic procedures and inductive definability.
Finite models and finitely many variables
This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.
Function operators spanning the arithmetical and the polynomial hierarchy
A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory....
Immunity and simplicity for exact counting and other counting classes
Immunity and Simplicity for Exact Counting and Other Counting Classes
Ko [26] and Bruschi [11] independently showed that, in some relativized world, PSPACE (in fact, ⊕P) contains a set that is immune to the polynomial hierarchy (PH). In this paper, we study and settle the question of relativized separations with immunity for PH and the counting classes PP, , and ⊕P in all possible pairwise combinations. Our main result is that there is an oracle A relative to which contains a set that is immune BPP⊕P. In particular, this set is immune to PHA and to ⊕PA. Strengthening...
Impulse noise removal based on new hybrid conjugate gradient approach
Image denoising is a fundamental problem in image processing operations. In this paper, we present a two-phase scheme for the impulse noise removal. In the first phase, noise candidates are identified by the adaptive median filter (AMF) for salt-and-pepper noise. In the second phase, a new hybrid conjugate gradient method is used to minimize an edge-preserving regularization functional. The second phase of our algorithm inherits advantages of both Dai-Yuan (DY) and Hager-Zhang (HZ) conjugate gradient...
Intuitionistic Frege systems are polynomially equivalent.
Komplexität von Algorithmen mit Anwendung auf die Analysis.
Natural limitations of decisions procedures for arithmetic with bounded quantifiers.