Publications

Authors Publication Name
F. Otto, P. Černo, F. Mráz On the Classes of Languages Accepted by Limited Context Restarting Automata
RAIRO - Theoretical Informatics and Applications, 2014, Vol. eFirst, 1–24. ISSN 1290-385X
Abstract: In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton families of languages, relating the classes of languages accepted by these automata in particular to the class GCSL of growing context-sensitive languages and to the class CRL of Church–Rosser languages.
Links: BibTeX, DOI
P. Černo Grammatical Inference of Lambda Confluent Context Rewriting Systems
In Suna Bench, Frank Drewes, Rudolf Freund, Friedrich Otto, editors, Workshop on Non-Classical Models of Automata and Applications (NCMA), books@ocg.at, pages 85-100. Österreichisches Computer Gesellschaft, 2013.
Abstract: We introduce a general learning algorithm for inferring various restricted types of context rewriting systems, which are defined as string-rewriting systems extended by contexts. We show that, under certain conditions, it is possible to identify in the limit any target context rewriting system with minimal width of instructions from the set of positive and negative samples. In addition, we show that the learning algorithm works in polynomial time with respect to the size of the set of positive and negative samples when used on lambda-confluent context rewriting systems.
Links: BibTeX, NCMA 2013, Presentation
P. Černo Clearing Restarting Automata and Grammatical Inference
Proceedings of the Eleventh International Conference on Grammatical Inference (ICGI 2012), September 5-8, 2012, University of Maryland, College Park, United States, JMLR, Vol. 21, 54-68.
Abstract: Clearing and subword-clearing restarting automata are linguistically motivated models of automata. We investigate the problem of grammatical inference for such automata based on the given set of positive and negative samples. We show that it is possible to identify these models in the limit. In this way we can learn a large class of languages. On the other hand, we prove that the task of finding a clearing restarting automaton consistent with a given set of positive and negative samples is NP-hard, provided that we impose an upper bound on the width of its instructions.
Links: BibTeX, JMLR Proceedings, Fulltext, Presentation
P. Černo Clearing Restarting Automata and Grammatical Inference (Technical Report)
Technical report, 1/2012, Charles University, Faculty of Mathematics and Physics, Prague.
Links: BibTeX, Fulltext
F. Otto, P. Černo, F. Mráz Limited Context Restarting Automata and McNaughton Families of Languages
In Rudolf Freund, Markus Holzer, Bianca Truthe, and Ulrich Ultes-Nitsche, editors, Workshop on Non-Classical Models of Automata and Applications (NCMA), books@ocg.at, pages 165-180. Österreichisches Computer Gesellschaft, 2012.
Abstract: In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word within a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton families of languages, relating the classes of languages accepted by these automata in particular to the class GCSL of growing context-sensitive languages and to the class CRL of Church-Rosser languages.
Links: BibTeX, NCMA 2012, Presentation
P. Černo Learning Automata and Grammars
Week of Doctoral Students 2011 - Proceedings of Contributed Papers: Part I – Mathematics and Computer Science (eds. J. Safrankova and J. Pavlu), Prague, Matfyzpress, pp. 125–131, 2011. ISBN 978-80-7378-184-2.
Abstract: The problem of learning or inferring automata and grammars has been studied for decades and has connections to many disciplines, including bio-informatics, computational linguistics and pattern recognition. In this paper we present a short survey of basic models and techniques related to the grammatical inference and try to outline some new promising approaches which we expect to bring new light into this subject. For illustration, we introduce delimited string-rewriting systems as a sample model for grammatical inference and sketch the simplified version of the learning algorithm LARS for these systems.
Links: BibTeX, Fulltext, Presentation
P. Černo, F. Mráz Delta-Clearing Restarting Automata and CFL
Proceedings of the 15th International Conference on Developments in Language Theory (DLT 2011) (Milano, Italy), Springer, Berlin, 2011, LNCS, Vol. 6795, 153-164.
Abstract: Delta-clearing restarting automata represent a new restricted model of restarting automata which, based on a limited context, can either delete a substring of the current content of its tape or replace a substring by a special auxiliary symbol Delta, which cannot be overwritten anymore, but it can be deleted later. The main result of this paper consists in proving that besides their limited operations, Delta-clearing restarting automata recognize all context-free languages.
Links: BibTeX, SpringerLink, Presentation
P. Černo, F. Mráz Delta-Clearing Restarting Automata and CFL (Technical Report)
Technical report, 8/2011, Charles University, Faculty of Mathematics and Physics, Prague.
Links: BibTeX, Fulltext
P. Černo, F. Mráz Clearing Restarting Automata
Fundamenta Informaticae, 2010, Vol. 104, No. 1, 17-54, DOI 10.3233/FI-2010-334.
Abstract: Restarting automata were introduced as a model for analysis by reduction, which is a linguistically motivated method for checking correctness of a sentence. We propose a new restricted version of restarting automata called clearing restarting automata with a very simple definition but simultaneously with interesting properties with respect to their possible applications. The new model can be learned very efficiently from positive examples and its stronger version can be used to learn effectively a large class of languages. We relate the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.
Links: BibTeX, Fundamenta Informaticae

Presentations

Presentation Name
icon Grammatical Inference of Lambda Confluent Context Rewriting Systems
Description Presentation for the Workshop on Non-Classical Models of Automata and Applications (NCMA 2013).
Links Pdf presentation | Powerpoint presentation
icon Clearing Restarting Automata and Grammatical Inference
Description Presentation for the 11th International Conference on Grammatical Inference .
Links Pdf presentation | Powerpoint presentation
icon Limited Context Restarting Automata and McNaughton Families of Languages
Description Presentation for the 4th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2012).
Links Pdf presentation | Powerpoint presentation | Official website
icon Grammatical Evolution
Description Presentation for the seminary NTIN091 Seminar for MSc. and Ph.D.-students I.
Links Pdf presentation | Powerpoint presentation
icon Learning Automata and Grammars
Description Presentation for the Week of Doctoral Students 2011.
Links Pdf presentation | Powerpoint presentation | Official website
icon Delta-Clearing Restarting Automata and CFL
Description Presentation for the 15th International Conference on Developments in Language Theory (DLT 2011).
Links Pdf presentation | Powerpoint presentation | Official website
icon Three Learnable Models for the Description of Language
Description Presentation for the seminary NTIN046 Parsing and Syntactic Analysis.
Links Pdf presentation | Powerpoint presentation
icon Delta Rules
Description Presentation for the seminary NTIN046 Parsing and Syntactic Analysis.
Links Pdf presentation | Powerpoint presentation
icon Coding
Description Presentation for the seminary NTIN046 Parsing and Syntactic Analysis.
Links Pdf presentation | Powerpoint presentation
icon Diploma Thesis: Clearing Restarting Automata
Description Diploma Thesis: Clearing Restarting Automata.
Links Pdf presentation | Powerpoint presentation
icon NCMA 2009: Clearing Restarting Automata
Description Workshop NCMA, Wroclaw, Poland, August 31 - September 1, 2009.
Links Pdf presentation | Powerpoint presentation | Pdf presentation (print version) | Powerpoint presentation (print version) | Official website
icon ABCD 2009: Learning Restricted Restarting Automata
Description Workshop ABCD, Prague, March 27-29, 2009. See some photos.
Links Pdf presentation | Powerpoint presentation | Official website

Last updated: Monday, 03/03/14