The Experts below are selected from a list of 5679 Experts worldwide ranked by ideXlab platform
Asger Tornquist - One of the best experts on this subject based on the ideXlab platform.
-
Definability and almost disjoint families
Advances in Mathematics, 2018Co-Authors: Asger TornquistAbstract:We show that there are no infinite maximal almost disjoint (“mad”) families in Solovay's model, thus solving a long-standing problem posed by A.R.D. Mathias in 1969. We also give a new proof of Mathias' theorem that no analytic infinite almost disjoint family can be maximal, and show more generally that if Martin's Axiom holds at κ<2^(ℵ0), then no κ-Souslin infinite almost disjoint family can be maximal. Finally we show that if ℵ_1^(L[a])<ℵ_1, then there are no Σ^1_2[a] infinite mad families.
-
Definability and almost disjoint families
arXiv: Logic, 2015Co-Authors: Asger TornquistAbstract:We show that there are no infinite maximal almost disjoint ("mad") families in Solovay's model, thus solving a long-standing problem posed by A.D.R. Mathias in 1967. We also give a new proof of Mathias' theorem that no analytic infinite almost disjoint family can be maximal, and show more generally that if Martin's Axiom holds at $\kappa<2^{\aleph_0}$, then no $\kappa$-Souslin infinite almost disjoint family can be maximal. Finally we show that if $\aleph_1^{L[a]}<\aleph_1$, then there are no $\Sigma^1_2[a]$ infinite mad families.
Martin Grohe - One of the best experts on this subject based on the ideXlab platform.
-
fixed parameter tractability Definability and model checking
SIAM Journal on Computing, 2002Co-Authors: Jorg Flum, Martin GroheAbstract:In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every $t\ge 0$ we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy. On a more abstract level, we consider two forms of Definability, called Fagin Definability and slicewise Definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise Definability in finite variable least fixed-point logic, which is reminiscent of the Immerman--Vardi theorem characterizing the class PTIME in terms of Definability in least fixed-point logic.
-
fixed parameter tractability Definability and model checking
arXiv: Computational Complexity, 1999Co-Authors: Jorg Flum, Martin GroheAbstract:In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t >= 0 we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy. On a more abstract level, we consider two forms of Definability, called Fagin Definability and slicewise Definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise Definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi Theorem characterizing the class PTIME in terms of Definability in least fixed-point logic.
Lotfi A Zadeh - One of the best experts on this subject based on the ideXlab platform.
-
fuzzy logic as a basis for a theory of hierarchical Definability thd
International Symposium on Multiple-Valued Logic, 2003Co-Authors: Lotfi A ZadehAbstract:Attempts to formulate mathematically precise definitions of basic concepts such as causality, randomness and probability have a long history. The concept of hierarchical Definability that is outlined in the following suggests that such definitions may not exist. Furthermore, it suggests that existing definitions of many basic concepts, among them those of linearity stability, statistical independence and Pareto-optimality, may be in need of reformulation.
-
toward a theory of hierarchical Definability thd causality is undefinable
International conference on rough sets and current trends in computing, 2002Co-Authors: Lotfi A ZadehAbstract:Attempts to formulate mathematically precise definitions of basic concepts such as causality, randomness and probability have a long history. The concept of hierarchical Definability that is outlined in the following suggests that such definitions may not exist. Furthermore, it suggests that existing definitions of many basic concepts, among them those of linearity stability, statistical independence and Pareto-optimality, may be in need of reformulation. In essence, Definability is concerned with whether and how a concept, X, can be defined in a way that lends itself to mathematical analysis and computation. In mathematics, though not in logic, Definability of mathematical concepts is taken for granted. But as we move further into the age of machine intelligence and automated reasoning, the issue of Definability is certain to grow in importance and visibility, raising basic questions that are not easy to resolve. To be more specific, let X be the concept of, say, a summary, and assume that I am instructing a machine to generate a summary of a given article or a book. To execute my instruction, the machine must be provided with a definition of what is meant by a summary. It is somewhat paradoxical that we have summarization programs that can summarize, albeit in a narrowly prescribed sense, without being able to formulate a general definition of summarization. The same applies to the concepts of causality, randomness and probability. Indeed, it may be argued that these and many other basic concepts cannot be defined within the conceptual framework of classical logic and set theory. The point of departure in our approach to Definability is the assumption that Definability has a hierarchical structure. Furthermore, it is understood that a definition ought to be unambiguous, precise, operational, general and co-extensive with the concept which it defines. In THD, a definition of X is represented as a quadruple (X, L, C, D), where L is the language in which X is defined; C is the context; and D is the definition. The context, C, delimits the class of instances to which D applies, that is, C defines the domain of D. For example, if X is the concept of volume, D may not apply to a croissant or a tree. The language, L, is assumed to be a member of hierarchy represented as (NL, BL, F, F.G, PNL). In this hierarchy, NL is a natural language-a language which is in predominant use as a definition language in social sciences and law; and BL is the binary-logic-based mathematical language used in all existing scientific theories. Informally, a concept, X, is BL-definable if it is a crisp concept, e.g., a prime number, a linear system or a Gaussian distribution. F is a mathematical language based on fuzzy logic and F.G is an extension of F in which variables and relations are allowed to have granular structure. The last member of the hierarchy is PNL-Precisiated Natural Language. PNL is a maximally-expressive language which subsumes BL, F and F.G. In particular, the language of fuzzy if-then rules is a sublanguage of PNL. X is a fuzzy concept if its denotation, D(X), is a fuzzy set in its universe of discourse. A fuzzy concept is associated with a membership function that assigns to each point, u, in the universe of discourse of X, the degree to which u is a member of D(X).
-
causality is undefinable toward a theory of hierarchical Definability
IEEE International Conference on Fuzzy Systems, 2001Co-Authors: Lotfi A ZadehAbstract:Attempts to formulate mathematically precise definitions of basic concepts such as causality, randomness, and probability have a long history. The concept of generalized Definability suggests that such definitions may not exist. Furthermore, it suggests that existing definitions of many basic concepts, among them those of stability, statistical independence and Pareto-optimality, may need to be redefined. The point of departure in our approach to Definability is the assumption that Definability has a hierarchical structure. Furthermore, it is understood that a definition must be unambiguous, precise, operational, general, and coextensive with the concept it defines.
Mohamed Quafafou - One of the best experts on this subject based on the ideXlab platform.
-
a rst a generalization of rough set theory
Information Sciences, 2000Co-Authors: Mohamed QuafafouAbstract:The paper presents a transition from the crisp rough set theory to a fuzzy one, called Alpha Rough Set Theory or, in short, a-RST. All basic concepts or rough set theory are extended, i.e., information system, indiscernibility, dependency, reduction, core, Definability, approximations and boundary. The resulted theory takes into account fuzzy data and allows the approximation of fuzzy concepts. Besides, the control of knowledge granularity is natural in a-RST which is based on a parameterized indiscernibility relation. a-RST is developed to recognize non-deterministic relationships using notions as a-dependency, a-reduct and so forth. On the other hand, we introduce a notion of relative dependency as an alternative of the absolute definibility presented in rough set theory. The extension a-RST leads naturally to the new concept of alpha rough sets which represents sets with fuzzy non-empty boundaries. ” 2000 Elsevier Science Inc. All rights reserved.
Balder Ten Cate - One of the best experts on this subject based on the ideXlab platform.
-
beth Definability in expressive description logics
Journal of Artificial Intelligence Research, 2013Co-Authors: Balder Ten Cate, Enrico Franconi, Inanc SeylanAbstract:The Beth Definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth Definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.
-
beth Definability in expressive description logics
International Joint Conference on Artificial Intelligence, 2011Co-Authors: Balder Ten Cate, Enrico Franconi, Inanc SeylanAbstract:The Beth Definability property, a well-known property from classical logic, is investigated in the context of description logics (DLs): if a general LTBox implicitly defines an L-concept in terms of a given signature, where L is a DL, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in DLs. In this paper a complete classification of Beth Definability is provided for extensions of the basic DL ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic then we show how to compute them in EXPTIME.
-
modal languages for topology expressivity and Definability
arXiv: Logic, 2006Co-Authors: Balder Ten Cate, David Gabelaia, Dmitry SustretovAbstract:In this paper we study the expressive power and Definability for (extended) modal languages interpreted on topological spaces. We provide topological analogues of the van Benthem characterization theorem and the Goldblatt-Thomason Definability theorem in terms of the well established first-order topological language $L_t$.
