Defining long words succinctly in FO and MSO

DOI10.1007/978-3-031-08740-0_11MaRDI QIDQ2104260zbMATH OpenOpenAlexFDO

Authors Lauri Hella, Miikka Vilander

Publication date 7 December 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2202.10180

zbMATH Keywords

logic on wordsmonadic second-order logicsuccinctness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Constructing antidictionaries of long texts in output-sensitive space
• Computing longest common extensions in partial words
• scientific article; zbMATH DE number 1408345
• On long words avoiding Zimin patterns
• On Long Words Avoiding Zimin Patterns
• Longest Common Extensions in Partial Words
• On semiconcise words
• Partitioning Subwords of Long Words

Cites work

• Defining long words succinctly in FO and MSO
• Descriptive complexity of finite structures: Saving the quantifier rank
• Elements of finite model theory.
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Large finite structures with few \(L^k\)-types
• Logical complexity of graphs: a survey
• Regular expressions: new results and open problems
• Some Remarks on Finite Löwenheim‐Skolem Theorems
• Succinct definitions in the first order theory of graphs
• The Complexity of Translating Logic to Finite Automata

Cited in

(6)

• Defining long words succinctly in FO and MSO
• Defining long words succinctly in FO and MSO
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO

This page was built for publication: Defining long words succinctly in FO and MSO

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104260)