A descriptive characterisation of linear languages

DOI10.1007/s10849-006-9016-zzbMath1105.68064OpenAlexW2079403768MaRDI QIDQ851197

Tore Langholm

Publication date: 17 November 2006

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10849-006-9016-z

zbMATH Keywords

descriptive complexitylinear languagesGreibach normal form

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items

Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A descriptive characterisation of even linear languages
• Existential second-order logic over strings
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• On a family of linear grammars
• Matrix Equations and Normal Forms for Context-Free Grammars