Strict LT₂ : regular :: local : recognizable

DOI10.1007/BFB0052167MaRDI QIDQ4370243zbMATH OpenFDO

Authors James Rogers

Publication date 2 April 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0052167

zbMATH Keywords

context-free grammarsdefinability in a restricted logical languagedescriptive complexitylocal setsrecognizable setstrees

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45)

Recommendations

• Local definitizability of \(T^{[\ast]}T\) and \(TT^{[\ast]}\)
• Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 3967078
• A characterization of local regular languages
• From regular to strictly locally testable languages
• From regular to strictly locally testable languages
• Strict \({\varPi^1_1}\)-reflection in bounded arithmetic
• scientific article; zbMATH DE number 4001459
• Local reflection, definable elements and 1-provability
• Recognizability equals definability for partial k-paths

Cited in

(4)

• Computing languages by (bounded) local sets
• Some classes of sets of structures definable without quantifiers
• Relativized adjacency
• The expressivity of autosegmental grammars

This page was built for publication: Strict \(\text{LT}_2\) : regular :: local : recognizable

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