{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:46Z","timestamp":1759638586554},"reference-count":25,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1051\/ita\/2015004","type":"journal-article","created":{"date-parts":[[2015,7,8]],"date-time":"2015-07-08T02:38:53Z","timestamp":1436323133000},"page":"153-178","source":"Crossref","is-referenced-by-count":6,"title":["Linear grammars with one-sided contexts and their automaton representation"],"prefix":"10.1051","volume":"49","author":[{"given":"Mikhail","family":"Barash","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2015,7,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"T. Aizikowitz and M. Kaminski, LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata.Comput. Sci. Russia(CSR 2011, St. Petersburg, Russia, 14\u201318 June 2011). Vol. 6651 ofLect. Notes Comput. Sci.(2011) 345\u2013358.","DOI":"10.1007\/978-3-642-20712-9_27"},{"key":"R2","unstructured":"M. Barash, Recursive descent parsing for grammars with contexts.SOFSEM 2013 student research forum \u0160pindler\u016fv Ml\u00fdn, Czech Republic, 26-31 January, 2013. Local Proceedings II, 10\u201321, Institute of Computer Science AS CR (2013)."},{"key":"R3","unstructured":"M. Barash, Programming language specification by a grammar with contexts. InFifth Workshop on Non-Classical Models of Automata and Applications, NCMA 2013, Ume\u00e5, Sweden, 13\u201314 August, 2013, edited by S. Bensch, F. Drewes, R. Freund, F. Otto. books@ocg.at 294, \u00d6sterreichische Computer Gesellschaft (2013) 51\u201367. http:\/\/users.utu.fi\/mikbar\/kieli\/"},{"key":"R4","unstructured":"Barash M. and Okhotin A., An extension of context-free grammars with one-sided context specifications.Inform. Comput.237(2014) 268\u2013293."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Barash and A. Okhotin, Linear grammars with one-sided contexts and their automaton representation.LATIN 2014: Theoretical Informatics, Montevideo,Uruguay, 31 March\u20134 April 2014. In vol. 8392, Lect. Notes Comput. Sci. (2014) 190\u2013201.","DOI":"10.1007\/978-3-642-54423-1_17"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Birman A. and Ullman J.D., Parsing algorithms with backtrack.Inform. Control23(1973) 1\u201334.","DOI":"10.1016\/S0019-9958(73)90851-6"},{"key":"R7","unstructured":"\u010cul\u00edk K., Gruska J. and Salomaa A., Systolic trellis automata I.Int. J. Comput. Math.15(1984) 195\u2013212."},{"key":"R8","unstructured":"\u010cul\u00edk K., Gruska J. and Salomaa A., Systolic trellis automata II.Int. J. Comput. Math.16(1984) 3\u201322."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Dyer C., One-way bounded cellular automata.Inform. Control44(1980) 261\u2013281.","DOI":"10.1016\/S0019-9958(80)90164-3"},{"key":"R10","unstructured":"Ibarra O.H. and Kim S.M., Characterizations and computational complexity of systolic trellis automata.Theoret. Comput. Sci.29(1984) 123\u2013153."},{"key":"R11","unstructured":"Ibarra O.H., Kim S.M. and Moran S., Sequential machine characterizations of trellis and cellular automata and applications.SIAM J. Comput.14(1985) 426\u2013447."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Je\u017c A., Conjunctive grammars can generate non-regular unary languages.Int. J. Found. Comput. Sci.19(2008) 597\u2013615.","DOI":"10.1142\/S012905410800584X"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Je\u017c A. and Okhotin A., Conjunctive grammars over a unary alphabet: undecidability and unbounded growth.Theory Comput. Syst.46(2010) 27\u201358.","DOI":"10.1007\/s00224-008-9139-5"},{"key":"R14","unstructured":"R. Kowalski, Logic for Problem Solving. North-Holland, Amsterdam (1979)."},{"key":"R15","unstructured":"Okhotin A., Conjunctive grammars.J. Autom. Lang. Comb.6(2001) 519\u2013535."},{"key":"R16","unstructured":"Okhotin A., On the closure properties of linear conjunctive languages.Theoret. Comput. Sci.299(2003) 663\u2013685."},{"key":"R17","unstructured":"Okhotin A., On the equivalence of linear conjunctive grammars to trellis automata.RAIRO: ITA38(2004) 69\u201388."},{"key":"R18","unstructured":"Okhotin A., Homomorphisms preserving linear conjunctive languages.J. Autom. Lang. Comb.13(2008) 299\u2013305."},{"key":"R19","unstructured":"Okhotin A., Conjunctive and Boolean grammars: the true general case of the context-free grammars.Comput. Sci. Rev.9(2013) 27\u201359."},{"key":"R20","unstructured":"Okhotin A., Improved normal form for grammars with one-sided contexts.Theoret. Comput. Sci.588(2015) 52\u201372."},{"key":"R21","unstructured":"H. Rogers, Jr., Theory of Recursive Functions and Effective Computability. McGraw-Hill (1967)."},{"key":"R22","unstructured":"Rounds W.C., LFP: A logic for linguistic descriptions and an analysis of its complexity.Comput. Linguistics14(1988) 1\u20139."},{"key":"R23","unstructured":"Terrier V., On real-time one-way cellular array.Theoret. Comput. Sci.141(1995) 331\u2013335."},{"key":"R24","unstructured":"I. T\u00f6rm\u00e4. Personal communication. February 2013."},{"key":"R25","unstructured":"Yu S., A property of real-time trellis automata.Discrete Appl. Math.15(1986) 117\u2013119."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015004\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T22:34:39Z","timestamp":1566945279000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":25,"journal-issue":{"issue":"2"},"alternative-id":["ita140050"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2015004","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}