. Lincc, 1 L 2 ) ? min{REGcc(L 1 ) + LINcc(L 2 ), LINcc(L 1 ) + REGcc(L 2 )}

. Slincc, 1 L 2 ) ? min{SREGcc(L 1 ) + SLINcc(L 2 ), SLINcc(L 1 ) + SREGcc(L 2 )}

}. .. {sreg, R. ;. Eades, P. Rose, and G. , A Lower-bound for the Number of Productions Required for a Certain Class of Languages, Then clearly we have Xcc(L 1 ) = m and Xcc(L 2 ) = n. Thus, References 1. Alspach, vol.6, pp.109-115, 1983.

W. Bucher, A Note on a Problem in the Theory of Grammatical Complexity, Theoretical Computer Science, vol.14, pp.337-344, 1981.

W. Bucher, H. A. Maurer, and K. C. Ii, Context-free Complexity of Finite Languages, Theoretical Computer Science, vol.28, pp.277-285, 1984.

W. Bucher, H. A. Maurer, K. C. Ii, and D. Wotschke, Concise Description of Finite Languages, Theoretical Computer Science, vol.14, pp.227-246, 1981.

C. Câmpeanu, N. Santean, and S. Yu, Minimal cover-automata for finite languages, International Workshop on Implementing Automata (WIA'98), vol.1660, pp.43-56, 1998.

C. Câmpeanu, N. Santean, and S. Yu, Minimal cover-automata for finite languages, Theoretical Computer Science, vol.267, issue.1-2, pp.3-16, 2001.

A. Cern´ycern´y, Complexity and minimality of context-Free grammars and languages, Mathematical Foundations of Computer Science (MFCS) 1977, vol.53, pp.263-271, 1977.

J. Dassow, Descriptional Complexity and Operations-Two Non-classical Cases, Workshop on Descriptional Complexity of Formal Systems (DCFS), vol.10316, pp.33-44, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01657004

J. Dassow and R. Harbich, Production Complexity of Some Operations on ContextFree Languages, Workshop on Descriptional Complexity of Formal Systems (DCFS), vol.7386, pp.141-154, 2012.

S. Eberhard and S. Hetzl, Compressibility of Finite Languages by Grammars, Descriptional Complexity of Formal Systems (DCFS) 2015, vol.9118, pp.93-104, 2015.

S. Eberhard and S. Hetzl, On the compressibility of finite languages and formal proofs, Information and Computation, vol.259, pp.191-213, 2018.

J. Gruska, On a Classification of Context-Free Languages, Kybernetika, vol.3, issue.1, p.29, 1967.

J. Gruska, Some Classifications of Context-Free Languages, Information and Control, vol.14, issue.2, pp.152-179, 1969.

J. Gruska, Complexity and unambiguity of context-free grammars and languages, Information and Control, vol.18, issue.5, pp.502-519, 1971.

J. Gruska, On the Size of Context-free Grammars, Kybernetika, vol.8, issue.3, pp.213-218, 1972.

S. Hetzl, Applying Tree Languages in Proof Theory, Language and Automata Theory and Applications (LATA) 2012, vol.7183, pp.301-312, 2012.

S. Hetzl, A. Leitsch, G. Reis, J. Tapolczai, and D. Weller, Introducing Quantified Cuts in Logic with Equality, Automated Reasoning-7th International Joint Conference, IJCAR, vol.8562, pp.240-254, 2014.

S. Hetzl, A. Leitsch, G. Reis, and D. Weller, Algorithmic introduction of quantified cuts, Theoretical Computer Science, vol.549, pp.1-16, 2014.

S. Hetzl, A. Leitsch, and D. Weller, Towards Algorithmic Cut-Introduction. In: Logic for Programming, Artificial Intelligence and Reasoning (LPAR-18), Lecture Notes in Computer Science, vol.7180, pp.228-242, 2012.

P. Pudlák, E. A. Hirsch, A. A. Razborov, and A. L. Semenov, Twelve Problems in Proof Complexity, Third International Computer Science Symposium in Russia (CSR), vol.5010, pp.13-27, 2008.

Z. Tuza, On the Context-Free Production Complexity of Finite Languages, Discrete Applied Mathematics, vol.18, issue.3, pp.293-304, 1987.