{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T10:25:13Z","timestamp":1648635913912},"reference-count":25,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2014,2,10]],"date-time":"2014-02-10T00:00:00Z","timestamp":1391990400000},"content-version":"vor","delay-in-days":40,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2014,1,8]]},"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>In the literature various types of restarting automata have been studied that are based\n          on contextual rewriting. A word <jats:italic>w<\/jats:italic> is accepted by such an automaton if,\n          starting from the initial configuration that corresponds to input <jats:italic>w<\/jats:italic>, the\n          word <jats:italic>w<\/jats:italic> is reduced to the empty word by a finite number of applications of\n          these contextual rewritings. This approach is reminiscent of the notion of McNaughton\n          families of languages. Here we put the aforementioned types of restarting automata into\n          the context of McNaughton families of languages, relating the classes of languages\n          accepted by these automata in particular to the class GCSL of growing context-sensitive\n          languages and to the class CRL of Church\u2013Rosser languages.<\/jats:p>","DOI":"10.1051\/ita\/2014001","type":"journal-article","created":{"date-parts":[[2014,2,10]],"date-time":"2014-02-10T08:43:23Z","timestamp":1392021803000},"page":"61-84","source":"Crossref","is-referenced-by-count":3,"title":["On the classes of languages accepted by limited context\n          restarting automata"],"prefix":"10.1051","volume":"48","author":[{"given":"Friedrich","family":"Otto","sequence":"first","affiliation":[]},{"given":"Peter","family":"\u010cerno","sequence":"additional","affiliation":[]},{"given":"Franti\u0161ek","family":"Mr\u00e1z","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2014,2,10]]},"reference":[{"key":"R1","unstructured":"S. Basovn\u00edk, Learning restricted restarting\n          automata using genetic algorithm. Master\u2019s thesis, Charles University. Faculty of\n          Mathematics and Physics, Prague, Czech (2010)."},{"key":"R2","unstructured":"S. Basovn\u00edk and F. Mr\u00e1z, Learning limited context\n          restarting automata by genetic algorithms, in Theorietag, edited by J.\n          Dassow and B. Truthe. Otto-von-Guericke-Universit\u00e4t, Magdeburg (2011) 1\u20134."},{"key":"R3","doi-asserted-by":"crossref","first-page":"1581","DOI":"10.1016\/S0304-3975(02)00070-1","volume":"290","author":"Beaudry","year":"2003","journal-title":"Theoret. Comput. Sci."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"R.V. Book and F. Otto, String-Rewriting Systems.\n          Springer, New York (1993).","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"R5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01969548","volume":"6","author":"B\u00fcchi","year":"1964","journal-title":"Arch. f. Math. Logik Grundlagenf."},{"key":"R6","unstructured":"G. Buntrock,Wachsende kontext-sensitive Sprachen.\n          Habilitationsschrift. Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (1996)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1997.2681","volume":"141","author":"Buntrock","year":"1998","journal-title":"Inf. Comput."},{"key":"R8","unstructured":"J. \u010cejka, Learning correctness preserving\n            reduction analysis. BSc Project, Charles University. Faculty of Mathematics and\n          Physics, Prague, Czech (2003)."},{"key":"R9","first-page":"17","volume":"104","author":"\u010cerno","year":"2010","journal-title":"Fund. Inf."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"P. \u010cerno and F. Mr\u00e1z, \u0394-clearing\n          restarting automata and CFL, in edited by G. Mauri and A. Leporati. DLT\n            2011, in vol. 6795 of Lect. Notes Comput. Sci. Springer,\n          Berlin (2011) 153\u2013164.","DOI":"10.1007\/978-3-642-22321-1_14"},{"key":"R11","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"Dahlhaus","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"R12","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.tcs.2004.04.009","volume":"327","author":"Hofbauer","year":"2004","journal-title":"Theoret. Comput. Sci."},{"key":"R13","unstructured":"P. Hoffmann, Learning restarting automata by\n          genetic algorithms, in SOFSEM 2002: Student Research Forum, edited by M.\n          Bielikov\u00e1. Masaryk University, Brno (2002) 15\u201320."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"P. Jan\u010dar, F. Mr\u00e1z, M. Pl\u00e1tek and J. Vogel,\n          Restarting automata, FCT\u201995, in vol. 965 of Lect. Notes Comput.\n            Sci., edited by H. Reichel. Springer, Berlin (1995) 283\u2013292.","DOI":"10.1007\/3-540-60249-6_60"},{"key":"R15","first-page":"287","volume":"4","author":"Jan\u010dar","year":"1999","journal-title":"J. Autom. Lang. Comb."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"D. Knuth and P. Bendix, Simple word problems in\n          universal algebras, in Comput. Problems in Abstract Algebra, edited by J.\n          Leech. Pergamon Press, New York (1970) 263\u2013297.","DOI":"10.1016\/B978-0-08-012975-4.50028-X"},{"key":"R17","first-page":"219","volume":"112","author":"Leupold","year":"2011","journal-title":"Fund. Inf."},{"key":"R18","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"McNaughton","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"F. Mr\u00e1z, F. Otto and M. Pl\u00e1tek, Learning analysis\n          by reduction from positive data, in ICGI 2006, in vol. 4201 of\n            Lect. Notes Comput. Sci., edited by Y. Sakakibara, S. Kobayashi, K.\n          Sato, T. Nishino and E. Tomita. Springer, Berlin (2006) 125\u2013136.","DOI":"10.1007\/11872436_11"},{"key":"R20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2004.09.003","volume":"197","author":"Niemann","year":"2005","journal-title":"Inform. Comput."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"G. Niemann and J.R. Woinowski, The growing\n          context-sensitive languages are the acyclic context-sensitive languages, in DLT\n            2002, in vol. 2295 of Lect. Notes Comput. Sci., edited by W.\n          Kuich, G. Rozenberg and A. Salomaa. Springer, Berlin (2002) 197\u2013205.","DOI":"10.1007\/3-540-46011-X_16"},{"key":"R22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0022-0000(87)90017-1","volume":"35","author":"Otto","year":"1987","journal-title":"J. Comput. System Sci."},{"key":"R23","unstructured":"F. Otto, Restarting automata, Recent\n            Advances in Formal Languages and Applications, in vol. 25 of Studies in\n            Comput. Intelligence, edited by Z. \u00c9sik, C. Martin-Vide and V. Mitrana.\n          Springer, Berlin (2006) 269\u2013303."},{"key":"R24","unstructured":"F. Otto, P. \u010cerno and F. Mr\u00e1z, Limited context\n          restarting automata and McNaughton families of languages, in Fourth Workshop on\n            Non-Classical Models for Automata and Applications (NCMA 2012), Proc.,\n          books@ocg.at, Band 290, edited by R. Freund, M. Holzer, B. Truthe and U. Ultes-Nitsche.\n          Oesterreichische Computer Gesellschaft, Wien (2012) 165\u2013180."},{"key":"R25","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0890-5401(03)00035-X","volume":"183","author":"Woinowski","year":"2003","journal-title":"Inform. Comput."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2014001\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T11:57:54Z","timestamp":1630670274000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2014001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":25,"journal-issue":{"issue":"1"},"alternative-id":["ita130005"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2014001","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}