A note on negative tagging for least fixed-point formulae
A Note on Negative Tagging for Least Fixed-Point Formulae
Proof systems with sequents of the form U ⊢ Φ for proving validity of a propositional modal μ-calculus formula Φ over a set U of states in a given model usually handle fixed-point formulae through unfolding, thus allowing such formulae to reappear in a proof. Tagging is a technique originated by Winskel for annotating fixed-point formulae with information about the proof states at which these are unfolded. This information is used later in the proof to avoid unnecessary unfolding, without...
A note on NSPACE () and substitution
A note on outerplanarity of product graphs
A note on read- times branching programs
A note on rectilinearity and angular resolution.
A note on rewriting theory for uniqueness of iteration.
A note on r-extensible prefix codes.
A note on separating the relativized polynomial time hierarchy by immune sets
A note on the asymptotic and computational complexity of graph distinguishability.
A note on the asymptotic behavior of the heights in -trees for large.
A note on the computational complexity of computing the edge rotation distance between graphs
A note on the computational complexity of hierarchical overlapping clustering
In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set by a -ultrametric on and by a Robinson dissimilarity measure on is investigared. It is shown that the underlying decision problems are NP-complete.
A note on the Glauber dynamics for sampling independent sets.
A note on the hardness results for the labeled perfect matching problems in bipartite graphs
In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected...
A note on the iteration of infinite matrices
A note on the minimality problem in indefinite summation of rational functions.
A note on the minimalization of tree-automata
A note on the number of squares in a partial word with one hole
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form uv where u is compatible with v, and consequently, such square is...
A note on the paper “disjunctive languages and compatible orders”