A semi-conditional grammar, introduced by Gheorghe Păun, is a form of regulated rewriting system where each rule consists of a context-free core rule along with two strings , . The rule is applicable if (the positive condition) occurs as a substring of the current sentential form, but (the negative condition) does not. The maximum lengths i, j of the positive or negative conditional strings, respectively, give a natural measure of descriptional complexity, known as the degree of such grammars. Employing several normal form results on phrase-structure grammars as derived in particular by Viliam Geffert, we improve on previously obtained results by reducing the number of nonterminals of semi-conditional grammars of a given degree while maintaining computational completeness of the said mechanisms.
DassowJ., A remark on limited 0L systems, Journal of Information Processing and Cybernetics EIK24(6) (1988), 287–291.
2.
DassowJ.PăunG., Regulated Rewriting in Formal Language Theory, EATCS Monographs in Theoretical Computer Science, Vol. 18, Springer, 1989.
3.
FernauH., Membership for 1-limited ET0L languages is not decidable, Journal of Information Processing and Cybernetics EIK30(4) (1994), 191–211.
4.
FernauH., Membership for k-limited ET0L languages is not decidable, Journal of Automata, Languages and Combinatorics1 (1996), 243–245.
5.
FernauH., Unconditional transfer in regulated rewriting, Acta Informatica34 (1997), 837–857. doi:10.1007/s002360050108.
6.
FernauH., Parsimonious computational completeness, in: Developments in Language Theory – 25th International Conference, DLT, MoreiraN.ReisR., eds, LNCS, Vol. 12811, Springer, 2021, pp. 12–26. doi:10.1007/978-3-030-81508-0_2.
7.
FernauH.FreundR.OswaldM.ReinhardtK., Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars, Journal of Automata, Languages and Combinatorics12(1/2) (2007), 117–138.
8.
FernauH.KuppusamyL.OladeleR.O., New nonterminal complexity results for semi-conditional grammars, in: Sailing Routes in the World of Computation, 14th Conference on Computability in Europe, CiE, ManeaF.MillerR.G.NowotkaD., eds, LNCS, Vol. 10936, Springer, 2018, pp. 172–182. doi:10.1007/978-3-319-94418-0_18.
FernauH.KuppusamyL.RamanI., Counting simple rules in semi-conditional grammars is not simple, in: Twenty Years of Theoretical and Practical Synergies, 20th Conference on Computability in Europe, CiE, L.L. Patey and E. Pimentel, eds, LNCS, Vol. 14773, Springer, 2024, pp. 192–204. doi:10.1007/978-3-031-64309-5_16.
11.
GeffertV., A representation of recursively enumerable languages by two homomorphisms and a quotient, Theoretical Computer Science62 (1988), 235–249. doi:10.1016/0304-3975(88)90068-0.
12.
GeffertV., Normal forms for phrase-structure grammars, RAIRO Informatique théorique et Applications/Theoretical Informatics and Applications25 (1991), 473–498. doi:10.1051/ita/1991250504731.
13.
GruskaJ., On a classification of context-free languages, Kybernetika3(1) (1967), 22–29.
14.
GruskaJ., A few remarks on the index of context-free grammars and languages, Information and Control (now Information and Computation)19 (1971), 216–223. doi:10.1016/S0019-9958(71)90095-7.
15.
MasopustT., Formal Models: Regulation and Reduction, PhD thesis, Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic, 2007.
16.
MasopustT., A note on the generative power of some simple variants of context-free grammars regulated by context conditions, in: Language and Automata Theory and Applications, LATA, DediuA.-H.IonescuA.-M.Martín-VideC., eds, LNCS, Vol. 5457, Springer, 2009, pp. 554–565. doi:10.1007/978-3-642-00982-2_47.
17.
MasopustT.MedunaA., Descriptional complexity of semi-conditional grammars, Information Processing Letters104(1) (2007), 29–31. doi:10.1016/j.ipl.2007.05.002.
18.
MayerO., Some restrictive devices for context-free languages, Information and Control (now Information and Computation)20 (1972), 69–92. doi:10.1016/S0019-9958(72)90287-2.
19.
MedunaA.GopalaratnamM., On semi-conditional grammars with productions having either forbidding or permitting conditions, Acta Cybernetica11 (1994), 309–323.
20.
OkuboF., A note on the descriptional complexity of semi-conditional grammars, Information Processing Letters110(1) (2009), 36–40. doi:10.1016/j.ipl.2009.10.002.
21.
PăunG., A variant of random context grammars: Semi-conditional grammars, Theoretical Computer Science41 (1985), 1–17. doi:10.1016/0304-3975(85)90056-8.
22.
VaszilG., On the descriptional complexity of some rewriting mechanisms regulated by context conditions, Theoretical Computer Science330 (2005), 361–373. doi:10.1016/j.tcs.2004.06.032.
