Concise description of finite languages

DOI10.1016/0304-3975(81)90044-XMaRDI QIDQ1157179zbMATH OpenFDO

Authors W. Bucher, Karel II Culik, Detlef Wotschke, Hermann Maurer

Publication date 1981

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

grammatical complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3488626 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3499244 (Why is no real title available?)
• scientific article; zbMATH DE number 3562527 (Why is no real title available?)
• scientific article; zbMATH DE number 3592979 (Why is no real title available?)
• scientific article; zbMATH DE number 3640909 (Why is no real title available?)
• scientific article; zbMATH DE number 3254902 (Why is no real title available?)
• scientific article; zbMATH DE number 3324737 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A note on the succinctness of descriptions of deterministic languages
• Amounts of nondeterminism in finite automata
• Complexity and unambiguity of context-free grammars and languages
• On the size of machines
• Size complexity in context-free grammars forms
• Some classifications of context-free languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages

Cited in

(18)

• On the cover complexity of finite languages
• Asymptotical behaviour of some non-uniform measures
• Simple splicing systems
• Nonuniform complexity and the randomness of certain complete languages
• On the complexity of the smallest grammar problem over fixed alphabets
• ON THE NUMBER OF ACTIVE SYMBOLS IN LINDENMAYER SYSTEMS
• Pareto grammars
• Generating all permutations by context-free grammars in Chomsky normal form
• Generating all permutations by context-free grammars in Greibach normal form
• scientific article; zbMATH DE number 97565 (Why is no real title available?)
• Context-free complexity of finite languages
• On the context-free production complexity of finite languages
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• A lower-bound for the number of productions required for a certain class of languages
• On the compressibility of finite languages and formal proofs
• Nonuniform complexity classes specified by lower and upper bounds
• A note on a problem in the theory of grammatical complexity
• On strongly context-free languages

This page was built for publication: Concise description of finite languages

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