On the public citation graph

Local normal forms for first-order logic with applications to games and automata

https://doi.org/10.1007/bfb0028580
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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1995.1100openalex-snapshot
On Monadic NP vs Monadic co-NP
inferredcites →https://doi.org/10.1006/jcss.1995.1025openalex-snapshot
Computing with First-Order Logic
inferredcites →https://doi.org/10.1007/3-540-28788-4openalex-snapshot
Finite Model Theory
inferredcites →https://doi.org/10.1007/3-540-54233-7_154openalex-snapshot
On logics, tilings, and automata
inferredcites →https://doi.org/10.1007/3-540-57787-4_11openalex-snapshot
A computational model for generic graph functions
inferredcites →https://doi.org/10.1007/3-540-60084-1_92openalex-snapshot
Graph Connectivity, Monadic NP and built-in relations of moderate degree
inferredcites →https://doi.org/10.1007/3-540-62222-5_42openalex-snapshot
Local properties of query languages
inferredcites →https://doi.org/10.1007/bfb0023863openalex-snapshot
The Ehrenfeucht-Fraïssé games for transitive closure
inferredcites →https://doi.org/10.1007/bfb0028560openalex-snapshot
Unary quantifiers, transitive closure, and relations of large degree
inferredcites →https://doi.org/10.1007/bfb0030586openalex-snapshot
Automata theory on trees and partial orders
inferredcites →https://doi.org/10.1016/0022-0000(82)90011-3openalex-snapshot
Upper and lower bounds for first order expressibility
inferredcites →https://doi.org/10.1016/0022-0000(89)90019-6openalex-snapshot
Descriptive characterizations of computational complexity
inferredcites →https://doi.org/10.1016/0168-0072(95)00030-5openalex-snapshot
On winning Ehrenfeucht games and monadic NP
inferredcites →https://doi.org/10.1016/0304-3975(92)90148-9openalex-snapshot
The monadic second-order logic of graphs VII: graphs as relational structures
inferredcites →https://doi.org/10.1016/0304-3975(92)90149-aopenalex-snapshot
Capturing complexity classes by fragments of second-order logic
inferredcites →https://doi.org/10.1016/0304-3975(95)00083-6openalex-snapshot
The monadic second-order logic of graphs X: Linear orderings
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/b978-0-7204-2233-7.50020-4openalex-snapshot
MODEL-THEORETIC METHODS IN THE STUDY OF ELEMENTARY LOGIC
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1016/s0049-237x(08)71879-2openalex-snapshot
On Local and Non-Local Properties
inferredcites →https://doi.org/10.1016/s0304-3975(96)00015-1openalex-snapshot
On winning strategies in Ehrenfeucht-Fraïssé games
inferredcites →https://doi.org/10.1016/s0304-3975(99)00223-6openalex-snapshot
Local properties of query languages
inferredcites →https://doi.org/10.1017/s1446788700020681openalex-snapshot
Second-order Ehrenfeucht games and the deciability of the second-order theory of an equivalence relation
inferredcites →https://doi.org/10.1090/dimacs/029/02openalex-snapshot
Elements of an automata theory over partial orders
inferredcites →https://doi.org/10.1090/dimacs/031/01openalex-snapshot
Easier ways to win logical games
inferredcites →https://doi.org/10.1109/lics.1989.39160openalex-snapshot
Fixpoint extensions of first-order logic and datalog-like languages
inferredcites →https://doi.org/10.1109/lics.1997.614948openalex-snapshot
On the forms of locality over finite models
inferredcites →https://doi.org/10.1109/psct.1987.10319271openalex-snapshot
Expressibility as a Complexity Measure: Results and Directions
inferredcites →https://doi.org/10.1145/800070.802186openalex-snapshot
The complexity of relational query languages (Extended Abstract)
inferredcites →https://doi.org/10.2307/2272133openalex-snapshot
On Moschovakis closure ordinals
inferredcites →https://doi.org/10.2307/2273560openalex-snapshot
Some useful preservation theorems
inferredcites →https://doi.org/10.2307/2274958openalex-snapshot
Reachability is harder for directed than for undirected finite graphs
inferredcites →https://doi.org/10.4064/fm-49-2-129-141openalex-snapshot
An application of games to the completeness problem for formalized theories

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/10703163_2openalex-snapshot
Descriptive Complexity, Lower Bounds and Linear Time
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_18openalex-snapshot
Logics Capturing Local Properties
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_2openalex-snapshot
Counting and Locality over Finite Structures A Survey
inferred← citeshttps://doi.org/10.1007/978-3-030-45231-5_6openalex-snapshot
Parameterized Synthesis for Fragments of First-Order Logic Over Data Words
inferred← citeshttps://doi.org/10.1007/978-3-319-41528-4_9openalex-snapshot
Synthesis of Self-Stabilising and Byzantine-Resilient Distributed Systems
inferred← citeshttps://doi.org/10.1007/978-3-540-30124-0_16openalex-snapshot
Game-Based Notions of Locality Over Finite Models
inferred← citeshttps://doi.org/10.1007/978-3-662-07003-1_4openalex-snapshot
Locality and Winning Games
inferred← citeshttps://doi.org/10.1016/j.apal.2007.11.012openalex-snapshot
Game-based notions of locality over finite models
inferred← citeshttps://doi.org/10.1016/j.entcs.2005.04.041openalex-snapshot
Locality of Queries and Transformations
inferred← citeshttps://doi.org/10.1016/j.ic.2013.01.003openalex-snapshot
Subshifts as models for MSO logic
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.01.005openalex-snapshot
A logical approach to locality in pictures languages
inferred← citeshttps://doi.org/10.1109/lics.1999.782626openalex-snapshot
Logics with counting, auxiliary relations, and lower bounds for invariant queries
inferred← citeshttps://doi.org/10.1109/lics.2005.32openalex-snapshot
On Locality and Uniform Reduction
inferred← citeshttps://doi.org/10.1145/1993806.1993829openalex-snapshot
Locally checkable proofs
inferred← citeshttps://doi.org/10.1145/2603088.2603093openalex-snapshot
Logic for communicating automata with parameterized topology
inferred← citeshttps://doi.org/10.1145/2933575.2934571openalex-snapshot
Hanf normal form for first-order logic with unary counting quantifiers
inferred← citeshttps://doi.org/10.1145/371282.371388openalex-snapshot
Logics capturing local properties
inferred← citeshttps://doi.org/10.4086/toc.2016.v012a019openalex-snapshot
inferred← citeshttps://doi.org/10.70675/f51892c5z9581z4412zbe27zaa702a9e56dfopenalex-snapshot
Synthesis for parameterized systems
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.