| 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 |
Czech 
Slovak 
