Concise description of finite languages

DOI10.1016/0304-3975(81)90044-XzbMath0469.68081MaRDI QIDQ1157179

Karel II Culik, W. Bucher, 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)

Related Items (17)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Amounts of nondeterminism in finite automata
• Size complexity in context-free grammars forms
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• On the size of machines
• Some classifications of context-free languages
• Complexity and unambiguity of context-free grammars and languages

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