On the width of regular classes of finite structures

DOI10.1007/978-3-030-29436-6_2MaRDI QIDQ2305404zbMATH OpenOpenAlexFDO

Authors Alexsander Andrade de Melo, Mateus de Oliveira Oliveira

Publication date 10 March 2020

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

zbMATH Keywords

automatic structuresfirst order logicwidth measures

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Recommendations

• On the widths of finite distributive lattices
• Asymptotic classes of finite structures
• Countability of widths of algebraic reducibility structures for models in some classes
• scientific article; zbMATH DE number 729864
• scientific article; zbMATH DE number 3057872
• On linear widths of classes \(H^\omega\)
• scientific article; zbMATH DE number 459357
• On the widths of finite groups
• scientific article; zbMATH DE number 5520457
• Ordered asymptotic classes of finite structures

Cites work

• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• 10.1162/jmlr.2003.3.4-5.679
• A Myhill-Nerode theorem for automata with advice
• Advice Automatic Structures and Uniformly Automatic Classes
• Algorithmic Meta-theorems
• Algorithmic meta theorems for sparse graph classes
• Automatic groups: A guided tour
• Automatic presentations of structures
• Decision Problems of Finite Automata Design and Related Arithmetics
• Graph classes with and without powers of bounded clique-width
• Graphs of relational structures: restricted types
• Linear time solvable optimization problems on graphs of bounded clique-width
• Mathematical Logic
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• On the Width of Ordered Binary Decision Diagrams
• SOFSEM 2004: Theory and Practice of Computer Science
• Symbolic topological sorting with OBDDs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The structure of the models of decidable monadic theories of graphs
• The treewidth and pathwidth of hypercubes
• Three lectures on automatic structures
• Trees, grids, and MSO decidability: from graphs to matroids
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(3)

• Second-order finite automata
• On the size of classes with weak membership properties
• Widths of function classes on sets with tree-like structure

This page was built for publication: On the width of regular classes of finite structures

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