The following problem is investigated. Let L be a given finite language, L⊂Ln = ab: 1≤a,b≤n, a≠b. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions.Among others, max c(L) = O(n2/log n) is proved, and languages satisfying c(L) = ¦L¦are characterized
It is well-known that context-free languages defined over a one-letter alpha-bet are regular. This i...
AbstractWe investigate the context-free languages whose complements are also context-free. We call t...
Abstract. We investigate the computational complexity of the nondeterministic finite automaton (NFA)...
The following problem is investigated. Let L be a given finite language, L⊂Ln = ab: 1≤a,b≤n, a≠b. De...
AbstractIn this paper the investigation of the theory of grammatical complexity as started by Bucher...
AbstractIn this note we answer an open question in the theory of grammatical complexity: We show tha...
AbstractIn this paper the investigation of the theory of grammatical complexity as started by Bucher...
AbstractW. Bucher, K. Culik II, H. Maurer and D. Wotschke (Theoretical Computer Science 14(1981), pp...
AbstractIn this note we answer an open question in the theory of grammatical complexity: We show tha...
AbstractThis paper is a contribution to the theory of grammatical complexity, in particular to the f...
Let Ln be the finite language of all n! strings that are permutations of n different symbols (n ≥ 1)...
Abstract. We study context-free grammars whose generated language is bounded (that is, subset of som...
AbstractIt is well known that a context-free language defined over a one-letter alphabet is regular....
It is well known that a context-free language defined over a one-letter alphabet is regular. This im...
AbstractLet Ln be the finite language of all n! strings that are permutations of n different symbols...
It is well-known that context-free languages defined over a one-letter alpha-bet are regular. This i...
AbstractWe investigate the context-free languages whose complements are also context-free. We call t...
Abstract. We investigate the computational complexity of the nondeterministic finite automaton (NFA)...
The following problem is investigated. Let L be a given finite language, L⊂Ln = ab: 1≤a,b≤n, a≠b. De...
AbstractIn this paper the investigation of the theory of grammatical complexity as started by Bucher...
AbstractIn this note we answer an open question in the theory of grammatical complexity: We show tha...
AbstractIn this paper the investigation of the theory of grammatical complexity as started by Bucher...
AbstractW. Bucher, K. Culik II, H. Maurer and D. Wotschke (Theoretical Computer Science 14(1981), pp...
AbstractIn this note we answer an open question in the theory of grammatical complexity: We show tha...
AbstractThis paper is a contribution to the theory of grammatical complexity, in particular to the f...
Let Ln be the finite language of all n! strings that are permutations of n different symbols (n ≥ 1)...
Abstract. We study context-free grammars whose generated language is bounded (that is, subset of som...
AbstractIt is well known that a context-free language defined over a one-letter alphabet is regular....
It is well known that a context-free language defined over a one-letter alphabet is regular. This im...
AbstractLet Ln be the finite language of all n! strings that are permutations of n different symbols...
It is well-known that context-free languages defined over a one-letter alpha-bet are regular. This i...
AbstractWe investigate the context-free languages whose complements are also context-free. We call t...
Abstract. We investigate the computational complexity of the nondeterministic finite automaton (NFA)...
DOI
Add to ORKG