1 L 2 ) ? min{REGcc(L 1 ) + LINcc(L 2 ), LINcc(L 1 ) + REGcc(L 2 )} ,
1 L 2 ) ? min{SREGcc(L 1 ) + SLINcc(L 2 ), SLINcc(L 1 ) + SREGcc(L 2 )} ,
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. ,
A Note on a Problem in the Theory of Grammatical Complexity, Theoretical Computer Science, vol.14, pp.337-344, 1981. ,
Context-free Complexity of Finite Languages, Theoretical Computer Science, vol.28, pp.277-285, 1984. ,
Concise Description of Finite Languages, Theoretical Computer Science, vol.14, pp.227-246, 1981. ,
Minimal cover-automata for finite languages, International Workshop on Implementing Automata (WIA'98), vol.1660, pp.43-56, 1998. ,
Minimal cover-automata for finite languages, Theoretical Computer Science, vol.267, issue.1-2, pp.3-16, 2001. ,
Complexity and minimality of context-Free grammars and languages, Mathematical Foundations of Computer Science (MFCS) 1977, vol.53, pp.263-271, 1977. ,
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
Production Complexity of Some Operations on ContextFree Languages, Workshop on Descriptional Complexity of Formal Systems (DCFS), vol.7386, pp.141-154, 2012. ,
Compressibility of Finite Languages by Grammars, Descriptional Complexity of Formal Systems (DCFS) 2015, vol.9118, pp.93-104, 2015. ,
On the compressibility of finite languages and formal proofs, Information and Computation, vol.259, pp.191-213, 2018. ,
On a Classification of Context-Free Languages, Kybernetika, vol.3, issue.1, p.29, 1967. ,
Some Classifications of Context-Free Languages, Information and Control, vol.14, issue.2, pp.152-179, 1969. ,
Complexity and unambiguity of context-free grammars and languages, Information and Control, vol.18, issue.5, pp.502-519, 1971. ,
On the Size of Context-free Grammars, Kybernetika, vol.8, issue.3, pp.213-218, 1972. ,
Applying Tree Languages in Proof Theory, Language and Automata Theory and Applications (LATA) 2012, vol.7183, pp.301-312, 2012. ,
Introducing Quantified Cuts in Logic with Equality, Automated Reasoning-7th International Joint Conference, IJCAR, vol.8562, pp.240-254, 2014. ,
Algorithmic introduction of quantified cuts, Theoretical Computer Science, vol.549, pp.1-16, 2014. ,
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. ,
Twelve Problems in Proof Complexity, Third International Computer Science Symposium in Russia (CSR), vol.5010, pp.13-27, 2008. ,
On the Context-Free Production Complexity of Finite Languages, Discrete Applied Mathematics, vol.18, issue.3, pp.293-304, 1987. ,