Publikace

Autori Název publikace
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
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: BibTeX, Fundamenta Informaticae

Prezentace

Název prezentace
icon Grammatical Inference of Lambda Confluent Context Rewriting Systems
Popis Prezentace pro Workshop NCMA 2013.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Clearing Restarting Automata and Grammatical Inference
Popis Prezentace pro 11. mezinárodní konferenci ICGI 2012.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Limited Context Restarting Automata and McNaughton Families of Languages
Popis Prezentace pro 4. mezinárodní workshop Non-Classical Models of Automata and Applications (NCMA 2012).
Odkazy Pdf prezentace | Powerpoint prezentace | Oficiální stránky
icon Grammatical Evolution
Popis Prezentace pro seminář NTIN091 Diplomový a doktorandský seminář I.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Learning Automata and Grammars
Popis Prezentace pro Doktorandský týden 2011.
Odkazy Pdf prezentace | Powerpoint prezentace | Oficiální stránky
icon Delta-Clearing Restarting Automata and CFL
Popis Prezentace pro 15. mezinárodní konferenci Developments in Language Theory (DLT 2011).
Odkazy Pdf prezentace | Powerpoint prezentace | Oficiální stránky
icon Three Learnable Models for the Description of Language
Popis Prezentace pro seminář NTIN046 Rozpoznávání a syntaktická analýza.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Delta Rules
Popis Prezentace pro seminář NTIN046 Rozpoznávání a syntaktická analýza.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Coding
Popis Prezentace pro seminář NTIN046 Rozpoznávání a syntaktická analýza.
Odkazy Pdf prezentace | Powerpoint prezentace
icon Diploma Thesis: Clearing Restarting Automata
Popis Diplomová práce: Clearing Restarting Automata.
Odkazy Pdf prezentace | Powerpoint prezentace
icon NCMA 2009: Clearing Restarting Automata
Popis Workshop NCMA, Wroclaw, Polsko, 31. srpna - 1. září 2009.
Odkazy Pdf prezentace | Powerpoint prezentace | Pdf prezentace (verze pro tisk) | Powerpoint prezentace (verze pro tisk) | Oficiální stránky
icon ABCD 2009: Learning Restricted Restarting Automata
Popis Workshop ABCD, Praha, 27.-29. března 2009. Pozri fotky.
Odkazy Pdf prezentace | Powerpoint prezentace | Oficiální stránky

Poslední úprava: Pondělí, 3.3.2014