Search results for " logic"
showing 10 items of 1720 documents
On the Power of Tree-Walking Automata
2000
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …
Absolutely Convergent Extensions of Nonclosable Positive Linear Functionals
2010
The existence of extensions of a positive linear functional ω defined on a dense *-subalgebra \({\mathfrak{A}_0}\) of a topological *-algebra \({\mathfrak{A}}\), satisfying certain regularity conditions, is examined. The main interest is focused on the case where ω is nonclosable and sufficient conditions for the existence of an absolutely convergent extension of ω are given.
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
Counting with Probabilistic and Ultrametric Finite Automata
2014
We investigate the state complexity of probabilistic and ultrametric finite automata for the problem of counting, i.e. recognizing the one-word unary language \(C_n=\left\{ 1^n \right\} \). We also review the known results for other types of automata.
Single-valued extension property at the points of the approximate point spectrum
2003
Abstract A localized version of the single-valued extension property is studied at the points which are not limit points of the approximate point spectrum, as well as of the surjectivity spectrum. In particular, we shall characterize the single-valued extension property at a point λ o ∈ C in the case that λoI−T is of Kato type. From this characterizations we shall deduce several results on cluster points of some distinguished parts of the spectrum.
Operators Which Do Not Have the Single Valued Extension Property
2000
Abstract In this paper we shall consider the relationships between a local version of the single valued extension property of a bounded operator T ∈ L ( X ) on a Banach space X and some quantities associated with T which play an important role in Fredholm theory. In particular, we shall consider some conditions for which T does not have the single valued extension property at a point λ o ∈ C .
On a Category of Extensional Fuzzy Rough Approximation L-valued Spaces
2016
We establish extensionality of some upper and lower fuzzy rough approximation operators on an L-valued set. Taking as the ground basic properties of these operators, we introduce the concept of an (extensional) fuzzy rough approximation L-valued space. We apply fuzzy functions satisfying certain continuity-type conditions, as morphisms between such spaces, and in the result obtain a category \(\mathcal{FRA}{} \mathbf{SPA}(L)\) of fuzzy rough approximation L-valued spaces. An interpretation of fuzzy rough approximation L-valued spaces as L-fuzzy (di)topological spaces is presented and applied for constructing examples in category \(\mathcal{FRA}{} \mathbf{SPA}(L)\).
Common fixed points for discontinuous mappings in fuzzy metric spaces
2008
In this paper we prove some common fixed point theorems for fuzzy contraction respect to a mapping, which satisfies a condition of weak compatibility. We deduce also fixed point results for fuzzy contractive mappings in the sense of Gregori and Sapena.
Locality of order-invariant first-order formulas
2000
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.
Two-Variable First-Order Logic with Equivalence Closure
2012
We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NExpTime, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NExpTime-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite sa…