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.
F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by the program ‘Information Society’ under project 1ET100300517. F. Mráz was also partially supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: A general theory of translation. Math. Systems Theory 3, 193–221 (1969)
Hajič, J., Krbec, P., Oliva, K., Květoň, P., Petkevič, V.: Serial combination of rules and statistics: A case study in Czech tagging. In: Proceedings of the 39th Association of Computational Linguistics Conference. Association for Computational Linguistics, Toulouse, France (2001)
Holzer, M., Kutrib, M., Reimann, J.: Descriptional complexity of deterministic restarting automata. In: Mereghetti, C., Palano, B., Pighizzini, G., Wotschke, D. (eds.) DCFS 2005, Proc. Università degli Studi di Milano, pp. 158–169 (2005)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)
Kuboň, V., Plátek, M.: A grammar based approach to a grammar checking of free word order languages. In: COLING 1994, Proc., Kyoto, Japan, vol. II, pp. 906–910 (1994)
Lopatková, M., Plátek, M., Kuboň, V.: Modeling syntax of free word-order languages: Dependency analysis by reduction. In: Matoušek, V., Mautner, P., Pavelka, T. (eds.) TSD 2005. LNCS, vol. 3658, pp. 140–147. Springer, Heidelberg (2005)
Lothaire, M.: Combinatorics on Words. In: Encyclopedia of Mathematics, vol. 17. Addison-Wesley, Reading (1983)
Messerschmidt, H., Mráz, F., Otto, F., Plátek, M.: On the descriptional complexity of simple sRL-automata. Mathematische Schriften Kassel 4/06, Universität Kassel (April 2006)
Mráz, F., Otto, F., Plátek, M.: Degrees of free word-order and restarting automata. Grammars (to appear)
Mráz, F., Otto, F., Plátek, M.: On the gap-complexity of simple RL-automata. In: Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 83–94. Springer, Heidelberg (2006)
Procházka, M.: Concepts of syntax error recovery for monotonic reducing automata. In: Obdržálek, D., Štanclová, J. (eds.) MIS 2004, Proc., Matfyzpress, Praha, pp. 94–103 (2004)
Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 55–74. Springer, Heidelberg (2003)
Păun, G.: Marcus Contextual Grammars, Studies in Linguistics and Philosophy, vol. 67. Kluwer, Dordrecht (1997)
Plátek, M.: Two-way restarting automata and J-monotonicity. In: Pacholski, L., Ružička, P. (eds.) SOFSEM 2001. LNCS, vol. 2234, pp. 316–325. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Messerschmidt, H., Mráz, F., Otto, F., Plátek, M. (2006). Correctness Preservation and Complexity of Simple RL-Automata. In: Ibarra, O.H., Yen, HC. (eds) Implementation and Application of Automata. CIAA 2006. Lecture Notes in Computer Science, vol 4094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11812128_16
Download citation
DOI: https://doi.org/10.1007/11812128_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37213-4
Online ISBN: 978-3-540-37214-1
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science