Defining Long Words Succinctly in FO and MSO
Copyright policy )Defining Long Words Succinctly in FO and MSO
Abstract We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.
- Tampere University Finland
- TAMPEREEN KORKEAKOULUSAATIO SR Finland
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, 213 Electronic, automation and communications engineering, electronics, monadic second-order logic, Model theory of finite structures, logic on words, succinctness, Mathematics - Logic, 111, 113, 004, Logic in Computer Science (cs.LO), Descriptive complexity and finite models, FOS: Mathematics, F.4.1, Logic (math.LO)
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, 213 Electronic, automation and communications engineering, electronics, monadic second-order logic, Model theory of finite structures, logic on words, succinctness, Mathematics - Logic, 111, 113, 004, Logic in Computer Science (cs.LO), Descriptive complexity and finite models, FOS: Mathematics, F.4.1, Logic (math.LO)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!