Learnability and definability in trees and similar structures

DOI10.1007/S00224-003-1112-8zbMath1062.03031OpenAlexW1996805091MaRDI QIDQ705070

Martin Grohe, György Turán

Publication date: 25 January 2005

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-003-1112-8

zbMATH Keywords

first-order logicmonadic second-order logicdefinabilitylearnabilityfinite automata over treeslogical predicate structureprobably approximately correct (PAC) learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Automata and formal grammars in connection with logical questions (03D05) Model theory of finite structures (03C13)

Related Items (6)

Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Containment of Monadic Datalog Programs via Bounded Clique-Width ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On low rank-width colorings

This page was built for publication: Learnability and definability in trees and similar structures