On the public citation graph
Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width
0 signed · 52 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/malq.19600060105openalex-snapshot
Weak Second‐Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1007/3-540-18771-5_41openalex-snapshot
May we introduce to you: Hyperedge replacement
inferredcites →https://doi.org/10.1007/3-540-62559-3_20openalex-snapshot
Definability equals recognizability of partial 3-trees
inferredcites →https://doi.org/10.1007/3-540-63165-8_233openalex-snapshot
Recognizability equals definability for partial k-paths
inferredcites →https://doi.org/10.1007/bf01692060openalex-snapshot
Graph expressions and graph rewritings
inferredcites →https://doi.org/10.1016/0095-8956(84)90013-3openalex-snapshot
Graph minors. III. Planar tree-width
inferredcites →https://doi.org/10.1016/0168-0072(90)90027-yopenalex-snapshot
The monadic second-order logic of graphs IV: definability properties of equational graphs11This work has been supported by the “Programme de Recherches Coordonnées: Mathématiques et Informatique”, and by the ESPRIT-Basic Research Action contract No. 3299, “Computing by graph transformations”.
inferredcites →https://doi.org/10.1016/0304-3975(91)90387-hopenalex-snapshot
The monadic second-order logic of graphs V: on closing the gap between definability and recognizability
inferredcites →https://doi.org/10.1016/0304-3975(94)90268-2openalex-snapshot
Monadic second-order definable graph transductions: a survey
inferredcites →https://doi.org/10.1016/0890-5401(90)90043-hopenalex-snapshot
The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
inferredcites →https://doi.org/10.1016/s0019-9958(67)90353-1openalex-snapshot
Algebraic automata and context-free sets
inferredcites →https://doi.org/10.1016/s0022-0000(70)80041-1openalex-snapshot
Tree acceptors and some of their applications
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.2001.3077openalex-snapshot
Rationality in Algebras with a Series Operation
inferred← citeshttps://doi.org/10.1006/inco.2002.3130openalex-snapshot
A Monadic Second-Order Definition of the Structure of Convex Hypergraphs
inferred← citeshttps://doi.org/10.1007/11538363_20openalex-snapshot
Towards a Characterization of Order-Invariant Queries over Tame Structures
inferred← citeshttps://doi.org/10.1007/3-540-44618-4_31openalex-snapshot
Pomsets for Local Trace Languages
inferred← citeshttps://doi.org/10.1007/3-540-44634-6_9openalex-snapshot
Deciding Clique-Width for Graphs of Bounded Tree-Width
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_55openalex-snapshot
Infinite Series-Parallel Posets: Logic and Languages
inferred← citeshttps://doi.org/10.1007/3-540-46011-x_17openalex-snapshot
Recognizable Sets of N-Free Pomsets Are Monadically Axiomatizable
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_8openalex-snapshot
Algebraic Recognizability of Languages
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_1openalex-snapshot
Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
inferred← citeshttps://doi.org/10.1007/978-3-540-72951-8_3openalex-snapshot
Treewidth: Structure and Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-30891-8_12openalex-snapshot
Fixed-Parameter Tractability of Treewidth and Pathwidth
inferred← citeshttps://doi.org/10.1007/978-3-642-32621-9_6openalex-snapshot
On the Expressive Power of Logics with Invariant Uses of Arithmetic Predicates
inferred← citeshttps://doi.org/10.1007/978-3-662-52921-8_13openalex-snapshot
Causality in Bounded Petri Nets is MSO Definable
inferred← citeshttps://doi.org/10.1007/bfb0055812openalex-snapshot
Facial circuits of planar graphs and context-free languages
inferred← citeshttps://doi.org/10.1007/s004530010019openalex-snapshot
Linear-Time Algorithms for Partial \boldmath k -Tree Complements
inferred← citeshttps://doi.org/10.1016/j.ejc.2017.06.025openalex-snapshot
Definability equals recognizability for k -outerplanar graphs and l -chordal partial k -trees
inferred← citeshttps://doi.org/10.1016/j.endm.2015.06.076openalex-snapshot
Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality
inferred← citeshttps://doi.org/10.1016/j.ic.2005.11.006openalex-snapshot
Recognizability, hypergraph operations, and logical types
inferred← citeshttps://doi.org/10.1016/j.jal.2005.08.004openalex-snapshot
The monadic second-order logic of graphs XV: On a conjecture by D. Seese
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.04.005openalex-snapshot
Measuring what matters: A hybrid approach to dynamic programming with treewidth
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.03.018openalex-snapshot
The recognizability of sets of graphs is a robust property
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.006openalex-snapshot
Trees, grids, and MSO decidability: From graphs to matroids
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00229-8openalex-snapshot
Uniform and nonuniform recognizability
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00370-5openalex-snapshot
Towards a language theory for infinite N-free pomsets
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00306-5openalex-snapshot
The monadic second-order logic of graphs XI: Hierarchical decompositions of connected graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80116-7openalex-snapshot
The algorithmic theory of treewidth
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)00191-4openalex-snapshot
GETGRATS A summary of scientific results (with annotated bibliography)
inferred← citeshttps://doi.org/10.1145/2933575.2934508openalex-snapshot
Definability equals recognizability for graphs of bounded treewidth
inferred← citeshttps://doi.org/10.1145/2933575.2934517openalex-snapshot
Order Invariance on Decomposable Structures
inferred← citeshttps://doi.org/10.1145/371316.371512openalex-snapshot
MSO definable string transductions and two-way finite-state transducers
inferred← citeshttps://doi.org/10.2168/lmcs-6(2:2)2010openalex-snapshot
On the Monadic Second-Order Transduction Hierarchy
inferred← citeshttps://doi.org/10.2178/jsl/1231082307openalex-snapshot
Towards a characterization of order-invariant queries over tame graphs
inferred← citeshttps://doi.org/10.26686/wgtn.17067797openalex-snapshot
Chordality in Matroids: In Search of the Converse to Hliněný's Theorem
inferred← citeshttps://doi.org/10.26686/wgtn.17067797.v1openalex-snapshot
Chordality in Matroids: In Search of the Converse to Hliněný's Theorem
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2008.1353openalex-snapshot
Order-Invariant MSO is Stronger than Counting MSO in the Finite
inferred← citeshttps://doi.org/10.48550/arxiv.1503.01604openalex-snapshot
MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree $k$-Outerplanar Graphs
inferred← citeshttps://doi.org/10.7146/brics.v9i44.21759openalex-snapshot
Higher Dimensional Automata
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.