Search results for "transitive"
showing 10 items of 98 documents
ON THE STAR HEIGHT OF RATIONAL LANGUAGES
1994
Two problems concerning the star height of a rational language are investigated: the star height one problem and the relationships between the unambiguity of an expression and its star height. For this purpose we consider the class of factorial, transitive and rational (FTR) languages. From the algebraic point of view a FTR language is the set of factors of a rational submonoid M. Two subclasses of FTR languages are introduced: renewal languages, corresponding to the case of M finitely generated, and unambiguous renewal languages, corresponding to the case of M finitely generated and free. We prove that a FTR language has star height one if and only if it is renewal. This gives a simple de…
A comparison of compatible, finite, and inductive graph properties
1993
Abstract In the theory of hyperedge-replacement grammars and languages, one encounters three types of graph properties that play an important role in proving decidability and structural results. The three types are called compatible, finite, and inductive graph properties. All three of them cover graph properties that are well-behaved with respect to certain operations on hypergraphs. In this paper, we show that the three notions are essentially equivalent. Consequently, three lines of investigation in the theory of hyperedge replacement - so far separated - merge into one.
P-matrix completions under weak symmetry assumptions
2000
An n-by-n matrix is called a Π-matrix if it is one of (weakly) sign-symmetric, positive, nonnegative P-matrix, (weakly) sign-symmetric, positive, nonnegative P0,1-matrix, or Fischer, or Koteljanskii matrix. In this paper, we are interested in Π-matrix completion problems, that is, when a partial Π-matrix has a Π-matrix completion. Here, we prove that a combinatorially symmetric partial positive P-matrix has a positive P-matrix completion if the graph of its specified entries is an n-cycle. In general, a combinatorially symmetric partial Π-matrix has a Π-matrix completion if the graph of its specified entries is a 1-chordal graph. This condition is also necessary for (weakly) sign-symmetric …
M-valued Measure of Roughness for Approximation of L-fuzzy Sets and Its Topological Interpretation
2015
We develop a scheme allowing to measure the “quality” of rough approximation of fuzzy sets. This scheme is based on what we call “an approximation quadruple” \((L,M,\varphi ,\psi )\) where L and M are cl-monoids (in particular, \(L=M=[0,1]\)) and \(\psi : L \rightarrow M\) and \(\varphi : M \rightarrow L\) are satisfying certain conditions mappings (in particular, they can be the identity mappings). In the result of realization of this scheme we get measures of upper and lower rough approximation for L-fuzzy subsets of a set equipped with a reflexive transitive M-fuzzy relation R. In case the relation R is also symmetric, these measures coincide and we call their value by the measure of rou…
A dual of 4-regular graph forG × C2n
2003
Abstract A graph is said h-decomposable if its edge-set is decomposable into edge-disjoint hamiltonian cycles. Jha [3] conjectured that if G is a non-bipartite h-decomposable graph on even number of vertices, then G × K2 is h-decomposable. We use the notion of dual graph defined in [4], we prove that if G = Q1,2 ⊕ C3,4 is a 4-regular non-bipartite h-decomposable graph and the dual graphs relative to Q1,2 and C3,4 are connected then G × K 2 and G × C 2n are h-decomposable (where C 2n is an even cycle).
Some dissenting views on the transitivity of individual preference
1990
(1) The transitivity property is not a necessary condition for the rationality of all individual preference relations. (2) A weakened definition of the transitivity is not necessarily relevant. (3) The non-transitivity of fuzzy preference relations is not inconsistent with a fuzzy total preorder structure on the set of alternatives.
Some local properties defining $\mathcal T_0$-groups and related classes of groups
2016
We call $G$ a $\operatorname{Hall}_{\mathcal X}$-group if there exists a normal nilpotent subgroup $N$ of $G$ for which $G/N'$ is an ${\mathcal X}$-group. We call $G$ a ${\mathcal T}_0$-group provided $G/\Phi(G)$ is a ${\mathcal T}$-group, that is, one in which normality is a transitive relation. We present several new local classes of groups which locally define $\operatorname{Hall}_{\mathcal X}$-groups and ${\mathcal T}_0$-groups where ${\mathcal X}\in\{ {\mathcal T},\mathcal {PT},\mathcal {PST}\}$; the classes $\mathcal {PT}$ and $\mathcal {PST}$ denote, respectively, the classes of groups in which permutability and S-permutability are transitive relations.
On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards
2007
The guarded fragment of first-order logic, GF, enjoys the finite model property, so the satisfiability and the finite satisfiability problems coincide. We are concerned with two extensions of the two-variable guarded fragment that do not possess the finite model property, namely, GF2 with equivalence and GF2 with transitive guards. We prove that in both cases every finitely satisfiable formula has a model of at most double exponential size w.r.t. its length. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NEXPTIME-upper bound on the complexity of the fini…
Counting in the Two Variable Guarded Logic with Transitivity
2005
We show that the extension of the two-variable guarded fragment with transitive guards (GF+TG) by functionality statements is undecidable. This gives immediately undecidability of the extension of GF+TG by counting quantifiers. The result is optimal, since both the three-variable fragment of the guarded fragment with counting quantifiers and the two-variable guarded fragment with transitivity are undecidable. We also show that the extension of GF+TG with functionality, where functional predicate letters appear in guards only, is decidable and of the same complexity as GF+TG. This fragment captures many expressive modal and description logics.
Ranking fuzzy interval numbers in the setting of random sets – further results
1999
Abstract We present some new properties of several fuzzy order relations, defined on the set of fuzzy numbers, from among those introduced in [S. Chanas, M. Delgado, J.L. Verdegay, M.A. Vila, Information Sciences 69 (1993) 201–217]. The main result is proving that four from among the relations considered in [S. Chanas, M. Delgado, J.L. Verdegay, M.A. Vila, Information Sciences 69 (1993) 201–217] are strongly transitive (s-transitive).