A descriptive characterisation of linear languages

DOI10.1007/S10849-006-9016-ZMaRDI QIDQ851197zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A descriptive characterisation of even linear languages
• scientific article; zbMATH DE number 1346364
• scientific article; zbMATH DE number 2079028
• Linear Context Free Languages
• Linear indexed languages

Cites work

• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2079028 (Why is no real title available?)
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• A descriptive characterisation of even linear languages
• Existential second-order logic over strings
• Matrix Equations and Normal Forms for Context-Free Grammars
• On a family of linear grammars

Cited in

(7)

• Grammatical Inference: Algorithms and Applications
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• scientific article; zbMATH DE number 95311 (Why is no real title available?)
• Properties of language classes between linear and context-free
• A descriptive characterisation of even linear languages
• Middle quotients of linear languages
• Linear Context Free Languages

This page was built for publication: A descriptive characterisation of linear languages

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