An extension of context-free grammars with one-sided context specifications

Aizikowitz, 2011, LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata, vol. 6651, 345 Autebert, 1997, Context-free languages and pushdown automata, 111 Barash, 2013, Recursive descent parsing for grammars with contexts, 10 Barash, 2013, Programming language specification by a grammar with contexts, 51 M. Barash, A. Okhotin, Linear grammars with one-sided contexts and their automaton representation, in: LATIN 2014: Theoretical Informatics, Montevideo, Uruguay, 31 March–4 April 2014, in: Lect. Notes Comput. Sci., vol. 8392, pp. 190–201. Chomsky, 1959, On certain formal properties of grammars, Inf. Control, 2, 137, 10.1016/S0019-9958(59)90362-6 Čulík, 1973, LR-regular grammars—an extension of LR(k) grammars, J. Comput. Syst. Sci., 7, 66, 10.1016/S0022-0000(73)80050-9 Ésik, 2007, Boolean fuzzy sets, Int. J. Found. Comput. Sci., 18, 1197, 10.1142/S0129054107005248 Ford, 2004, Parsing expression grammars: a recognition-based syntactic foundation, 111 Ginsburg, 1962, Two families of languages related to ALGOL, J. ACM, 9, 350, 10.1145/321127.321132 Jarząbek, 1975, LL-regular grammars, Inf. Process. Lett., 4, 31, 10.1016/0020-0190(75)90009-5 Jeż, 2008, Conjunctive grammars can generate non-regular unary languages, Int. J. Found. Comput. Sci., 19, 597, 10.1142/S012905410800584X Jeż, 2010, Conjunctive grammars over a unary alphabet: undecidability and unbounded growth, Theory Comput. Syst., 46, 27, 10.1007/s00224-008-9139-5 Joshi, 1975, Tree adjunct grammars, J. Comput. Syst. Sci., 10, 136, 10.1016/S0022-0000(75)80019-5 Joshi, 1991, The convergence of mildly context-sensitive grammatical formalisms Kasami, 1969, A syntax-analysis procedure for unambiguous context-free grammars, J. ACM, 16, 423, 10.1145/321526.321531 Kountouriotis, 2009, Well-founded semantics for Boolean grammars, Inf. Comput., 207, 945, 10.1016/j.ic.2009.05.002 Kowalski, 1979 Okhotin, 2001, Conjunctive grammars, J. Autom. Lang. Comb., 6, 519 Okhotin, 2002, Conjunctive grammars and systems of language equations, Program. Comput. Softw., 28, 243, 10.1023/A:1020213411126 Okhotin, 2004, Boolean grammars, Inf. Comput., 194, 19, 10.1016/j.ic.2004.03.006 Okhotin, 2005, The dual of concatenation, Theor. Comput. Sci., 345, 425, 10.1016/j.tcs.2005.07.019 Okhotin, 2006, Generalized LR parsing algorithm for Boolean grammars, Int. J. Found. Comput. Sci., 17, 629, 10.1142/S0129054106004029 Okhotin, 2007, Recursive descent parsing for Boolean grammars, Acta Inform., 44, 167, 10.1007/s00236-007-0045-0 Okhotin, 2008, Unambiguous Boolean grammars, Inf. Comput., 206, 1234, 10.1016/j.ic.2008.03.023 Okhotin, 2013, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Comput. Sci. Rev., 9, 27, 10.1016/j.cosrev.2013.06.001 Okhotin, 2014, Parsing by matrix multiplication generalized to Boolean grammars, Theor. Comput. Sci., 516, 101, 10.1016/j.tcs.2013.09.011 Okhotin, 2010, Conjunctive grammars with restricted disjunction, Theor. Comput. Sci., 411, 2559, 10.1016/j.tcs.2010.03.015 Okhotin, 2012, On the expressive power of univariate equations over sets of natural numbers, Inf. Comput., 212, 1, 10.1016/j.ic.2012.01.004 Parr, 2011, LL(⁎): the foundation of the ANTLR parser generator, 425 F.C.N. Pereira, D.H.D. Warren, Parsing as deduction, in: 21st Annual Meeting of the Association for Computational Linguistics, ACL 1983, Cambridge, Massachusetts, USA, 15–17 June 1983, pp. 137–144. Rounds, 1988, LFP: A logic for linguistic descriptions and an analysis of its complexity, Comput. Linguist., 14, 1 Seki, 1991, On multiple context-free grammars, Theor. Comput. Sci., 88, 191, 10.1016/0304-3975(91)90374-B Sikkel, 1997 Valiant, 1975, General context-free recognition in less than cubic time, J. Comput. Syst. Sci., 10, 308, 10.1016/S0022-0000(75)80046-8 K. Vijay-Shanker, D.J. Weir, A.K. Joshi, Characterizing structural descriptions produced by various grammatical formalisms, in: ACL 1987, pp. 104–111.