Global QuickSearch:   Number of matching entries: 0

Search Settings

    BibTeX-Key Author / Editor / Organization Title Year Journal / Proceedings / Book BibTeX type Keywords
    BasM11 Basovník, S. & Mráz, F. Learning Limited Context Restarting Automata by
    Genetic Algorithm
    2011 Proc. Theorietag 2011, Otto-von-Guercke-Universität, pp. 1-4 incollection reduction analysis, grammatical inference,
    restarting automata, genetic algorithms
    Abstract: We propose a genetic algorithm for learning
    restricted variants of restarting automata from positive and negative
    samples. Experiments comparing the proposed genetic algorithm to algorithms
    RPNI and LARS on sample languages indicate that the new algorithm is able to
    infer a target language even from a small set of samples.
    BibTeX:
    @incollection{BasM11,
      author = {Stanislav Basovník and František Mráz},
      title = {Learning Limited Context Restarting Automata by
    Genetic Algorithm}, booktitle = {Proc. Theorietag 2011}, publisher = {Otto-von-Guercke-Universität}, year = {2011}, pages = {1--4} }
    BasM10 Basovník, S. & Mráz, F. Learning Restricted Restarting Automata using
    Genetic Algorithm
    2010 Charles University, Faculty of Mathematics and
    Physics, 2011/9, Prague, 4 pages
    techreport reduction analysis, grammatical inference,
    restarting automata, genetic algorithms
    Abstract: We propose a genetic algorithm for learning
    restricted variants of restarting automata from positive and negative
    samples. Experiments comparing the proposed genetic algorithm to algorithms
    RPNI and LARS on sample languages indicate that the new algorithm is able to
    infer a target language even from a small set of samples.
    BibTeX:
    @techreport{BasM10,
      author = {Stanislav Basovník and František Mráz},
      title = {Learning Restricted Restarting Automata using
    Genetic Algorithm}, address = {Prague}, institution = {Charles University, Faculty of Mathematics and
    Physics}, year = {2010}, number = {2011/9}, note = {4 pages} }
    CM09 Černo, P. & Mráz, F.
    Bordihn, H.; Freund, R.; Holzer, M.; Kutrib, M. & Otto, F. (Eds.)
    Clearing restarting automata 2009 Workshop on Non-Classical Models for Automata
    and Applications (NCMA), Vol. 256(), books@ocg.at, Österreichisches Computer Gesellschaft, pp. 77-90
    inproceedings
    BibTeX:
    @inproceedings{CM09,
      author = {Peter Černo and František Mráz},
      title = {Clearing restarting automata},
      booktitle = {Workshop on Non-Classical Models for Automata
    and Applications (NCMA)}, editor = {Henning Bordihn and Rudolf Freund and Markus
    Holzer and Martin Kutrib and Friedrich Otto}, publisher = {Österreichisches Computer Gesellschaft}, series = {books@ocg.at}, year = {2009}, volume = {256}, pages = {77--90} }
    CM11dlt Černo, P. & Mráz, F.
    Mauri, G. & Leporati, A. (Eds.)
    $Delta $-clearing restarting automata and
    CFL.
    2011 Developments in Language Theory - 15th
    International Conference, DLT 2011, Milan, Italy, July 19-22, 2011.
    Proceedings, Vol. 6795(), Lecture Notes in Computer Science, Berlin, Springer, pp. 153-164
    inproceedings analysis by reduction; context-free languages;
    $delta $-clearing restarting automata; formal languages
    Abstract: Summary: $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.
    BibTeX:
    @inproceedings{CM11dlt,
      author = {Černo, Peter and Mráz, František},
      title = {$Delta $-clearing restarting automata and
    CFL.}, booktitle = {Developments in Language Theory - 15th
    International Conference, DLT 2011, Milan, Italy, July 19-22, 2011.
    Proceedings}, editor = {Giancarlo Mauri and Alberto Leporati}, publisher = {Berlin, Springer}, series = {Lecture Notes in Computer Science}, year = {2011}, volume = {6795}, pages = {153--164}, doi = {http://dx.doi.org/10.1007/978-3-642-22321-1_14} }
    CM11tech Černo, P. & Mráz, F. Delta-Clearing Restarting Automata and CFL 2011 Charles University, Faculty of Mathematics and
    Physics, 2011/8, Prague
    techreport analysis by reduction, context-free languages,
    delta-clearing restarting automata, formal languages
    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 $, which cannot be
    overwritten anymore, but it can be deleted later. The main result of this
    paper consists in the proving that beside their limited operations,
    Delta-clearing restarting automata recognize all context-free languages.
    BibTeX:
    @techreport{CM11tech,
      author = {Peter Černo and František Mráz},
      title = {Delta-Clearing Restarting Automata and CFL},
      address = {Prague},
      institution = {Charles University, Faculty of Mathematics and
    Physics}, year = {2011}, number = {2011/8}, url = {http://popelka.ms.mff.cuni.cz/cerno/files/cerno_mraz_dclra_and_cfl.pdf} }
    CM10 Černo, P. & Mráz, F. Clearing Restarting Automata 2010 Fundamenta Informaticae, Vol. 104(1), pp. 17-54 article
    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.
    BibTeX:
    @article{CM10,
      author = {Peter Černo and František Mráz},
      title = {Clearing Restarting Automata},
      journal = {Fundamenta Informaticae},
      year = {2010},
      volume = {104},
      number = {1},
      pages = {17--54},
      url = {http://www.mimuw.edu.pl/~fundam/FI/previous/abs104.html#2},
      doi = {http://dx.doi.org/10.3233/FI-2010-334}
    }
    					
    CM09techrep Černo, P. & Mráz, F. Clearing restarting automata 2009 Department of Computer Science, 2010/6, Charles University, Prague techreport
    BibTeX:
    @techreport{CM09techrep,
      author = {Peter Černo and František Mráz},
      title = {Clearing restarting automata},
      address = {Charles University, Prague},
      institution = {Department of Computer Science},
      year = {2009},
      number = {2010/6}
    }
    					
    ChM90slo Chytil, M. & Mráz, F.
    Bartošek, M. (Eds.)
    Složitost paralelních výpočtů 1990 SOFSEM'90, Janské Lázně, Krkonoše, pp. 157-186 inproceedings
    BibTeX:
    @inproceedings{ChM90slo,
      author = {Michal Chytil and František Mráz},
      title = {Složitost paralelních výpočtů},
      booktitle = {SOFSEM'90},
      editor = {Miroslav Bartošek},
      address = {Janské Lázně, Krkonoše},
      year = {1990},
      pages = {157--186}
    }
    					
    ChMSV89slo Chytil, M.; Mráz, F.; Škarvada, L. & Vašín, M.
    Bartošek, M. (Eds.)
    Paralelní výpočet chybové vzdálenosti 1989 SOFSEM'89, Ždiar, Vysoké Tatry, pp. 27-30 inproceedings
    BibTeX:
    @inproceedings{ChMSV89slo,
      author = {Michal Chytil and František Mráz and Libor
    Škarvada and Marek Vašín}, title = {Paralelní výpočet chybové vzdálenosti}, booktitle = {SOFSEM'89}, editor = {Miroslav Bartošek}, address = {Ždiar, Vysoké Tatry}, year = {1989}, pages = {27--30} }
    JMP92sofabbr Jančar, P.; Mráz, F. & Plátek, M.
    Bartošek, M. (Eds.)
    Forgetting automata and the Chomsky
    hierarchy
    1992 SOFSEM'92, Contributed talks, Magura, Vysoké Tatry, Czechoslovakia, pp. 41-44 inproceedings
    BibTeX:
    @inproceedings{JMP92sofabbr,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {Forgetting automata and the Chomsky
    hierarchy}, booktitle = {SOFSEM'92, Contributed talks}, editor = {Miroslav Bartošek}, address = {Magura, Vysoké Tatry, Czechoslovakia}, year = {1992}, pages = {41--44} }
    JMP93abbr Jančar, P.; Mráz, F. & Plátek, M.
    Borzyszkowski, A.M. & Sokolowski, S. (Eds.)
    A Taxonomy of Forgetting Automata 1993 MFCS'93, 18th International Symposium, Vol. 711(), LNCS, Springer, Gdansk, Poland, pp. 527-536 inproceedings
    BibTeX:
    @inproceedings{JMP93abbr,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {A Taxonomy of Forgetting Automata}, booktitle = {MFCS'93, 18th International Symposium}, editor = {Andrzej M. Borzyszkowski and Stefan
    Sokolowski}, publisher = {Springer}, address = {Gdansk, Poland}, series = {LNCS}, year = {1993}, volume = {711}, pages = {527--536} }
    JMP92abbr Jančar, P.; Mráz, F. & Plátek, M.
    Havel, I.M. & Koubek, V. (Eds.)
    Characterization of Context-Free Languages by
    Erasing Automata
    1992 MFCS'92, 17th International Symposium, Vol. 629(), LNCS, Springer, Prague, Czechoslovakia, pp. 307-314 inproceedings
    BibTeX:
    @inproceedings{JMP92abbr,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {Characterization of Context-Free Languages by
    Erasing Automata}, booktitle = {MFCS'92, 17th International Symposium}, editor = {Ivan M. Havel and Václav Koubek}, publisher = {Springer}, address = {Prague, Czechoslovakia}, series = {LNCS}, year = {1992}, volume = {629}, pages = {307--314} }
    JMP96 Jančar, P.; Mráz, F. & Plátek, M. Forgetting Automata and Context-Free
    Languages
    1996 Acta Informatica, Vol. 33(5), pp. 409-420 article
    BibTeX:
    @article{JMP96,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {Forgetting Automata and Context-Free
    Languages}, journal = {Acta Informatica}, year = {1996}, volume = {33}, number = {5}, pages = {409--420} }
    JMP93p Jančar, P.; Mráz, F. & Plátek, M. A Taxonomy of Forgetting Automata 1993 Department of Computer Science, 101, Charles University Prague, 17 pages techreport
    BibTeX:
    @techreport{JMP93p,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {A Taxonomy of Forgetting Automata}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1993}, number = {101}, note = {17 pages} }
    JMP92p Jančar, P.; Mráz, F. & Plátek, M. Characterization of Context-Free Languages by
    Erasing Automata
    1992 Department of Computer Science, 99, Charles University Prague, 9 pages techreport
    BibTeX:
    @techreport{JMP92p,
      author = {Petr Jančar and František Mráz and Martin
    Plátek}, title = {Characterization of Context-Free Languages by
    Erasing Automata}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1992}, number = {99}, note = {9 pages} }
    JMPPV98 Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J.
    Bozapalidis, S. (Eds.)
    Deleting Automata with a Restart Operation 1998 Developments in Language Theory, 1997, University of Thessaloniki, Thessaloniki, Greece, pp. 191-202 inproceedings
    BibTeX:
    @inproceedings{JMPPV98,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Martin Procházka and Jörg Vogel}, title = {Deleting Automata with a Restart Operation}, booktitle = {Developments in Language Theory, 1997}, editor = {S. Bozapalidis}, publisher = {University of Thessaloniki}, address = {Thessaloniki, Greece}, year = {1998}, pages = {191--202} }
    JMPPV96 Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J.
    Dassow, J.; Rozenberg, G. & Salomaa, A. (Eds.)
    Restarting Automata, Marcus Grammars and
    Context-Free Languages
    1996 Developments in Language Theory II, World Scientific Publ., Magdeburg, Germany, pp. 102-111 inproceedings
    BibTeX:
    @inproceedings{JMPPV96,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Martin Procházka and Jörg Vogel}, title = {Restarting Automata, Marcus Grammars and
    Context-Free Languages}, booktitle = {Developments in Language Theory II}, editor = {J. Dassow and G. Rozenberg and A. Salomaa}, publisher = {World Scientific Publ.}, address = {Magdeburg, Germany}, year = {1996}, pages = {102--111} }
    JMPPV97p Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J. Deleting Automata with a Restart Operation 1997 Department of Computer Science, 97/2, Charles University Prague, 12 pages techreport
    BibTeX:
    @techreport{JMPPV97p,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Martin Procházka and Jörg Vogel}, title = {Deleting Automata with a Restart Operation}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1997}, number = {97/2}, note = {12 pages} }
    JMPPV95j Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J. Restarting Automata and Marcus Grammars 1995 Institut für Informatik, Math/95/1, Friedrich-Schiller-Universität Jena, 11 pages techreport
    BibTeX:
    @techreport{JMPPV95j,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Martin Procházka and Jörg Vogel}, title = {Restarting Automata and Marcus Grammars}, address = {Friedrich-Schiller-Universität Jena}, institution = {Institut für Informatik}, year = {1995}, number = {Math/95/1}, note = {11 pages} }
    JMPV98 Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
    Arvind, V. & Ramanujam, R. (Eds.)
    Different Types of Monotonicity for Restarting
    Automata
    1998 FSTsl &TCS'98, Vol. 1530(), LNCS, Springer, Chennai, India, pp. 343-354 inproceedings
    BibTeX:
    @inproceedings{JMPV98,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Different Types of Monotonicity for Restarting
    Automata}, booktitle = {FSTsl &TCS'98}, editor = {V. Arvind and R. Ramanujam}, publisher = {Springer}, address = {Chennai, India}, series = {LNCS}, year = {1998}, volume = {1530}, pages = {343--354} }
    JMPV96abbr Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
    Jeffery, K.G.; Král, J. & Bartošek, M. (Eds.)
    Restarting Automata with Rewriting 1996 SOFSEM'96, Vol. 1175(), LNCS, Springer, Milovy, Czech Republic, pp. 401-408 inproceedings
    BibTeX:
    @inproceedings{JMPV96abbr,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Restarting Automata with Rewriting}, booktitle = {SOFSEM'96}, editor = {K. G. Jeffery and J. Král and M. Bartošek}, publisher = {Springer}, address = {Milovy, Czech Republic}, series = {LNCS}, year = {1996}, volume = {1175}, pages = {401--408} }
    JMPV98a Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
    Kudlek, M. (Eds.)
    On Monotony for Restarting Automata 1998 `Mathematical Linguistics' Workshop
    Proceedings, Bericht 213, Universität Hamburg, Fachbereich Informatik, pp. 71-84
    inproceedings
    BibTeX:
    @inproceedings{JMPV98a,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {On Monotony for Restarting Automata}, booktitle = {`Mathematical Linguistics' Workshop
    Proceedings}, editor = {M. Kudlek}, publisher = {Universität Hamburg, Fachbereich Informatik}, series = {Bericht 213}, year = {1998}, pages = {71--84} }
    JMPV97 Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
    Păun, G. & Salomaa, A. (Eds.)
    On Restarting Automata with Rewriting 1997 New Trends in Formal Language Theory (Control,
    Cooperation and Combinatorics), Vol. 1218(), LNCS, Springer, pp. 119-136
    incollection
    BibTeX:
    @incollection{JMPV97,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {On Restarting Automata with Rewriting}, booktitle = {New Trends in Formal Language Theory (Control,
    Cooperation and Combinatorics)}, editor = {G. Păun and A. Salomaa}, publisher = {Springer}, series = {LNCS}, year = {1997}, volume = {1218}, pages = {119--136} }
    JMPV95 Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
    Reichel, H. (Eds.)
    Restarting Automata 1995 FCT'95, Vol. 965(), LNCS, Springer, Dresden, Germany, pp. 283-292 inproceedings
    BibTeX:
    @inproceedings{JMPV95,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Restarting Automata}, booktitle = {FCT'95}, editor = {Horst Reichel}, publisher = {Springer}, address = {Dresden, Germany}, series = {LNCS}, year = {1995}, volume = {965}, pages = {283--292} }
    JMPV07 Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. Monotonicity of Restarting Automata 2007 Journal of Automata, Languages and
    Combinatorics, Vol. 12(3), pp. 355-371
    article
    BibTeX:
    @article{JMPV07,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Monotonicity of Restarting Automata}, journal = {Journal of Automata, Languages and
    Combinatorics}, year = {2007}, volume = {12}, number = {3}, pages = {355--371} }
    JMPV02j Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. Monotonicity on restarting automata 2002 Institut für Informatik,
    Friedrich-Schiller-Universität Jena, Math/Inf/02/01, 12 pages
    techreport
    BibTeX:
    @techreport{JMPV02j,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Monotonicity on restarting automata}, institution = {Institut für Informatik,
    Friedrich-Schiller-Universität Jena}, year = {2002}, number = {Math/Inf/02/01}, note = {12 pages} }
    JMPV99 Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. On Monotonic Automata with a Restart
    Operation
    1999 Journal of Automata, Languages and
    Combinatorics, Vol. 4(4), pp. 287-311
    article
    BibTeX:
    @article{JMPV99,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {On Monotonic Automata with a Restart
    Operation}, journal = {Journal of Automata, Languages and
    Combinatorics}, year = {1999}, volume = {4}, number = {4}, pages = {287--311} }
    JMPV98j Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. Different Types of Monotonicity for Restarting
    Automata
    1998 Institut für Informatik, Math/Inf/98/15, Friedrich-Schiller-Universität Jena, 15 pages techreport
    BibTeX:
    @techreport{JMPV98j,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Different Types of Monotonicity for Restarting
    Automata}, address = {Friedrich-Schiller-Universität Jena}, institution = {Institut für Informatik}, year = {1998}, number = {Math/Inf/98/15}, note = {15 pages} }
    JMPV96p Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. On Restarting Automata with Rewriting 1996 Department of Computer Science, 96/5, Charles University Prague, 21 pages techreport
    BibTeX:
    @techreport{JMPV96p,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {On Restarting Automata with Rewriting}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1996}, number = {96/5}, note = {21 pages} }
    JMPV94j Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. Restarting Automata 1994 Institut für Informatik, Math/94/8, Friedrich-Schiller-Universität Jena, 12 pages techreport
    BibTeX:
    @techreport{JMPV94j,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Restarting Automata}, address = {Friedrich-Schiller-Universität Jena}, institution = {Institut für Informatik}, year = {1994}, number = {Math/94/8}, note = {12 pages} }
    JMPV94p Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. Deleting Automata with a Restart Operation 1994 Department of Computer Science, 105, Charles University Prague, 13 pages techreport
    BibTeX:
    @techreport{JMPV94p,
      author = {Petr Jančar and František Mráz and Martin
    Plátek and Jörg Vogel}, title = {Deleting Automata with a Restart Operation}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1994}, number = {105}, note = {13 pages} }
    JMOP05cai Jurdziński, T.; Mráz, F.; Otto, F. & Plátek, M.
    Bozapalidis, S.; Kalampakas, A. & Rahonis, G. (Eds.)
    Cut hierarchies for restarting automata and
    Marcus t-contextual grammars
    2005 Proceedings of the 1st International Confernce
    on Agebraic Informatics, Aristotle University of Thessaloniki, pp. 157-172
    inproceedings
    BibTeX:
    @inproceedings{JMOP05cai,
      author = {Tomasz Jurdziński and František Mráz and
    Friedrich Otto and Martin Plátek}, title = {Cut hierarchies for restarting automata and
    Marcus t-contextual grammars}, booktitle = {Proceedings of the 1st International Confernce
    on Agebraic Informatics}, editor = {S. Bozapalidis and A. Kalampakas and G.
    Rahonis}, publisher = {Aristotle University of Thessaloniki}, year = {2005}, pages = {157--172} }
    JMOP06 Jurdziński, T.; Mráz, F.; Otto, F. & Plátek, M. Degrees of non-monotonicity for restarting
    automata
    2006 Theoretical Computer Science, Vol. 369(1--3), pp. 1-34 article
    Abstract: In the literature various notions of
    monotonicity for restarting automata have been studied. Here we introduce
    two new variants of monotonicity for restarting automata and for two-way
    restarting automata: left-monotonicity and right-left-monotonicity. It is
    shown that for the various types of deterministic and nondeterministic
    (two-way) restarting automata without auxiliary symbols, these notions yield
    infinite hierarchies, and we compare these hierarchies to each other.
    Further, as a tool used to simplify some of the proofs, the shrinking
    restarting automaton is introduced, which is a generalization of the
    standard (length-reducing) restarting automaton to the weight-reducing case.
    Some of the consequences of this generalization are also discussed.
    BibTeX:
    @article{JMOP06,
      author = {Tomasz Jurdziński and František Mráz and
    Friedrich Otto and Martin Plátek}, title = {Degrees of non-monotonicity for restarting
    automata}, journal = {Theoretical Computer Science}, year = {2006}, volume = {369}, number = {1--3}, pages = {1--34} }
    JMOP04t21 Jurdziński, T.; Mráz, F.; Otto, F. & Plátek, M. Cut hierarchies for restarting automata and
    Marcus t-contextual grammars
    2004 Universität Kassel, 21/04, 23 pages techreport
    BibTeX:
    @techreport{JMOP04t21,
      author = {Tomasz Jurdziński and František Mráz and
    Friedrich Otto and Martin Plátek}, title = {Cut hierarchies for restarting automata and
    Marcus t-contextual grammars}, institution = {Universität Kassel}, year = {2004}, number = {21/04}, note = {23 pages} }
    JOMP04comp Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M.
    Calude, C.; Calude, E. & Dinneen, M. (Eds.)
    On the Complexity of 2-Monotone Restarting
    Automata
    2004 Developments in Language Theory, Proceedings DLT
    2004, Vol. 3340(), LNCS, Springer-Verlag, Berlin, pp. 237-248
    inproceedings
    Abstract: It is known that for monotone deterministic
    one-way restarting automata, the use of auxiliary symbols does not increase
    the expressive power. Here we show that the same is true for deterministic
    two-way restarting automata that are right- or left-monotone. Actually in
    these cases it suffices to admit delete operations instead of the more
    general rewrite operations. In addition, we characterize the classes of
    languages that are accepted by these types of two-way restarting automata by
    certain combinations of deterministic pushdown automata and deterministic
    transducers.
    BibTeX:
    @inproceedings{JOMP04comp,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {On the Complexity of 2-Monotone Restarting
    Automata}, booktitle = {Developments in Language Theory, Proceedings DLT
    2004}, editor = {C.S.~Calude and E.~Calude and M.J.~Dinneen}, publisher = {Springer-Verlag}, address = {Berlin}, series = {LNCS}, year = {2004}, volume = {3340}, pages = {237--248} }
    JOMP04leftmon Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M.
    Calude, C.; Calude, E. & Dinneen, M. (Eds.)
    On left-monotone deterministic restarting
    automata
    2004 Developments in Language Theory, Proceedings DLT
    2004, Vol. 3340(), LNCS, Springer-Verlag, Berlin, pp. 249-260
    inproceedings
    BibTeX:
    @inproceedings{JOMP04leftmon,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {On left-monotone deterministic restarting
    automata}, booktitle = {Developments in Language Theory, Proceedings DLT
    2004}, editor = {C.S.~Calude and E.~Calude and M.J.~Dinneen}, publisher = {Springer-Verlag}, address = {Berlin}, series = {LNCS}, year = {2004}, volume = {3340}, pages = {249--260} }
    JOMP05dlt Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M.
    Felice, C.D. & Restivo, A. (Eds.)
    Monotone deterministic RL-automata don't need
    auxiliary symbols
    2005 Developments in Language Theory, Proceedings DLT
    2005, Vol. 3572(), LNCS, Springer-Verlag, Berlin, pp. 284-295
    inproceedings
    Abstract: It is known that for monotone deterministic
    one-way restarting automata, the use of auxiliary symbols does not increase
    the expressive power. Here we show that the same is true for deterministic
    two-way restarting automata that are right- or left-monotone. Actually in
    these cases it suffices to admit delete operations instead of the more
    general rewrite operations. In addition, we characterize the classes of
    languages that are accepted by these types of two-way restarting automata by
    certain combinations of deterministic pushdown automata and deterministic
    transducers.
    BibTeX:
    @inproceedings{JOMP05dlt,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {Monotone deterministic RL-automata don't need
    auxiliary symbols}, booktitle = {Developments in Language Theory, Proceedings DLT
    2005}, editor = {C.~De~Felice and A.~Restivo}, publisher = {Springer-Verlag}, address = {Berlin}, series = {LNCS}, year = {2005}, volume = {3572}, pages = {284--295} }
    JOMP08 Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. On the Complexity of 2-Monotone Restarting
    Automata
    2008 Theory of Computing Systems, Vol. 42(4), pp. 488-518 article
    Abstract: The R-automaton is the weakest form of the
    nondeterministic version of the restarting automaton that was introduced by
    Jančar et al. to model the so-called analysis by reduction. Here it is
    shown that the class L(R) of languages that are accepted by R-automata is
    incomparable under set inclusion to the class CRL of Church-Rosser languages
    and to the class GCSL of growing context-sensitive languages. In fact this
    already holds for the class 2-mon-R of languages that are accepted by
    2-monotone R-automata. In addition, we prove that already the latter class
    contains NP-complete languages, showing that already the 2-monotone
    R-automaton has a surprisingly large expressive power.
    BibTeX:
    @article{JOMP08,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {On the Complexity of 2-Monotone Restarting
    Automata}, journal = {Theory of Computing Systems}, year = {2008}, volume = {42}, number = {4}, pages = {488--518}, doi = {http://dx.doi.org/10.1007/s00224-007-9004-y} }
    JOMP05 Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. Deterministic Two-Way Restarting Automata and
    Marcus Contextual Grammars
    2005 Fundamenta Informaticae, Vol. 64(1--4), pp. 217-228 article
    Abstract: It is known that for (right-) monotone
    deterministic one-way restarting automata, the use of auxiliary symbols does
    not increase the expressive power. Here we show that the same is true for
    deterministic two-way restarting automata that are right-left-monotone.
    Moreover, we present a transformation of this kind of restarting automata
    into contextual grammars with regular selection.
    BibTeX:
    @article{JOMP05,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {Deterministic Two-Way Restarting Automata and
    Marcus Contextual Grammars}, journal = {Fundamenta Informaticae}, year = {2005}, volume = {64}, number = {1--4}, pages = {217--228} }
    JOMP04t18 Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. Deterministic two-way restarting automata and
    Marcus contextual grammars
    2004 Universität Kassel, 18/04, 14 pages techreport
    BibTeX:
    @techreport{JOMP04t18,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {Deterministic two-way restarting automata and
    Marcus contextual grammars}, institution = {Universität Kassel}, year = {2004}, number = {18/04}, note = {14 pages} }
    JOMP04t4 Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. On the Complexity of 2-Monotone Restarting
    Automata
    2004 Universität Kassel, 4/04 techreport
    BibTeX:
    @techreport{JOMP04t4,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {On the Complexity of 2-Monotone Restarting
    Automata}, institution = {Universität Kassel}, year = {2004}, number = {4/04} }
    JOMP04t7 Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. Deterministic Two-Way Restarting Automata Don't
    Need Auxiliary Symbols If They Are (Right-, Left-, Right-Left-) Monotone
    2004 Universität Kassel, 7/04 techreport
    BibTeX:
    @techreport{JOMP04t7,
      author = {Tomasz Jurdziński and Friedrich Otto and
    František Mráz and Martin Plátek}, title = {Deterministic Two-Way Restarting Automata Don't
    Need Auxiliary Symbols If They Are (Right-, Left-, Right-Left-) Monotone}, institution = {Universität Kassel}, year = {2004}, number = {7/04} }
    KrMr14ncma Krtek, L. & Mráz, F.
    Bensch, S.; Freund, R. & Otto, F. (Eds.)
    Two-dimensional limited context restarting
    automata
    2014 Sixth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2014, Kassel, Germany, July 28-29, 2014.
    Proceedings, Vol. 304(), books@ocg.at, Österreichische Computer Gesellschaft, pp. 147-162
    inproceedings
    BibTeX:
    @inproceedings{KrMr14ncma,
      author = {Lukáš Krtek and František Mráz},
      title = {Two-dimensional limited context restarting
    automata}, booktitle = {Sixth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2014, Kassel, Germany, July 28-29, 2014.
    Proceedings}, editor = {Suna Bensch and Rudolf Freund and Friedrich
    Otto}, publisher = {Österreichische Computer Gesellschaft}, series = {books@ocg.at}, year = {2014}, volume = {304}, pages = {147--162} }
    LopMraPla10 Lopatková, M.; Mráz, F. & Plátek, M.
    Pardubská, D. (Eds.)
    Towards a formal model of natural language
    description based on restarting automata with parallel DR-structures
    2010 Proceedings of the Conference on Theory and
    Practice of Information Technologies, ITAT 2010, Hotel Smrekovica,
    Veľká Fatra, Slovak Republic, September 21-25, 2010, Vol. 683(), CEUR Workshop Proceedings, CEUR-WS.org, pp. 25-32
    inproceedings
    BibTeX:
    @inproceedings{LopMraPla10,
      author = {Markéta Lopatková and Frantisek Mráz and
    Martin Plátek}, title = {Towards a formal model of natural language
    description based on restarting automata with parallel DR-structures}, booktitle = {Proceedings of the Conference on Theory and
    Practice of Information Technologies, ITAT 2010, Hotel Smrekovica,
    Veľká Fatra, Slovak Republic, September 21-25, 2010}, editor = {Dana Pardubská}, publisher = {CEUR-WS.org}, series = {CEUR Workshop Proceedings}, year = {2010}, volume = {683}, pages = {25--32}, url = {http://ceur-ws.org/Vol-683/paper5.pdf} }
    MMOP06ciaa Messerschmidt, H.; Mráz, F.; Otto, F. & Plátek, M.
    Ibarra, O.H. & Yen, H.-C. (Eds.)
    Correctness preservation and complexity of
    simple RL-automata
    2006 Proceedings CIAA 2006, Vol. 4094(), LNCS, Springer-Verlag, Berlin, pp. 162-172 inproceedings
    Abstract: Analysis by reduction is a method used in
    linguistics for checking the correctness of sentences of natural languages.
    This method can be modelled by restarting automata. Here we study a new type
    of restarting automaton, the so-called t-sRL-automaton, which is an
    RL-automaton that is rather restricted in that it has a window of size 1
    only, and that it works under a minimal acceptance condition. On the other
    hand, it is allowed to perform up to t rewrite (that is, delete) steps per
    cycle. We study the correctness preservation of these automata on the one
    hand, and the complexity of these automata on the other hand, establishing a
    complexity measure that is based on the description of t-sRL-automata in
    terms of so-called meta-instructions. We present a hierarchy result and we
    show that the correctness preserving nondeterministic t-sRL-automata are not
    stronger than the deterministic t-sRL-automata.
    BibTeX:
    @inproceedings{MMOP06ciaa,
      author = {Hartmut Messerschmidt and František Mráz and
    Friedrich Otto and Martin Plátek}, title = {Correctness preservation and complexity of
    simple RL-automata}, booktitle = {Proceedings CIAA 2006}, editor = {Oscar H. Ibarra and Hsu-Chun Yen}, publisher = {Springer-Verlag}, address = {Berlin}, series = {LNCS}, year = {2006}, volume = {4094}, pages = {162--172} }
    MMOP06t4 Messerschmidt, H.; Mráz, F.; Otto, F. & Plátek, M. On the descriptional complexity of simple
    RL-automata
    2006 Universität Kassel, 4/06, 13 pages techreport
    BibTeX:
    @techreport{MMOP06t4,
      author = {Hartmut Messerschmidt and František Mráz and
    Friedrich Otto and Martin Plátek}, title = {On the descriptional complexity of simple
    RL-automata}, institution = {Universität Kassel}, year = {2006}, number = {4/06}, note = {13 pages}, url = {https://kobra.bibliothek.uni-kassel.de/handle/urn:nbn:de:hebis:34-2006110215424} }
    Mra14ncma Mráz, F.
    Bensch, S.; Freund, R. & Otto, F. (Eds.)
    Limited restarting automata 2014 Sixth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2014, Kassel, Germany, July 28-29, 2014.
    Proceedings, Vol. 304(), books@ocg.at, Österreichische Computer Gesellschaft, pp. 29-56
    inproceedings
    BibTeX:
    @inproceedings{Mra14ncma,
      author = {František Mráz},
      title = {Limited restarting automata},
      booktitle = {Sixth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2014, Kassel, Germany, July 28-29, 2014.
    Proceedings}, editor = {Suna Bensch and Rudolf Freund and Friedrich
    Otto}, publisher = {Österreichische Computer Gesellschaft}, series = {books@ocg.at}, year = {2014}, volume = {304}, pages = {29--56} }
    MOP14fi Mráz, F.; Otto, F. & Plátek, M. Free Word-Order and Restarting Automata 2014 Fundam. Inform., Vol. 133(4), pp. 399-419 article
    BibTeX:
    @article{MOP14fi,
      author = {Frantisek Mráz and
    Friedrich Otto and
    Martin Plátek}, title = {Free Word-Order and Restarting Automata}, journal = {Fundam. Inform.}, year = {2014}, volume = {133}, number = {4}, pages = {399--419}, url = {http://dx.doi.org/10.3233/FI-2014-1083}, doi = {http://dx.doi.org/10.3233/FI-2014-1083} }
    MOP15ncma Mráz, F.; Otto, F. & Prusa, D. On a class of rational functions for pictures 2015 NCMA, Vol. 318(), books@ocg.at, Österreichische Computer Gesellschaft, pp. 159-176 inproceedings
    BibTeX:
    @inproceedings{MOP15ncma,
      author = {Frantisek Mráz and
    Friedrich Otto and
    Daniel Prusa}, title = {On a class of rational functions for pictures}, booktitle = {NCMA}, publisher = {Österreichische Computer Gesellschaft}, series = {books@ocg.at}, year = {2015}, volume = {318}, pages = {159--176} }
    M89slo Mráz, F.
    Bartošek, M. (Eds.)
    Paralelné algoritmy redukcie koneČných
    automatov
    1989 SOFSEM'89, Ždiar, Vysoké Tatry, pp. 49-52 inproceedings
    BibTeX:
    @inproceedings{M89slo,
      author = {František Mráz},
      title = {Paralelné algoritmy redukcie koneČných
    automatov}, booktitle = {SOFSEM'89}, editor = {Miroslav Bartošek}, address = {Ždiar, Vysoké Tatry}, year = {1989}, pages = {49--52} }
    M00abbr Mráz, F.
    Boldt, O. & Jürgensen, H. (Eds.)
    Lookahead Hierarchies of Restarting Automata 2000 Pre-Proceedings of DCAGRS 2000 Descriptional
    Complexity of Automata, Grammars and Related Structures, Dept. of Comp. Science, The University of
    Western Ontario, London, Canada, pp. 1-15, As Rep. No. 255. Ext. version of teM01.
    inproceedings
    BibTeX:
    @inproceedings{M00abbr,
      author = {František Mráz},
      title = {Lookahead Hierarchies of Restarting Automata},
      booktitle = {Pre-Proceedings of DCAGRS 2000 Descriptional
    Complexity of Automata, Grammars and Related Structures}, editor = {O. Boldt and H. Jürgensen}, publisher = {Dept. of Comp. Science, The University of
    Western Ontario}, address = {London, Canada}, year = {2000}, pages = {1--15}, note = {As Rep. No. 255. Ext. version of teM01.} }
    M01 Mráz, F. Lookahead Hierarchies of Restarting Automata 2001 Journal of Automata, Languages and
    Combinatorics, Vol. 6(4), pp. 493-506
    article
    BibTeX:
    @article{M01,
      author = {František Mráz},
      title = {Lookahead Hierarchies of Restarting Automata},
      journal = {Journal of Automata, Languages and
    Combinatorics}, year = {2001}, volume = {6}, number = {4}, pages = {493--506} }
    M01phd Mráz, F. Forgetting and restarting automata 2001 , Prague School: Charles University phdthesis 
    Abstract: 
    BibTeX:
    @phdthesis{M01phd,
      author = {František Mráz},
      title = {Forgetting and restarting automata},
      address = {Prague},
      school = {Charles University},
      year = {2001}
    }
    					
    MrOt14sofsem Mráz, F. & Otto, F.
    Geffert, V.; Preneel, B.; Rovan, B.; Stuller, J. & Tjoa, A.M. (Eds.)
    Ordered Restarting Automata for Picture
    Languages
    2014 SOFSEM 2014: Theory and Practice of Computer
    Science, Vol. 8327(), LNCS, Springer, pp. 431-442
    inproceedings
    BibTeX:
    @inproceedings{MrOt14sofsem,
      author = {František Mráz and Friedrich Otto},
      title = {Ordered Restarting Automata for Picture
    Languages}, booktitle = {SOFSEM 2014: Theory and Practice of Computer
    Science}, editor = {Viliam Geffert and Bart Preneel and Branislav
    Rovan and Julius Stuller and A Min Tjoa}, publisher = {Springer}, series = {LNCS}, year = {2014}, volume = {8327}, pages = {431--442} }
    MO03TT Mráz, F. & Otto, F.
    Holzer, M. (Eds.)
    Hierarchies of weakly monotone restarting
    automata
    2003 Workshop ``Petrinetze'' und 13. Theorietag
    ``Automaten und Formale Sprachen'', Institut für Informatik, Technishe
    Universität München, pp. 83-89
    incollection
    BibTeX:
    @incollection{MO03TT,
      author = {František Mráz and Friedrich Otto},
      title = {Hierarchies of weakly monotone restarting
    automata}, booktitle = {Workshop ``Petrinetze'' und 13. Theorietag
    ``Automaten und Formale Sprachen''}, editor = {Markus Holzer}, publisher = {Institut für Informatik, Technishe
    Universität München}, year = {2003}, pages = {83--89} }
    MraOtt13 Mráz, F. & Otto, F.
    Konstantinidis, S. (Eds.)
    Lambda-Confluence Is Undecidable for Clearing
    Restarting Automata
    2013 Implementation and Application of Automata, Vol. 7982(), Lecture Notes in Computer Science, Springer Berlin Heidelberg, Halifax, NS, pp. 256-267 inproceedings clearing restarting automaton; limited context
    restarting automaton; factor-erasing string-rewriting system;
    ?-confluence
    Abstract: Clearing restarting automata are based on
    contextual rewriting. A word w is accepted by an automaton of this type if
    there is a computation that reduces the word w to the empty word ? by a
    finite sequence of rewritings. Accordingly, the word problem for a clearing
    restarting automaton can be solved nondeterministically in quadratic time.
    If, however, the contextual rewritings happen to be ?-confluent, that is,
    confluent on the congruence class of the empty word, then the word problem
    can be solved deterministically in linear time. Here we show that,
    unfortunately, ?-confluence is not even recursively enumerable for clearing
    restarting automata. This follows from the fact that ?-confluence is not
    recursively enumerable for finite factor-erasing string-rewriting systems. ©
    2013 Springer-Verlag.
    BibTeX:
    @inproceedings{MraOtt13,
      author = {Mráz, František and Otto, Friedrich},
      title = {Lambda-Confluence Is Undecidable for Clearing
    Restarting Automata}, booktitle = {Implementation and Application of Automata}, editor = {Konstantinidis, Stavros}, publisher = {Springer Berlin Heidelberg}, address = {Halifax, NS}, series = {Lecture Notes in Computer Science}, year = {2013}, volume = {7982}, pages = {256--267}, doi = {http://dx.doi.org/10.1007/978-3-642-39274-0_23} }
    MO05 Mráz, F. & Otto, F. Hierarchies of weakly monotone restarting
    automata
    2005 RAIRO - Theoretical Informatics and
    Applications, Vol. 39(2), pp. 325-342
    article
    Abstract: It is known that the weakly monotone restarting
    automata accept exactly the growing context-sensitive languages. We
    introduce a measure on the degree of weak monotonicity and show that the
    language classes obtained in this way form strict hierarchies for the
    various types of deterministic and nondeterministic restarting automata
    without auxiliary symbols.
    BibTeX:
    @article{MO05,
      author = {František Mráz and Friedrich Otto},
      title = {Hierarchies of weakly monotone restarting
    automata}, journal = {RAIRO -- Theoretical Informatics and
    Applications}, year = {2005}, volume = {39}, number = {2}, pages = {325--342} }
    MO03t Mráz, F. & Otto, F. Hierarchies of weakly monotone restarting
    automata
    2003 Fachbereich Mathematik/Informatik,
    Universität Kassel, 8/03
    techreport
    BibTeX:
    @techreport{MO03t,
      author = {František Mráz and Friedrich Otto},
      title = {Hierarchies of weakly monotone restarting
    automata}, institution = {Fachbereich Mathematik/Informatik,
    Universität Kassel}, year = {2003}, number = {8/03} }
    MOP07mcu Mráz, F.; Otto, F. & Plátek, M.
    Durand-Lose, J.O. & Margenstern, M. (Eds.)
    Hierarchical Relaxations of the Correctness
    Preserving Property for Restarting Automata
    2007 Proceedings MCU 2007, Vol. 4664(), LNCS, Springer, Berlin, pp. 230-241 inproceedings
    Abstract: A nondeterministic restarting automaton M is
    said to be (strongly) correctness preserving, if, for each cycle u
    M^c v, the word v belongs to the complete language L_C(M) accepted by
    M, if the word u does. Here, in order to differentiate between
    nondeterministic restarting automata that are correctness preserving and
    nondeterministic restarting automata in general we introduce two gradual
    relaxations of the correctness preserving property. These relaxations lead
    to an infinite twodimensional hierarchy of classes of languages with
    membership problems that are decidable in polynomial time.
    BibTeX:
    @inproceedings{MOP07mcu,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Hierarchical Relaxations of the Correctness
    Preserving Property for Restarting Automata}, booktitle = {Proceedings MCU 2007}, editor = {Jerome Olivier Durand-Lose and Maurice
    Margenstern}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2007}, volume = {4664}, pages = {230--241} }
    MOP05tagi Mráz, F.; Otto, F. & Plátek, M.
    Fernau, H. (Eds.)
    Learning analysis by reduction from positive
    data
    2005 Theoretical Aspects of Grammar Induction, Wilhem-Schickard-Institut für Informatik,
    University Tübingen, pp. 22-25, WSI-2005-14
    incollection
    BibTeX:
    @incollection{MOP05tagi,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Learning analysis by reduction from positive
    data}, booktitle = {Theoretical Aspects of Grammar Induction}, editor = {H.~Fernau}, publisher = {Wilhem-Schickard-Institut für Informatik,
    University Tübingen}, year = {2005}, pages = {22-25}, note = {WSI-2005-14} }
    MOP05tt Mráz, F.; Otto, F. & Plátek, M.
    Fernau, H. (Eds.)
    Parametrized syntactic analysis by freely
    rewriting restarting automata
    2005 15. Theorietag der GI Fachgruppe 0.1.5 Automaten
    und Formalen Sprachen, Wilhem-Schickard-Institut für Informatik,
    University Tübingen, pp. 45-48, WSI-2005-16
    incollection
    BibTeX:
    @incollection{MOP05tt,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Parametrized syntactic analysis by freely
    rewriting restarting automata}, booktitle = {15. Theorietag der GI Fachgruppe 0.1.5 Automaten
    und Formalen Sprachen}, editor = {H.~Fernau}, publisher = {Wilhem-Schickard-Institut für Informatik,
    University Tübingen}, year = {2005}, pages = {45--48}, note = {WSI-2005-16} }
    MOP06dlt Mráz, F.; Otto, F. & Plátek, M.
    Ibarra, O.H. & Dang, Z. (Eds.)
    On the gap-complexity of simple RL-automata 2006 Developments in Language Theory, Proceedings DLT
    2006, Vol. 4036(), LNCS, Springer, Berlin, pp. 83-94
    inproceedings
    Abstract: Analysis by reduction is a method used in
    linguistics for checking the correctness of sentences of natural languages.
    This method is modelled by restarting automata. Here we introduce and study
    a new type of restarting automaton, the so-called t-sRL-automaton, which is
    an RL-automaton that is rather restricted in that it has a window of size 1
    only, and that it works under a minimal acceptance condition. On the other
    hand, it is allowed to perform up to t rewrite (that is, delete) steps per
    cycle. Here we study the gap-complexity of these automata. The membership
    problem for a language that is accepted by a t-sRLautomaton with a bounded
    number of gaps can be solved in polynomial time. On the other hand,
    t-sRL-automata with an unbounded number of gaps accept NP-complete
    languages.
    BibTeX:
    @inproceedings{MOP06dlt,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {On the gap-complexity of simple RL-automata}, booktitle = {Developments in Language Theory, Proceedings DLT
    2006}, editor = {Oscar H. Ibarra and Zhe Dang}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2006}, volume = {4036}, pages = {83--94} }
    MOP07lataprep Mráz, F.; Otto, F. & Plátek, M.
    Loos, R.; Fazekas, S.Z. & Martín-Vide, C. (Eds.)
    Free Word-Order and Restarting Automata 2007 Pre-proceedings of LATA 2007, Universitat Rovira I Virgili, Tarragona, pp. 425-436 inproceedings
    Abstract: In natural languages with a high degree of
    word-order freedom syntactic phenomena like dependencies (subordinations) or
    valences do not depend on the word-order (or on the individual positions of
    the individual words). This means that some permutations of sentences of
    these languages are in some (important) sense syntactically equivalent. Here
    we study this phenomenon in a formal way. Various types of jmonotonicity for
    restarting automata can serve as parameters for the degree of word-order
    freedom and for the complexity of word-order in sentences (languages). Here
    we combine two types of parameters on computations of restarting automata:
    the degree of j-monotonicity, and the number of rewrites per cycle. We study
    these notions formally in order to obtain an adequate tool for modelling and
    comparing formal descriptions of (natural) languages with di.erent degrees
    of word-order freedom and word-order complexity.
    BibTeX:
    @inproceedings{MOP07lataprep,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Free Word-Order and Restarting Automata}, booktitle = {Pre-proceedings of LATA 2007}, editor = {Remco Loos and Szilárd Zsolt Fazekas and Carlos
    Martín-Vide}, publisher = {Universitat Rovira I Virgili}, address = {Tarragona}, year = {2007}, pages = {425--436} }
    MOP06icgi Mráz, F.; Otto, F. & Plátek, M.
    Sakakibara, Y.; Kobayashi, S.; Sato, K.; Nishino, T. & Tomita, E. (Eds.)
    Learning analysis by reduction from positive
    data
    2006 Proceedings ICGI 2006, Vol. 4201(), LNCS, Springer, Berlin, pp. 125-136 inproceedings
    Abstract: Analysis by reduction is a linguistically
    motivated method for checking correctness of a sentence. It can be modelled
    by restarting automata. In this paper we propose a method for learning
    restarting automata which are strictly locally testable (SLT-R-automata).
    The method is based on the concept of identification in the limit from
    positive examples only. Also we characterize the class of languages accepted
    by SLT-R-automata with respect to the Chomsky hierarchy.
    BibTeX:
    @inproceedings{MOP06icgi,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Learning analysis by reduction from positive
    data}, booktitle = {Proceedings ICGI 2006}, editor = {Y.~Sakakibara and S.~Kobayashi and K.~Sato and
    T.~Nishino and E.~Tomita}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2006}, volume = {4201}, pages = {125--136} }
    MOP03ITAT Mráz, F.; Otto, F. & Plátek, M.
    Vojtáš, P. (Eds.)
    Restarting automata and combinations of
    constraints
    2003 Proc. of ITAT 2003, pp. 83-91, P.~J.~šafárik University inproceedings
    BibTeX:
    @inproceedings{MOP03ITAT,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Restarting automata and combinations of
    constraints}, booktitle = {Proc. of ITAT 2003}, editor = {Peter Vojtáš}, organization = {P.~J.~šafárik University}, year = {2003}, pages = {83--91} }
    MOP09 Mráz, F.; Otto, F. & Plátek, M. The Degree of Word-Expansion of Lexicalized
    RRWW-Automata - A New Measure for The Degree of Nondeterminism of
    (Context-Free) Languages
    2009 Theoretical Computer Science, Vol. 410(37), pp. 3530-3538 article
    Abstract: Restarting automata can be seen as analytical
    variants of classical automata as well as of regulated rewriting systems. We
    study a measure for the degree of nondeterminism of (context-free) languages
    in terms of deterministic restarting automata that are (strongly)
    lexicalized. This measure is based on the number of auxiliary symbols
    (categories) used for recognizing a language as the projection of its
    characteristic language onto its input alphabet. This type of recognition is
    typical for analysis by reduction, a method used in linguistics for the
    creation and verification of formal descriptions of natural languages. Our
    main results establish a hierarchy of classes of context-free languages and
    two hierarchies of classes of non-context-free languages that are based on
    the expansion factor of a language.
    BibTeX:
    @article{MOP09,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {The Degree of Word-Expansion of Lexicalized
    RRWW-Automata - A New Measure for The Degree of Nondeterminism of
    (Context-Free) Languages}, journal = {Theoretical Computer Science}, year = {2009}, volume = {410}, number = {37}, pages = {3530--3538}, url = {http://198.81.200.2/science/article/B6V1G-4VXB90X-3/2/c2cdd1e1b5138171c33398f7e2d2a5ad}, doi = {http://dx.doi.org/10.1016/j.tcs.2009.03.017} }
    MOP07ciaatcsTR Mráz, F.; Otto, F. & Plátek, M. The Degree of Word-Expansion of Lexicalized
    RRWW-Automata - A New Measure for The Degree of Nondeterminism of
    (Context-Free) Languages
    2007 Fachbereich Elektrotechnik/Informatik,
    Universität Kassel, 5/2007
    techreport
    Abstract: Restarting automata can be seen as analytical
    variants of classical automata as well as of regulated rewriting systems. We
    study a measure for the degree of nondeterminism of (context-free) languages
    in terms of deterministic restarting automata that are (strongly)
    lexicalized. This measure is based on the number of auxiliary symbols
    (categories) used for recognizing a language as the projection of its
    characteristic language onto its input alphabet. This type of recognition is
    typical for analysis by reduction, a method used in linguistics for the
    creation and verification of formal descriptions of natural languages. Our
    main results establish a hierarchy of classes of context-free languages and
    two hierarchies of classes of non-context-free languages that are based on
    the expansion factor of a language.
    BibTeX:
    @techreport{MOP07ciaatcsTR,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {The Degree of Word-Expansion of Lexicalized
    RRWW-Automata - A New Measure for The Degree of Nondeterminism of
    (Context-Free) Languages}, institution = {Fachbereich Elektrotechnik/Informatik,
    Universität Kassel}, year = {2007}, number = {5/2007}, url = {https://kobra.bibliothek.uni-kassel.de/handle/
    urn:nbn:de:hebis:34-2007112619730} }
    MOP06t2 Mráz, F.; Otto, F. & Plátek, M. On the Gap-Complexity of Simple RL-Automata 2006 Universität Kassel, 2/06, 13 pages techreport
    BibTeX:
    @techreport{MOP06t2,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {On the Gap-Complexity of Simple RL-Automata}, institution = {Universität Kassel}, year = {2006}, number = {2/06}, note = {13 pages}, url = {https://kobra.bibliothek.uni-kassel.de/handle/urn:nbn:de: hebis: 34
    -2006053112600} }
    MOP05t5 Mráz, F.; Otto, F. & Plátek, M. Degrees of Free Word-Order and Freely Rewriting
    Restarting Automata
    2005 Universität Kassel, 5/05 techreport
    BibTeX:
    @techreport{MOP05t5,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Degrees of Free Word-Order and Freely Rewriting
    Restarting Automata}, institution = {Universität Kassel}, year = {2005}, number = {5/05} }
    MOP05t7 Mráz, F.; Otto, F. & Plátek, M. Learning analysis by reduction from positive
    data
    2005 Universität Kassel, 7/05 techreport
    BibTeX:
    @techreport{MOP05t7,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek}, title = {Learning analysis by reduction from positive
    data}, institution = {Universität Kassel}, year = {2005}, number = {7/05} }
    MOPJ06 Mráz, F.; Otto, F.; Plátek, M. & Jurdziński, T. Marcus t-contextual grammars and cut hierarchies
    and monotonicity for restarting automata
    2006 Theoretical Computer Science, Vol. 366(3), pp. 272-296 article
    Abstract: The t -contextual grammars are generalizations
    of Marcus contextual grammars, which insert t contexts in each derivation
    step. If the selection mappings are regular and satisfy an additional
    locality restriction, then these grammars correspond in their expressive
    power to restarting automata with cut-index t . In the first part of the
    paper classes of languages are studied that are accepted by certain types of
    restarting automata with limited cut-index. As already R-automata with
    cut-index 1 accept NP-complete languages, additional restrictions in the
    form of certain monotonicity conditions are also considered.Without the
    locality restriction t-contextual grammars with regular selection correspond
    to t -RR-automata with cut-index one. These areRR-automata that are allowed
    to perform up to t deletion operations in each cycle that each delete a
    single factor only. In the second part of the paper the expressive power of
    these automata is studied, where the focus is on the special case that
    certain monotonicity conditions are satisfied.
    BibTeX:
    @article{MOPJ06,
      author = {František Mráz and Friedrich Otto and Martin
    Plátek and Tomasz Jurdziński}, title = {Marcus t-contextual grammars and cut hierarchies
    and monotonicity for restarting automata}, journal = {Theoretical Computer Science}, year = {2006}, volume = {366}, number = {3}, pages = {272--296} }
    MP95 Mráz, F. & Plátek, M. Erasing Automata Recognize More Than
    Context-Free Languages
    1995 Acta Mathematica et Informatica Universitatis
    Ostraviensis, Vol. 3(), pp. 77-85
    article
    BibTeX:
    @article{MP95,
      author = {František Mráz and Martin Plátek},
      title = {Erasing Automata Recognize More Than
    Context-Free Languages}, journal = {Acta Mathematica et Informatica Universitatis
    Ostraviensis}, year = {1995}, volume = {3}, pages = {77--85} }
    MP93 Mráz, F. & Plátek, M. A Remark About Forgetting Automata 1993 SOFSEM'93, Hrdoňov, Czech Republic, pp. 63-66 inproceedings
    BibTeX:
    @inproceedings{MP93,
      author = {František Mráz and Martin Plátek},
      title = {A Remark About Forgetting Automata},
      booktitle = {SOFSEM'93},
      address = {Hrdoňov, Czech Republic},
      year = {1993},
      pages = {63--66}
    }
    					
    MP91abbr Mráz, F. & Plátek, M. Erasing Automata Recognize More Than
    Context-Free Languages
    1991 SOFSEM'91, Jasná pod Chopkom, pp. 251-255 inproceedings
    BibTeX:
    @inproceedings{MP91abbr,
      author = {František Mráz and Martin Plátek},
      title = {Erasing Automata Recognize More Than
    Context-Free Languages}, booktitle = {SOFSEM'91}, address = {Jasná pod Chopkom}, year = {1991}, pages = {251--255} }
    MP91p Mráz, F. & Plátek, M. Erasing Automata Recognize More Than
    Context-Free Languages
    1991 Department of Computer Science, 90, Charles University Prague, 7 pages techreport
    BibTeX:
    @techreport{MP91p,
      author = {František Mráz and Martin Plátek},
      title = {Erasing Automata Recognize More Than
    Context-Free Languages}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1991}, number = {90}, note = {7 pages} }
    MPJV97 Mráz, F.; Plátek, M.; Jančar, P. & Vogel, J.
    Plášil, F. & Jeffery, K.G. (Eds.)
    Monotonic Rewriting Automata with a Restart
    Operation
    1997 SOFSEM'97, Vol. 1338(), LNCS, Springer, Milovy, Czech Republic, pp. 505-512 inproceedings
    BibTeX:
    @inproceedings{MPJV97,
      author = {František Mráz and Martin Plátek and Petr
    Jančar and Jörg Vogel}, title = {Monotonic Rewriting Automata with a Restart
    Operation}, booktitle = {SOFSEM'97}, editor = {František Plášil and Keith G. Jeffery}, publisher = {Springer}, address = {Milovy, Czech Republic}, series = {LNCS}, year = {1997}, volume = {1338}, pages = {505--512} }
    MPJV97p Mráz, F.; Plátek, M.; Jančar, P. & Vogel, J. Monotonic Rewriting Automata with a Restart
    Operation
    1997 Department of Computer Science, 97/6, Charles University Prague, 8 pages techreport
    BibTeX:
    @techreport{MPJV97p,
      author = {František Mráz and Martin Plátek and Petr
    Jančar and Jörg Vogel}, title = {Monotonic Rewriting Automata with a Restart
    Operation}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1997}, number = {97/6}, note = {8 pages} }
    MPJu07ijfcs Mráz, F.; Plátek, M. & Jurdziński, T. Ambiguity by restarting automata 2007 International Journal of Foundations of Computer
    Science, Vol. 18(6), pp. 1343-1352
    article
    BibTeX:
    @article{MPJu07ijfcs,
      author = {František Mráz and Martin Plátek and Tomasz
    Jurdziński}, title = {Ambiguity by restarting automata}, journal = {International Journal of Foundations of Computer
    Science}, year = {2007}, volume = {18}, number = {6}, pages = {1343--1352} }
    MPO07ciaa Mráz, F.; Plátek, M. & Otto, F.
    Holub, J. & Žďárek, J. (Eds.)
    A Measure for The Degree of Nondeterminism of
    Context-free Languages
    2007 Proceedings of CIAA 2007, LNCS, Springer, Berlin, pp. 192-202 inproceedings
    Abstract: Restarting automata can be seen as analytical
    variants of classical automata as well as of regulated rewriting systems. We
    study some measures for the degree of nondeterminism of (context-free)
    languages in terms of lexicalized deterministic restarting automata. These
    measures are based on the number of auxiliary symbols (categories) used for
    recognizing a language as the projection of its characteristic language onto
    its input alphabet. This type of recognition is typical for analysis by
    reduction, a method used in linguistics for the creation and verification of
    formal descriptions of natural languages. Our main results establish a
    two-dimensional hierarchy of classes of (context-free) languages based on
    the expansion factor of a language and on the number of different auxiliary
    symbols available in the underlying characteristic language.
    BibTeX:
    @inproceedings{MPO07ciaa,
      author = {František Mráz and Martin Plátek and Friedrich
    Otto}, title = {A Measure for The Degree of Nondeterminism of
    Context-free Languages}, booktitle = {Proceedings of CIAA 2007}, editor = {Jan Holub and Jan Žďárek}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2007}, pages = {192--202} }
    MPO07ciaapre Mráz, F.; Plátek, M. & Otto, F.
    Holub, J. & Žďárek, J. (Eds.)
    A Measure for The Degree of Nondeterminism of
    Context-free Languages
    2007 Pre-proceedings of CIAA 2007, Czech Technical University in Prague, pp. 161-169 inproceedings
    BibTeX:
    @inproceedings{MPO07ciaapre,
      author = {František Mráz and Martin Plátek and Friedrich
    Otto}, title = {A Measure for The Degree of Nondeterminism of
    Context-free Languages}, booktitle = {Pre-proceedings of CIAA 2007}, editor = {Jan Holub and Jan Žďárek}, publisher = {Czech Technical University in Prague}, year = {2007}, pages = {161--169} }
    MPP98 Mráz, F.; Plátek, M. & Procházka, M.
    Bozapalidis, S. (Eds.)
    Deleting Automata with a Restart Operation and
    Marcus Grammars
    1998 Developments in Language Theory, 1997, University of Thessaloniki, Thessaloniki, Greece, pp. 329-342 inproceedings
    BibTeX:
    @inproceedings{MPP98,
      author = {František Mráz and Martin Plátek and Martin
    Procházka}, title = {Deleting Automata with a Restart Operation and
    Marcus Grammars}, booktitle = {Developments in Language Theory, 1997}, editor = {S. Bozapalidis}, publisher = {University of Thessaloniki}, address = {Thessaloniki, Greece}, year = {1998}, pages = {329--342} }
    MPPk00 Mráz, F.; Plátek, M. & Procházka, M.
    C. Martín-Vide, V.M. (Eds.)
    On special forms of restarting automata 2000 Words, sequences, grammars, languages: where
    biology, computer science, linguistics and mathematics meet I, Kluwer, Dordrecht, pp. 149-160
    incollection
    BibTeX:
    @incollection{MPPk00,
      author = {František Mráz and Martin Plátek and Martin
    Procházka}, title = {On special forms of restarting automata}, booktitle = {Words, sequences, grammars, languages: where
    biology, computer science, linguistics and mathematics meet I}, editor = {C. Martín-Vide, V. Mitrana}, publisher = {Kluwer}, address = {Dordrecht}, year = {2000}, pages = {149--160} }
    MPP00 Mráz, F.; Plátek, M. & Procházka, M.
    Martín-Vide, C. & Păun, G. (Eds.)
    Restarting Automata, Deleting, and Marcus
    Grammars
    2000 Recent topics in mathematical and computational
    linguistics, The Publishing House of the Romanian Academy, Bucharest, pp. 218-233
    incollection
    BibTeX:
    @incollection{MPP00,
      author = {František Mráz and Martin Plátek and Martin
    Procházka}, title = {Restarting Automata, Deleting, and Marcus
    Grammars}, booktitle = {Recent topics in mathematical and computational
    linguistics}, editor = {C. Martín-Vide and Gh. Păun}, publisher = {The Publishing House of the Romanian Academy}, address = {Bucharest}, year = {2000}, pages = {218--233} }
    MPP99 Mráz, F.; Plátek, M. & Procházka, M. On Special Forms of Restarting Automata 1999 Grammars, Vol. 2(3), pp. 223-233 article
    BibTeX:
    @article{MPP99,
      author = {František Mráz and Martin Plátek and Martin
    Procházka}, title = {On Special Forms of Restarting Automata}, journal = {Grammars}, year = {1999}, volume = {2}, number = {3}, pages = {223--233} }
    MPP97p Mráz, F.; Plátek, M. & Procházka, M. Deleting Automata with a Restart Operation and
    Marcus Grammars
    1997 Department of Computer Science, 97/3, Charles University Prague, 11 pages techreport
    BibTeX:
    @techreport{MPP97p,
      author = {František Mráz and Martin Plátek and Martin
    Procházka}, title = {Deleting Automata with a Restart Operation and
    Marcus Grammars}, address = {Charles University Prague}, institution = {Department of Computer Science}, year = {1997}, number = {97/3}, note = {11 pages} }
    MM01 Mrázová, I. & Mráz, F.
    Andrejková, G. & KrajČi, S. (Eds.)
    Data Mining and Neural Networks 2001 ITAT´2001: Information Technologies --
    Applications and Theory, Dept. of Comp. Science, Pavol Jozef šafárik
    University, Košice, Slovakia, pp. 41-52
    inproceedings
    BibTeX:
    @inproceedings{MM01,
      author = {Iveta Mrázová and František Mráz},
      title = {Data Mining and Neural Networks},
      booktitle = {ITAT´2001: Information Technologies --
    Applications and Theory}, editor = {Gabriela Andrejková and Stanislav KrajČi}, publisher = {Dept. of Comp. Science, Pavol Jozef šafárik
    University}, address = {Košice, Slovakia}, year = {2001}, pages = {41--52} }
    MMRP08 Mrázová, I.; Mráz, F.; Reitermanová, Z. & PetříČek, M.
    et al., C.H.D. (Eds.)
    Phonetic Search in Foreign Texts 2008 Intelligent Engineering Systems though
    Artificial Neural Networks (Proc. of ANNIE 2008, Nov. 9-12, St. Louis,
    USA), ASME Press Series, pp. 533-540
    inproceedings
    BibTeX:
    @inproceedings{MMRP08,
      author = {Iveta Mrázová and František Mráz and Zuzana
    Reitermanová and Martin PetříČek}, title = {Phonetic Search in Foreign Texts}, booktitle = {Intelligent Engineering Systems though
    Artificial Neural Networks (Proc. of ANNIE 2008, Nov. 9-12, St. Louis,
    USA)}, editor = {C. H. Dagli et al.}, series = {ASME Press Series}, year = {2008}, pages = {533--540} }
    OtCeMr14rairo Otto, F.; Černo, P. & Mràz, F. On the classes of languages accepted by limited
    context restarting automata
    2014 RAIRO - Theor. Inf. and Applic., Vol. 48(1), pp. 61-84 article
    BibTeX:
    @article{OtCeMr14rairo,
      author = {Friedrich Otto and Peter Černo and František
    Mràz}, title = {On the classes of languages accepted by limited
    context restarting automata}, journal = {RAIRO - Theor. Inf. and Applic.}, year = {2014}, volume = {48}, number = {1}, pages = {61--84}, url = {http://dx.doi.org/10.1051/ita/2014001}, doi = {http://dx.doi.org/10.1051/ita/2014001} }
    OCM12 Otto, F.; Černo, P. & Mráz, F.
    Freund, R.; Holzer, M.; Truthe, B. & Ultes-Nitsche, U. (Eds.)
    Limited Context Restarting Automata and
    McNaughton Families of Languages
    2012 Fourth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2012, Fribourg, Switzerland, August 23-24,
    2012. Proceedings, Vol. 290(), books@ocg.at, Österreichische Computer Gesellschaft, pp. 165-180
    inproceedings
    BibTeX:
    @inproceedings{OCM12,
      author = {Friedrich Otto and Peter Černo and František
    Mráz}, title = {Limited Context Restarting Automata and
    McNaughton Families of Languages}, booktitle = {Fourth Workshop on Non-Classical Models for
    Automata and Applications - NCMA 2012, Fribourg, Switzerland, August 23-24,
    2012. Proceedings}, editor = {Rudolf Freund and Markus Holzer and Bianca
    Truthe and Ulrich Ultes-Nitsche}, publisher = {Österreichische Computer Gesellschaft}, series = {books@ocg.at}, year = {2012}, volume = {290}, pages = {165-180} }
    OCM12tt Otto, F.; Černo, P. & Mráz, F.
    Mráz, F. (Eds.)
    Limited Context Restarting Automata and
    McNaughton Families of Languages
    2012 Proceedings of the 22nd Theorietag Automata and
    Formal Languages (Charles University, Prague), Matfyzpress, Prague, pp. 109-114
    inproceedings
    BibTeX:
    @inproceedings{OCM12tt,
      author = {Friedrich Otto and Peter Černo and František
    Mráz}, title = {Limited Context Restarting Automata and
    McNaughton Families of Languages}, booktitle = {Proceedings of the 22nd Theorietag Automata and
    Formal Languages (Charles University, Prague)}, editor = {František Mráz}, publisher = {Matfyzpress}, address = {Prague}, year = {2012}, pages = {109--114} }
    OM15tcs Otto, F. & Mráz, F. Lambda-confluence for context rewriting
    systems
    2015 Theor. Comput. Sci., Vol. 578(), pp. 88-99 article
    BibTeX:
    @article{OM15tcs,
      author = {Friedrich Otto and
    Frantisek Mráz}, title = {Lambda-confluence for context rewriting
    systems}, journal = {Theor. Comput. Sci.}, year = {2015}, volume = {578}, pages = {88--99} }
    OtMr14lata Otto, F. & Mráz, F.
    Dediu, A.H.; Martín-Vide, C.; Sierra-Rodríguez, J.L. & Truthe, B. (Eds.)
    Extended Two-Way Ordered Restarting Automata for
    Picture Languages
    2014 Language and Automata Theory and Applications -
    8th International Conference, LATA 2014, Vol. 8370(), LNCS, Springer, pp. 541-552
    inproceedings
    BibTeX:
    @inproceedings{OtMr14lata,
      author = {Friedrich Otto and František Mráz},
      title = {Extended Two-Way Ordered Restarting Automata for
    Picture Languages}, booktitle = {Language and Automata Theory and Applications -
    8th International Conference, LATA 2014}, editor = {Adrian Horia Dediu and Carlos Martín-Vide and
    José Luis Sierra-Rodríguez and Bianca Truthe}, publisher = {Springer}, series = {LNCS}, year = {2014}, volume = {8370}, pages = {541--552} }
    OttMra15actinf Otto, F. & Mráz, F. Deterministic ordered restarting automata for
    picture languages
    2015 Acta Informatica, Vol. 52(), pp. 593-623 article
    BibTeX:
    @article{OttMra15actinf,
      author = {Otto, F. and Mráz, F.},
      title = {Deterministic ordered restarting automata for
    picture languages}, journal = {Acta Informatica}, year = {2015}, volume = {52}, pages = {593--623}, doi = {http://dx.doi.org/10.1007/s00236-015-0230-5} }
    OMP05 Otto, F.; Mráz, F. & Plátek, M.
    Ésik, Z. & Fülöp, Z. (Eds.)
    Degrees of monotonicity and Marcus t-contextual
    grammars
    2005 Automata and Formal Languages, Proceedings AFL
    2005, Szeged, pp. 249-262, Institute of Informatics, University of
    Szeged
    inproceedings
    BibTeX:
    @inproceedings{OMP05,
      author = {Friedrich Otto and František Mráz and Martin
    Plátek}, title = {Degrees of monotonicity and Marcus t-contextual
    grammars}, booktitle = {Automata and Formal Languages, Proceedings AFL
    2005}, editor = {Z.~Ésik and Z.~Fülöp}, address = {Szeged}, organization = {Institute of Informatics, University of
    Szeged}, year = {2005}, pages = {249--262} }
    OPM10dlt Otto, F.; Plátek, M. & Mráz, F.
    Gao, Y.; Lu, H.; Seki, S. & Yu, S. (Eds.)
    On Lexicalized Well-Behaved Restarting Automata
    That Are Monotone
    2010 Developments in Language Theory, Vol. 6224(), LNCS, Springer, Berlin, pp. 352-363, 10.1007/978-3-642-14455-432 inproceedings
    Abstract: We introduce lexicalized well-behaved restarting
    automata as a model of the gradual lexicalized syntactic disambiguation of
    natural languages. This model presents a non-correctness preserving
    counter-part to the (correctness preserving) models of analysis by reduction
    of natural languages. We study two types of gradual relaxations of the
    correctness preserving property for monotone automata of this type. They
    lead to two infinite hierarchies of language classes. The basic levels of
    these hierarchies coincide with the class LRR of left-to-right regular
    languages, and the hierarchies exhaust the class of context-free
    languages.
    BibTeX:
    @inproceedings{OPM10dlt,
      author = {Otto, Friedrich and Plátek, Martin and Mráz,
    František}, title = {On Lexicalized Well-Behaved Restarting Automata
    That Are Monotone}, booktitle = {Developments in Language Theory}, editor = {Gao, Yuan and Lu, Hanlin and Seki, Shinnosuke
    and Yu, Sheng}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2010}, volume = {6224}, pages = {352--363}, note = {10.1007/978-3-642-14455-432}, url = {http://dx.doi.org/10.1007/978-3-642-14455-4_32} }
    PaMP11 Pardubská, D.; Mráz, F. & Plátek, M. Translations by Regulated Parallel Communicating
    Grammar Systems
    2011 Journal of automata, languages and
    combinatorics, Vol. 16(2--4), pp. 215-251
    article
    BibTeX:
    @article{PaMP11,
      author = {Dana Pardubská and František Mráz and
    Martin~Plátek}, title = {Translations by Regulated Parallel Communicating
    Grammar Systems}, journal = {Journal of automata, languages and
    combinatorics}, year = {2011}, volume = {16}, number = {2--4}, pages = {215--251} }
    PM01 Plátek, M. & Mráz, F.
    Dassow, J. & Wotschke, D. (Eds.)
    Degrees of (non)monotonicity of
    RRWW-automata
    2001 Pre-Proceedings of DCAGRS 2001 Descriptional
    Complexity of Automata, Grammars and Related Structures, Fakultät für informatik, Otto-von-Guericke
    Universität, Magdeburg, pp. 159-165, As Report No. 16
    inproceedings
    BibTeX:
    @inproceedings{PM01,
      author = {Martin Plátek and František Mráz},
      title = {Degrees of (non)monotonicity of
    RRWW-automata}, booktitle = {Pre-Proceedings of DCAGRS 2001 Descriptional
    Complexity of Automata, Grammars and Related Structures}, editor = {Jürgen Dassow and Detlef Wotschke}, publisher = {Fakultät für informatik, Otto-von-Guericke
    Universität, Magdeburg}, year = {2001}, pages = {159--165}, note = {As Report No. 16} }
    PML10ncma Plátek, M.; Mráz, F. & Lopatková, M.
    Bordihn, H.; Freund, R.; Hinze, T.; Holzer, M.; Kutrib, M. & Otto, F. (Eds.)
    (In)dependencies in Functional Generative
    Description by Restarting Automata
    2010 Second Workshop on Non-Classical Models for
    Automata and Applications (NCMA 2010), Vol. 263(), books@ocg.at, Österreichisches Computer Gesellschaft, pp. 155-170
    inproceedings
    BibTeX:
    @inproceedings{PML10ncma,
      author = {Martin Plátek and František Mráz and Markéta
    Lopatková}, title = {(In)dependencies in Functional Generative
    Description by Restarting Automata}, booktitle = {Second Workshop on Non-Classical Models for
    Automata and Applications (NCMA 2010)}, editor = {Henning Bordihn and Rudolf Freund and Thomas
    Hinze and Markus Holzer and Martin Kutrib and Friedrich Otto}, publisher = {Österreichisches Computer Gesellschaft}, series = {books@ocg.at}, year = {2010}, volume = {263}, pages = {155--170} }
    PML10 Plátek, M.; Mráz, F. & Lopatková, M.
    Dediu, A.-H.; Fernau, H. & Martín-Vide, C. (Eds.)
    Restarting Automata with Structured Output and
    Functional Generative Description
    2010 LATA 2010, Vol. 6031(), LNCS, Springer, Berlin, pp. 500-511 inproceedings
    Abstract: Restarting automata were introduced for modeling
    linguistically motivated analysis by reduction. In this paper we enhance
    these automata with a structured output in the form of a tree. Enhanced
    restarting automata can serve as a formal framework for the Functional
    Generative Description. In this framework, a natural language is described
    at four layers. Working simultaneously with all these layers,
    tectogrammatical dependency structures that represent the meaning of the
    sentence are derived.
    BibTeX:
    @inproceedings{PML10,
      author = {Martin Plátek and František Mráz and Markéta
    Lopatková}, title = {Restarting Automata with Structured Output and
    Functional Generative Description}, booktitle = {LATA 2010}, editor = {A.-H.~Dediu and H.~Fernau and
    C.~Martín-Vide}, publisher = {Springer}, address = {Berlin}, series = {LNCS}, year = {2010}, volume = {6031}, pages = {500--511} }
    PMOL05 Plátek, M.; Mráz, F.; Otto, F. & Lopatková, M.
    Vojtáš, P. (Eds.)
    O roztržitosti a volnosti slovosledu pomocí
    restartovacích automatů
    2005 ITAT 2005, Information Technologies --
    Applications and Theory, Proc., Pavol Jozef šafárik University, Košice, pp. 145-155, Department of Computer Science, Faculty of
    Science, In Czech, Eng. translation: On discontinuity and
    freenes of word-order by restarting automata
    inproceedings
    BibTeX:
    @inproceedings{PMOL05,
      author = {Martin Plátek and František Mráz and Friedrich
    Otto and Markéta Lopatková}, title = {O roztržitosti a volnosti slovosledu pomocí
    restartovacích automatů}, booktitle = {ITAT 2005, Information Technologies --
    Applications and Theory, Proc.}, editor = {P.~Vojtáš}, publisher = {Pavol Jozef šafárik University}, address = {Košice}, organization = {Department of Computer Science, Faculty of
    Science}, year = {2005}, pages = {145--155}, note = {In Czech, Eng. translation: On discontinuity and
    freenes of word-order by restarting automata} }
    POM03 Plátek, M.; Otto, F. & Mráz, F.
    Csuhaj-Varjú, E.; Kintala, C.; Wotschke, D. & Vaszil, G. (Eds.)
    Restarting Automata and Variants of
    j-Monotonicity
    2003 Proceedings of DCFS 2003 Descriptional
    Complexity of Formal Systems, MTA SZTAKI, Budapest, pp. 303-312
    inproceedings
    BibTeX:
    @inproceedings{POM03,
      author = {Martin Plátek and Friedrich Otto and František
    Mráz}, title = {Restarting Automata and Variants of
    j-Monotonicity}, booktitle = {Proceedings of DCFS 2003 Descriptional
    Complexity of Formal Systems}, editor = {Erzsébet Csuhaj-Varjú and Chandra Kintala and
    Detlef Wotschke and György Vaszil}, publisher = {MTA SZTAKI, Budapest}, year = {2003}, pages = {303--312} }
    POM09 Plátek, M.; Otto, F. & Mráz, F. Two-dimensional hierarchies of proper languages
    of lexicalized FRR-automata
    2009 Inf. Comput., Vol. 207(11), pp. 1300-1314 article
    Abstract: Various syntactical phenomena play an important
    role when developing grammars for natural languages. Among them are the
    dependencies (subordination) or valences, which are closely related to the
    complexity of the word-order of the language considered, and the number and
    types of categories that are used during the process of syntactic
    disambiguation. Here we present the freely rewriting restarting automaton
    (FRR-automaton), which is a variant of the restarting automaton that is
    tuned towards modeling such phenomena. We study proper languages of
    deterministic FRR-automata that are (strongly) lexicalized, where we focus
    on two types of constraints: the number of rewrites per cycle, which models
    the degree of valences within sentences, and the number of occurrences of
    auxiliary symbols (categories) in the sentences (words) of the corresponding
    characteristic language, which models the use of categories during the
    process of syntactic disambiguation. Based on these constraints we obtain
    four variants of two-dimensional hierarchies of language classes.
    BibTeX:
    @article{POM09,
      author = {Martin Plátek and Friedrich Otto and František
    Mráz}, title = {Two-dimensional hierarchies of proper languages
    of lexicalized FRR-automata}, journal = {Inf. Comput.}, year = {2009}, volume = {207}, number = {11}, pages = {1300-1314} }
    POMJ03 Plátek, M.; Otto, F.; Mráz, F. & Jurdzińnski, T. Restarting automata and variants of
    $j$-monotonicity
    2003 Fachbereich Mathematik/Informatik,
    Universität Kassel, 9/03
    techreport
    BibTeX:
    @techreport{POMJ03,
      author = {Martin Plátek and Friedrich Otto and František
    Mráz and Tomasz Jurdzińnski}, title = {Restarting automata and variants of
    $j$-monotonicity}, institution = {Fachbereich Mathematik/Informatik,
    Universität Kassel}, year = {2003}, number = {9/03} }
    PrM12t Pruša, D. & Mráz, F. New models for recognition of picture languages: Sgraffito and
    restarting tiling automata
    2012 Center for Machine Perception, K13133 FEE Czech Technical
    University, Prague, Czech Republic (March 2012), CTU--CMP--2012--08
    techreport
    BibTeX:
    @techreport{PrM12t,
      author = {Pruša, Daniel and Mráz, František},
      title = {New models for recognition of picture languages: Sgraffito and
    restarting tiling automata}, institution = {Center for Machine Perception, K13133 FEE Czech Technical
    University, Prague, Czech Republic (March 2012)}, year = {2012}, number = {CTU--CMP--2012--08} }
    PM12ciaa Průša, D. & Mráz, F.
    Moreira, N. & Reis, R. (Eds.)
    Restarting Tiling Automata 2012 Implementation and Application of Automata, Vol. 7381(), LNCS, Springer Berlin Heidelberg, pp. 289-300 inproceedings two-dimensional languages; tiling systems;
    restarting automata
    Abstract: We present a new model of a two-dimensional
    computing device called restarting tiling automaton. The automaton defines a
    set of tile-rewriting, weight-reducing rules and a scanning strategy by
    which a tile to rewrite is being searched. We investigate properties of the
    induced families of picture languages. Special attention is paid to picture
    languages that can be accepted independently of the scanning strategy. We
    show that this family strictly includes REC and exhibits similar closure
    properties. Moreover, we prove that its intersection with the set of one-row
    languages coincides with the regular languages. © 2012 Springer-Verlag.
    BibTeX:
    @inproceedings{PM12ciaa,
      author = {Průša, Daniel and Mráz, František},
      title = {Restarting Tiling Automata},
      booktitle = {Implementation and Application of Automata},
      editor = {Moreira, Nelma and Reis, Rogério},
      publisher = {Springer Berlin Heidelberg},
      series = {LNCS},
      year = {2012},
      volume = {7381},
      pages = {289-300},
      url = {http://dx.doi.org/10.1007/978-3-642-31606-7_25},
      doi = {http://dx.doi.org/10.1007/978-3-642-31606-7_25}
    }
    					
    PrM00 Průša, D. & Mráz, F.
    Svoboda, T. (Eds.)
    Parallel Turing Machines on a Two-Dimensional
    Tape
    2000 Proceedings of the Czech Pattern Recognition
    Workshop 2000, Czech Pattern Recognition Society, Praha, pp. 155-160, ISBN 80-238-5215-9
    inproceedings
    BibTeX:
    @inproceedings{PrM00,
      author = {Daniel Průša and František Mráz},
      title = {Parallel Turing Machines on a Two-Dimensional
    Tape}, booktitle = {Proceedings of the Czech Pattern Recognition
    Workshop 2000}, editor = {Tomáš Svoboda}, publisher = {Czech Pattern Recognition Society}, address = {Praha}, year = {2000}, pages = {155--160}, note = {ISBN 80-238-5215-9} }
    PM12dlt Průša, D. & Mráz, F.
    Yen, H.-C. & Ibarra, O. (Eds.)
    Two-Dimensional Sgraffito Automata 2012 Developments in Language Theory, Vol. 7410(), LNCS, Springer Berlin Heidelberg, pp. 251-262 inproceedings two-dimensional languages; sgraffito automaton;
    bounded turing machine; rec
    BibTeX:
    @inproceedings{PM12dlt,
      author = {Průša, Daniel and Mráz, František},
      title = {Two-Dimensional Sgraffito Automata},
      booktitle = {Developments in Language Theory},
      editor = {Yen, Hsu-Chun and Ibarra, OscarH.},
      publisher = {Springer Berlin Heidelberg},
      series = {LNCS},
      year = {2012},
      volume = {7410},
      pages = {251-262},
      url = {http://dx.doi.org/10.1007/978-3-642-31653-1_23},
      doi = {http://dx.doi.org/10.1007/978-3-642-31653-1_23}
    }
    					
    PrMr13 Průša, D. & Mráz, F. Restarting Tiling Automata 2013 Int. J. Found. Comput. Sci., Vol. 24(6), pp. 863-878 article
    BibTeX:
    @article{PrMr13,
      author = {Daniel Průša and František Mráz},
      title = {Restarting Tiling Automata},
      journal = {Int. J. Found. Comput. Sci.},
      year = {2013},
      volume = {24},
      number = {6},
      pages = {863--878}
    }
    					
    PruMraOtt13dlt Průša, D.; Mráz, F. & Otto, F.
    Béal, M.-P. & Carton, O. (Eds.)
    New Results on Deterministic Sgraffito
    Automata
    2013 Developments in Language Theory, Vol. 7907(), Lecture Notes in Computer Science, Springer Berlin Heidelberg, Marne-la-Vallee, pp. 409-419 inproceedings picture languages; sgraffito automaton;
    recognizable picture languages
    Abstract: The deterministic sgraffito automaton is a
    two-dimensional computing device that allows a clear and simple design of
    important computations. The family of picture languages it accepts has many
    nice closure properties, but when restricted to one-row inputs (that is,
    strings), this family collapses to the class of regular languages. Here we
    compare the deterministic sgraffito automaton to some other two-dimensional
    models: the two-dimensional deterministic forgetting automaton, the four-way
    alternating automaton and the sudoku-deterministically recognizable picture
    languages. In addition, we prove that deterministic sgraffito automata
    accept some unary picture languages that are outside the class REC of
    recognizable picture languages. © 2013 Springer-Verlag.
    BibTeX:
    @inproceedings{PruMraOtt13dlt,
      author = {Průša, Daniel and Mráz, František and Otto,
    Friedrich}, title = {New Results on Deterministic Sgraffito
    Automata}, booktitle = {Developments in Language Theory}, editor = {Béal, Marie-Pierre and Carton, Olivier}, publisher = {Springer Berlin Heidelberg}, address = {Marne-la-Vallee}, series = {Lecture Notes in Computer Science}, year = {2013}, volume = {7907}, pages = {409--419}, doi = {http://dx.doi.org/10.1007/978-3-642-38771-5_36} }
    PruMraOtt13ciaa Průša, D.; Mráz, F. & Otto, F.
    Konstantinidis, S. (Eds.)
    Comparing Two-Dimensional One-Marker Automata to
    Sgraffito Automata
    2013 Implementation and Application of Automata, Vol. 7982(), Lecture Notes in Computer Science, Springer Berlin Heidelberg, Halifax, NS, pp. 268-279 inproceedings picture languages; two-dimensional one-marker
    automaton; sgraffito automaton; recognizable picture languages
    Abstract: We compare two types of automata for accepting
    picture languages to each other: the two-dimensional one-marker automaton
    and the sgraffito automaton. On the one hand, it is shown that deterministic
    sgraffito automata are strictly more powerful than deterministic
    two-dimensional one-marker automata. On the other hand, nondeterministic
    two-dimensional one-marker automata accept some picture languages that
    cannot be accepted by sgraffito automata. However, if nondeterministic
    two-dimensional one-marker automata were to accept all picture languages
    that are accepted by (deterministic) sgraffito automata, then the complexity
    classes NL (nondeterministic logarithmic space) and P (deterministic
    polynomial time) would coincide. Accordingly, it is likely that the classes
    of picture languages accepted by these two types of nondeterministic
    automata are incomparable under inclusion. © 2013 Springer-Verlag.
    BibTeX:
    @inproceedings{PruMraOtt13ciaa,
      author = {Průša, Daniel and Mráz, František and Otto,
    Friedrich}, title = {Comparing Two-Dimensional One-Marker Automata to
    Sgraffito Automata}, booktitle = {Implementation and Application of Automata}, editor = {Konstantinidis, Stavros}, publisher = {Springer Berlin Heidelberg}, address = {Halifax, NS}, series = {Lecture Notes in Computer Science}, year = {2013}, volume = {7982}, pages = {268--279}, doi = {http://dx.doi.org/10.1007/978-3-642-39274-0_24} }
    PruMraOtt15rairo Průša, D.; Mráz, F. & Otto, F. Two-dimensional Sgraffito automata 2014 RAIRO - Theoretical Informatics and
    Applications, Vol. 48(5), pp. 505-539
    article
    BibTeX:
    @article{PruMraOtt15rairo,
      author = {Průša,Daniel and Mráz,František and
    Otto,Friedrich}, title = {Two-dimensional Sgraffito automata}, journal = {RAIRO - Theoretical Informatics and
    Applications}, year = {2014}, volume = {48}, number = {5}, pages = {505--539}, url = {http://www.rairo-ita.org/article_S098837541400023X}, doi = {http://dx.doi.org/10.1051/ita/2014023} }
    Mra12tt
    Mráz, F. (Eds.)
    Proceedings of the 22nd Theorietag Automata and Formal
    Languages
    2012 Charles University, , Matfyzpress, Prague proceedings
    BibTeX:
    @proceedings{Mra12tt,,
      title = {Proceedings of the 22nd Theorietag Automata and Formal
    Languages}, editor = {František Mráz}, publisher = {Matfyzpress}, address = {Prague}, institution = {Charles University}, year = {2012} }

    Created by JabRef on 06/06/2016.