Computability by monadic second-order logic

DOI10.1016/j.ipl.2020.106074OpenAlexW3108768550MaRDI QIDQ2656341

Joost Engelfriet

Publication date: 11 March 2021

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

monadic second-order logicrecursively enumerabletheory of computationgraph relation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-model theory -- A personal perspective
• A Kleene characterization of computability
• A regular characterization of graph languages definable in monadic second-order logic
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• MSO definable string transductions and two-way finite-state transducers
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Finite automata and the logic of one-place predicates