Friedrich Otto
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Friedrich Otto has a total of 70 co-authors. Here are the top co-authors by number of shared publications:
- František Mráz
Charles University in Prague
8 shared publications - Kent Kwee
Universität Kassel
4 shared publications - Yuji Kobayashi
Laboratory of Mathematics and Games
4 shared publications Kent Kwee
Universität Kassel
3 shared publications- Martin Kutrib
Institut für Informatik, Universität Gießen
3 shared publications - Martin Plátek
Charles University in Prague
3 shared publications
Latest Publications
- 1 April 2018
- Published by Elsevier in Information and Computation
- Vol. 259, 277-302
On the descriptional complexity of stateless deterministic ordered restarting automata
- 1 April 2018
- Published by Elsevier in Information and Computation
- Vol. 259, 277-302
On the descriptional complexity of stateless deterministic ordered restarting automata
- Open Access
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 219-233
On h-Lexicalized Restarting Automata
Following some previous studies on restarting automata, we introduce a refined model - the h-lexicalized restarting automaton (h-RLWW). We argue that this model is useful for expressing lexicalized syntax in computational linguistics. We compare the input languages, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages, which are (implicitly) used by categorial grammars, the original tool for the description of lexicalized syntax. The basic and h-proper languages allow us to stress several nice properties of h-lexicalized restarting automata, and they are suitable for modeling the analysis by reduction and, subsequently, for the development of categories of a lexicalized syntax. Based on the fact that a two-way deterministic monotone restarting automaton can be transformed into an equivalent deterministic monotone RL-automaton in (Marcus) contextual form, we obtain a transformation from monotone RLWW-automata that recognize the class CFL of context-free languages as their input languages to deterministic monotone h-RLWW-automata that recognize CFL through their h-proper languages. Through this transformation we obtain automata with the complete correctness preserving property and an infinite hierarchy within CFL, based on the size of the read/write window. Additionally, we consider h-RLWW-automata that are allowed to perform multiple rewrite steps per cycle, and we establish another infinite hierarchy above CFL that is based on the number of rewrite steps that may be executed within a cycle. The corresponding separation results and their proofs illustrate the transparency of h-RLWW-automata that work with the (complete or cyclic) correctness preserving propertyComment: In Proceedings AFL 2017, arXiv:1708.0622
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 219-233
Open AccessOn h-Lexicalized Restarting Automata
Following some previous studies on restarting automata, we introduce a refined model - the h-lexicalized restarting automaton (h-RLWW). We argue that this model is useful for expressing lexicalized syntax in computational linguistics. We compare the input languages, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages, which are (implicitly) used by categorial grammars, the original tool for the description of lexicalized syntax. The basic and h-proper languages allow us to stress several nice properties of h-lexicalized restarting automata, and they are suitable for modeling the analysis by reduction and, subsequently, for the development of categories of a lexicalized syntax. Based on the fact that a two-way deterministic monotone restarting automaton can be transformed into an equivalent deterministic monotone RL-automaton in (Marcus) contextual form, we obtain a transformation from monotone RLWW-automata that recognize the class CFL of context-free languages as their input languages to deterministic monotone h-RLWW-automata that recognize CFL through their h-proper languages. Through this transformation we obtain automata with the complete correctness preserving property and an infinite hierarchy within CFL, based on the size of the read/write window. Additionally, we consider h-RLWW-automata that are allowed to perform multiple rewrite steps per cycle, and we establish another infinite hierarchy above CFL that is based on the number of rewrite steps that may be executed within a cycle. The corresponding separation results and their proofs illustrate the transparency of h-RLWW-automata that work with the (complete or cyclic) correctness preserving propertyComment: In Proceedings AFL 2017, arXiv:1708.0622
- 21 July 2017
- Published by Springer Nature
- p. 272-283
Deleting Deterministic Restarting Automata with Two Windows
- 21 July 2017
- Published by Springer Nature
- p. 272-283
Deleting Deterministic Restarting Automata with Two Windows
- Open Access
- 3 June 2017
- Published by Springer Nature
- p. 226-237
A Pumping Lemma for Ordered Restarting Automata
- 3 June 2017
- Published by Springer Nature
- p. 226-237
Open AccessA Pumping Lemma for Ordered Restarting Automata
- 1 June 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 682, 190-207
Regulated variants of limited context restarting automata
- 1 June 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 682, 190-207
Regulated variants of limited context restarting automata
- 24 December 2016
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 148 (3-4)
Preface
- 1 October 2016
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 50 (4) , 351-369
Some classes of rational functions for pictures
With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail.
- 1 October 2016
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 50 (4) , 351-369
Some classes of rational functions for pictures
With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail.
- 6 July 2016
- Published by Springer Nature
- p. 298-309
Weighted Restarting Automata as Language Acceptors
- 1 July 2016
- Published by Elsevier in Theoretical Computer Science
- Vol. 635, 1-15
Weighted restarting automata and pushdown relations
- 1 July 2016
- Published by Elsevier in Theoretical Computer Science
- Vol. 635, 1-15
Weighted restarting automata and pushdown relations