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 |
||||||
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 |
||||||
CM09 |
Černo, P. & Mráz, F.
Bordihn, H.; Freund, R.; Holzer, M.; Kutrib, M. & Otto, F. (Eds.) |
Clearing restarting automata
[BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
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
[BibTeX] |
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ů
[BibTeX] |
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
[BibTeX] |
1989 | SOFSEM'89, Ždiar, Vysoké Tatry, pp. 27-30 | inproceedings | |
BibTeX:
@inproceedings{ChMSV89slo, author = {Michal Chytil and František Mráz and Libor |
||||||
JMP92sofabbr |
Jančar, P.; Mráz, F. & Plátek, M.
Bartošek, M. (Eds.) |
Forgetting automata and the Chomsky hierarchy [BibTeX] |
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 |
||||||
JMP93abbr |
Jančar, P.; Mráz, F. & Plátek, M.
Borzyszkowski, A.M. & Sokolowski, S. (Eds.) |
A Taxonomy of Forgetting Automata
[BibTeX] |
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 |
||||||
JMP92abbr |
Jančar, P.; Mráz, F. & Plátek, M.
Havel, I.M. & Koubek, V. (Eds.) |
Characterization of Context-Free Languages by Erasing Automata [BibTeX] |
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 |
||||||
JMP96 | Jančar, P.; Mráz, F. & Plátek, M. |
Forgetting Automata and Context-Free Languages [BibTeX] |
1996 | Acta Informatica, Vol. 33(5), pp. 409-420 | article | |
BibTeX:
@article{JMP96, author = {Petr Jančar and František Mráz and Martin |
||||||
JMP93p | Jančar, P.; Mráz, F. & Plátek, M. |
A Taxonomy of Forgetting Automata
[BibTeX] |
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 |
||||||
JMP92p | Jančar, P.; Mráz, F. & Plátek, M. |
Characterization of Context-Free Languages by Erasing Automata [BibTeX] |
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 |
||||||
JMPPV98 |
Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J.
Bozapalidis, S. (Eds.) |
Deleting Automata with a Restart Operation
[BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
JMPPV97p | Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J. |
Deleting Automata with a Restart Operation
[BibTeX] |
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 |
||||||
JMPPV95j | Jančar, P.; Mráz, F.; Plátek, M.; Procházka, M. & Vogel, J. |
Restarting Automata and Marcus Grammars
[BibTeX] |
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 |
||||||
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 |
||||||
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
[BibTeX] |
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 |
||||||
JMPV98a |
Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J.
Kudlek, M. (Eds.) |
On Monotony for Restarting Automata
[BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
JMPV07 | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
Monotonicity of Restarting Automata
[BibTeX] |
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 |
||||||
JMPV02j | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
Monotonicity on restarting automata
[BibTeX] |
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 |
||||||
JMPV99 | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
On Monotonic Automata with a Restart Operation [BibTeX] |
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 |
||||||
JMPV98j | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
Different Types of Monotonicity for Restarting Automata [BibTeX] |
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 |
||||||
JMPV96p | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
On Restarting Automata with Rewriting
[BibTeX] |
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 |
||||||
JMPV94j | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
Restarting Automata
[BibTeX] |
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 |
||||||
JMPV94p | Jančar, P.; Mráz, F.; Plátek, M. & Vogel, J. |
Deleting Automata with a Restart Operation
[BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
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 |
||||||
JMOP04t21 | Jurdziński, T.; Mráz, F.; Otto, F. & Plátek, M. |
Cut hierarchies for restarting automata and Marcus t-contextual grammars [BibTeX] |
2004 | Universität Kassel, 21/04, 23 pages | techreport | |
BibTeX:
@techreport{JMOP04t21, author = {Tomasz Jurdziński and František Mráz and |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
JOMP04t18 | Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. |
Deterministic two-way restarting automata and Marcus contextual grammars [BibTeX] |
2004 | Universität Kassel, 18/04, 14 pages | techreport | |
BibTeX:
@techreport{JOMP04t18, author = {Tomasz Jurdziński and Friedrich Otto and |
||||||
JOMP04t4 | Jurdziński, T.; Otto, F.; Mráz, F. & Plátek, M. |
On the Complexity of 2-Monotone Restarting Automata [BibTeX] |
2004 | Universität Kassel, 4/04 | techreport | |
BibTeX:
@techreport{JOMP04t4, author = {Tomasz Jurdziński and Friedrich Otto and |
||||||
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 [BibTeX] |
2004 | Universität Kassel, 7/04 | techreport | |
BibTeX:
@techreport{JOMP04t7, author = {Tomasz Jurdziński and Friedrich Otto and |
||||||
KrMr14ncma |
Krtek, L. & Mráz, F.
Bensch, S.; Freund, R. & Otto, F. (Eds.) |
Two-dimensional limited context restarting automata [BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
Mra14ncma |
Mráz, F.
Bensch, S.; Freund, R. & Otto, F. (Eds.) |
Limited restarting automata
[BibTeX] |
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 |
||||||
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 |
||||||
MOP15ncma | Mráz, F.; Otto, F. & Prusa, D. |
On a class of rational functions for pictures
[BibTeX] |
2015 | NCMA, Vol. 318(), books@ocg.at, Österreichische Computer Gesellschaft, pp. 159-176 | inproceedings | |
BibTeX:
@inproceedings{MOP15ncma, author = {Frantisek Mráz and |
||||||
M89slo |
Mráz, F.
Bartošek, M. (Eds.) |
Paralelné algoritmy redukcie koneČných automatov [BibTeX] |
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 |
||||||
M00abbr |
Mráz, F.
Boldt, O. & Jürgensen, H. (Eds.) |
Lookahead Hierarchies of Restarting Automata
[BibTeX] |
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 |
||||||
M01 | Mráz, F. |
Lookahead Hierarchies of Restarting Automata
[BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
MO03TT |
Mráz, F. & Otto, F.
Holzer, M. (Eds.) |
Hierarchies of weakly monotone restarting automata [BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
MO03t | Mráz, F. & Otto, F. |
Hierarchies of weakly monotone restarting automata [BibTeX] |
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 |
||||||
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 |
||||||
MOP05tagi |
Mráz, F.; Otto, F. & Plátek, M.
Fernau, H. (Eds.) |
Learning analysis by reduction from positive data [BibTeX] |
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 |
||||||
MOP05tt |
Mráz, F.; Otto, F. & Plátek, M.
Fernau, H. (Eds.) |
Parametrized syntactic analysis by freely rewriting restarting automata [BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
MOP03ITAT |
Mráz, F.; Otto, F. & Plátek, M.
Vojtáš, P. (Eds.) |
Restarting automata and combinations of constraints [BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
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 |
||||||
MOP05t5 | Mráz, F.; Otto, F. & Plátek, M. |
Degrees of Free Word-Order and Freely Rewriting Restarting Automata [BibTeX] |
2005 | Universität Kassel, 5/05 | techreport | |
BibTeX:
@techreport{MOP05t5, author = {František Mráz and Friedrich Otto and Martin |
||||||
MOP05t7 | Mráz, F.; Otto, F. & Plátek, M. |
Learning analysis by reduction from positive data [BibTeX] |
2005 | Universität Kassel, 7/05 | techreport | |
BibTeX:
@techreport{MOP05t7, author = {František Mráz and Friedrich Otto and Martin |
||||||
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 |
||||||
MP95 | Mráz, F. & Plátek, M. |
Erasing Automata Recognize More Than Context-Free Languages [BibTeX] |
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 |
||||||
MP93 | Mráz, F. & Plátek, M. |
A Remark About Forgetting Automata
[BibTeX] |
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 [BibTeX] |
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 |
||||||
MP91p | Mráz, F. & Plátek, M. |
Erasing Automata Recognize More Than Context-Free Languages [BibTeX] |
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 |
||||||
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 |
||||||
MPJV97p | Mráz, F.; Plátek, M.; Jančar, P. & Vogel, J. |
Monotonic Rewriting Automata with a Restart Operation [BibTeX] |
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 |
||||||
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 |
||||||
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 |
||||||
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 [BibTeX] |
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 |
||||||
MPP98 |
Mráz, F.; Plátek, M. & Procházka, M.
Bozapalidis, S. (Eds.) |
Deleting Automata with a Restart Operation and Marcus Grammars [BibTeX] |
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 |
||||||
MPPk00 |
Mráz, F.; Plátek, M. & Procházka, M.
C. Martín-Vide, V.M. (Eds.) |
On special forms of restarting automata
[BibTeX] |
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 |
||||||
MPP00 |
Mráz, F.; Plátek, M. & Procházka, M.
Martín-Vide, C. & Păun, G. (Eds.) |
Restarting Automata, Deleting, and Marcus Grammars [BibTeX] |
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 |
||||||
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 |
||||||
MPP97p | Mráz, F.; Plátek, M. & Procházka, M. |
Deleting Automata with a Restart Operation and Marcus Grammars [BibTeX] |
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 |
||||||
MM01 |
Mrázová, I. & Mráz, F.
Andrejková, G. & KrajČi, S. (Eds.) |
Data Mining and Neural Networks
[BibTeX] |
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 -- |
||||||
MMRP08 |
Mrázová, I.; Mráz, F.; Reitermanová, Z. & PetříČek, M.
et al., C.H.D. (Eds.) |
Phonetic Search in Foreign Texts
[BibTeX] |
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 |
||||||
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 |
||||||
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 [BibTeX] |
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 |
||||||
OCM12tt |
Otto, F.; Černo, P. & Mráz, F.
Mráz, F. (Eds.) |
Limited Context Restarting Automata and McNaughton Families of Languages [BibTeX] |
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 |
||||||
OM15tcs | Otto, F. & Mráz, F. |
Lambda-confluence for context rewriting systems [BibTeX] |
2015 | Theor. Comput. Sci., Vol. 578(), pp. 88-99 | article | |
BibTeX:
@article{OM15tcs, author = {Friedrich Otto and |
||||||
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 [BibTeX] |
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 |
||||||
OttMra15actinf | Otto, F. & Mráz, F. |
Deterministic ordered restarting automata for picture languages [BibTeX] |
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 |
||||||
OMP05 |
Otto, F.; Mráz, F. & Plátek, M.
Ésik, Z. & Fülöp, Z. (Eds.) |
Degrees of monotonicity and Marcus t-contextual grammars [BibTeX] |
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 |
||||||
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, |
||||||
PaMP11 | Pardubská, D.; Mráz, F. & Plátek, M. |
Translations by Regulated Parallel Communicating Grammar Systems [BibTeX] |
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 |
||||||
PM01 |
Plátek, M. & Mráz, F.
Dassow, J. & Wotschke, D. (Eds.) |
Degrees of (non)monotonicity of RRWW-automata [BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
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 |
||||||
PMOL05 |
Plátek, M.; Mráz, F.; Otto, F. & Lopatková, M.
Vojtáš, P. (Eds.) |
O roztržitosti a volnosti slovosledu pomocí restartovacích automatů [BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
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 |
||||||
POMJ03 | Plátek, M.; Otto, F.; Mráz, F. & Jurdzińnski, T. |
Restarting automata and variants of $j$-monotonicity [BibTeX] |
2003 |
Fachbereich Mathematik/Informatik, Universität Kassel, 9/03 |
techreport | |
BibTeX:
@techreport{POMJ03, author = {Martin Plátek and Friedrich Otto and František |
||||||
PrM12t | Pruša, D. & Mráz, F. |
New models for recognition of picture languages: Sgraffito and restarting tiling automata [BibTeX] |
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 |
||||||
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 [BibTeX] |
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 |
||||||
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
[BibTeX] |
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, |
||||||
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, |
||||||
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 |
||||||
Mra12tt |
Mráz, F. (Eds.) |
Proceedings of the 22nd Theorietag Automata and Formal Languages [BibTeX] |
2012 | Charles University, , Matfyzpress, Prague | proceedings | |
BibTeX:
@proceedings{Mra12tt,, title = {Proceedings of the 22nd Theorietag Automata and Formal |
Created by JabRef on 06/06/2016.