|
S2S (mathematics)
In mathematics, S2S is the monadic second order theory with two successors. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969. Basic properties The first order objects of S2S are finite binary strings. The second order objects are arbitrary sets (or unary predicates) of finite binary strings. S2S has functions ''s''→''s''0 and ''s''→''s''1 on strings, and predicate ''s''∈''S'' (equivalently, ''S''(''s'')) meaning string ''s'' belongs to set ''S''. Some properties and conventions: * By default, lowercase letters refer to first order objects, and uppercase to second order objects. * The inclusion of sets makes S2S second order, with "monadic" indicating absence of ''k''-ary predicate variables for ''k''>1. * Concatenation of strings ''s'' and ''t'' is denoted by ''st'', and is ''not'' generally available in S2S, not even ''s''→0''s''. The prefix relation be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monadic Second-order Logic
In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages. Second-order logic allows quantification over predicates. However, MSO is the fragment in which second-order quantification is limited to monadic predicates (predicates having a single argument). This is often described as quantification over "sets" because monadic predicates are equivalent in expressive power to sets (the set of elements for which the predicate is true). Variants Monadic second-order logic comes in two variants. In the variant considered over str ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pathwidth
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition is a sequence of subsets of vertices of such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets,. and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness (one less than the maximum clique size in an interval supergraph of ), vertex separation number, or node searching number. Pathwidth and path-decompositions are closely analogous to treewidth and tree decompositions. They play a key role in the theory of graph minors: the families of graphs that are closed under graph minors and do not include all forests may be characterized as having bounded pathwidth, and the "vortices ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Beta-model
In model theory, a mathematical discipline, a β-model (from the French "bon ordre", well-ordering) is a model which is correct about statements of the form "''X'' is well-ordered". The term was introduced by Mostowski (1959)K. R. Apt, W. Marek,Second-order Arithmetic and Some Related Topics (1973), p. 181 as a strengthening of the notion of ω-model. In contrast to the notation for set-theoretic properties named by ordinals, such as \xi-indescribability, the letter β here is only denotational. In set theory It's a consequence of Shoenfield's absoluteness theorem that the constructible universe L is a β-model. In analysis β-models appear in the study of the reverse mathematics Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in cont ... of subsystems of second-order arithmetic. In this ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed-point Logic
In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query languages, in particular to Datalog. Least fixed-point logic was first studied systematically by Yiannis N. Moschovakis in 1974, and it was introduced to computer scientists in 1979, when Alfred Aho and Jeffrey Ullman suggested fixed-point logic as an expressive database query language. Partial fixed-point logic For a relational signature ''X'', FO FP''X'') is the set of formulas formed from ''X'' using first-order connectives and predicates, second-order variables as well as a partial fixed point operator \operatorname used to form formulas of the form operatorname_ \varphivec, where P is a second-order variable, \vec a tuple of first-order variables, \vec a tuple of terms and the lengths of \vec and \vec coincide with the arity of P ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Large Countable Ordinal
In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations (see ordinal analysis). However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not (for reasons somewhat analogous to the unsolvability of the halting problem); various more-concrete ways of defining ordinals that definitely have notations are available. Since there are only countably many notations, all ordinals with notations are exhausted well below the first uncountable ordinal ω1; their supremum is called ''Church–Kleene'' ω1 or ω1CK (not to be confused with the first uncountable ordinal, ω1), described below. Ordinal numbers below ω1CK are the recursive ordinals (see below). Countable ordinals larger than this may ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Constructible Universe
In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory (that is, of Zermelo–Fraenkel set theory with the axiom of choice excluded), and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result. What is can be thought of as being built in "stages" resembling the constr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reverse Mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones. The reverse mathematics program was foreshadowed by results in set theory such as the classical theorem that the axiom of choice and Zorn's lemma are equivalent over ZF set theory. The goal of reverse mathematics, however, is to study possible axioms of ordinary theorems of mathematics rather than possible axioms for set theory. Reverse mathematics is usually carried out using subsystems of second-order arithmetic,Simpson, Stephen G. (2009), Subsystems of second-order arithmetic, Perspectives in Logic (2nd ed.), Cambridge University Press, doi:10.1017/CBO9780511581007, ISBN 978 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
ω-automaton
In automata theory, a branch of theoretical computer science, an ω-automaton (or stream automaton) is a variation of finite automata that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states. ω-automata are useful for specifying behavior of systems that are not expected to terminate, such as hardware, operating systems and control systems. For such systems, one may want to specify a property such as "for every request, an acknowledge eventually follows", or its negation "there is a request that is not followed by an acknowledge". The former is a property of infinite words: one cannot say of a finite sequence that it satisfies this property. Classes of ω-automata include the Büchi automata, Rabin automata, Streett automata, parity automata and Muller automata, each deterministic or non-deterministic. These classes of ω-automata differ only in terms of a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Omega-regular Language
The ω-regular languages are a class of ω-languages that generalize the definition of regular languages to infinite words. Formal definition An ω-language ''L'' is ω-regular if it has the form * ''A''ω where ''A'' is a regular language not containing the empty string * ''AB'', the concatenation of a regular language ''A'' and an ω-regular language ''B'' (Note that ''BA'' is ''not'' well-defined) * ''A'' ∪ ''B'' where ''A'' and ''B'' are ω-regular languages (this rule can only be applied finitely many times) The elements of ''A''ω are obtained by concatenating words from ''A'' infinitely many times. Note that if ''A'' is regular, ''A''ω is not necessarily ω-regular, since ''A'' could be for example , the set containing only the empty string, in which case ''A''ω=''A'', which is not an ω-language and therefore not an ω-regular language. It is a straightforward consequence of the definition that the ω-regular languages are precisely the ω-languages of the form ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars. Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows: * The empty language Ø is a regular language. * For each ''a'' ∈ Σ (''a'' belongs to Σ), the singleton language is a regular language. * If ''A'' is a regular language, ''A''* ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kripke Semantics
Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André Joyal. It was first conceived for modal logics, and later adapted to intuitionistic logic and other non-classical systems. The development of Kripke semantics was a breakthrough in the theory of non-classical logics, because the model theory of such logics was almost non-existent before Kripke (algebraic semantics existed, but were considered 'syntax in disguise'). Semantics of modal logic The language of propositional modal logic consists of a countable set, countably infinite set of propositional variables, a set of truth-functional Logical connective, connectives (in this article \to and \neg), and the modal operator \Box ("necessarily"). The modal operator \Diamond ("possibly") is (classically) the duality (mathematics)#Duality in log ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weakly Compact Cardinal
In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by ; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory. (Tarski originally called them "not strongly incompact" cardinals.) Formally, a cardinal κ is defined to be weakly compact if it is uncountable and for every function ''f'': º 2 → there is a set of cardinality κ that is homogeneous for ''f''. In this context, º 2 means the set of 2-element subsets of κ, and a subset ''S'' of κ is homogeneous for ''f'' if and only if either all of 'S''sup>2 maps to 0 or all of it maps to 1. The name "weakly compact" refers to the fact that if a cardinal is weakly compact then a certain related infinitary language satisfies a version of the compactness theorem; see below. Every weakly compact cardinal is a reflecting cardinal, and is also a limit of reflecting cardinals. This means also that weakly compact ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
