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-sRL-automaton 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.
The first and the third author 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. The first author 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
Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141, 1–36 (1998)
Holan, T.: Dependency analyser configurable by measures. In: Sojka, P., Kopeček, I., Pala, K. (eds.) TSD 2002. LNCS, vol. 2448, pp. 81–88. Springer, Heidelberg (2002)
Holan, T., Kuboň, V., Oliva, K., Plátek, M.: Two useful measures of word order complexity. In: Polguere, A., Kahane, S. (eds.) Workshop Processing of Dependency-Based Grammars, COLING 1998, Proc., University of Montreal, pp. 21–28 (1998)
Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On monotonic automata with a restart operation. Journal of Automata, Languages and Combinatorics 4, 287–311 (1999)
Jurdziński, T., Otto, F., Mráz, F., Plátek, M.: On the complexity of 2-monotone restarting automata. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 237–248. Springer, Heidelberg (2004)
Jurdziński, T., Otto, F., Mráz, F., Plátek, M.: On the complexity of 2-monotone restarting automata. Mathematische Schriften Kassel 4/04, Universität Kassel (2004)
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. Encyclopedia of Mathematics, vol. 17. Addison-Wesley, Reading (1983)
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)
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)
Plátek, M., Otto, F., Mráz, F.: Restarting automata and variants of j-monotonicity. In: Csuhaj-Varjú, E., Kintala, C., Wotschke, D., Vaszil, G. (eds.) DCFS 2003, Proc., MTA SZTAKI, Budapest, pp. 303–312 (2003)
Plátek, M., Otto, F., Mráz, F., Jurdziński, T.: Restarting automata and variants of j-monotonicity. Mathematische Schriften Kassel 9/03, Universität Kassel (2003)
von Solms, S.H.: The characterization by automata of certain classes of languages in the context sensitive area. Information and Control 27, 262–271 (1975)
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
Mráz, F., Otto, F., Plátek, M. (2006). On the Gap-Complexity of Simple RL-Automata. In: Ibarra, O.H., Dang, Z. (eds) Developments in Language Theory. DLT 2006. Lecture Notes in Computer Science, vol 4036. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11779148_9
Download citation
DOI: https://doi.org/10.1007/11779148_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35428-4
Online ISBN: 978-3-540-35430-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.