Top

Published in:

2016 | OriginalPaper | Chapter

Two Results on Discontinuous Input Processing

Author : Vojtěch Vorel

Published in: Descriptional Complexity of Formal Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

First, we show that universality and other properties of general jumping finite automata are undecidable, which answers questions asked by Meduna and Zemek in 2012 [12]. Second, we close a study started by Černo and Mráz in 2010 [3] by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter State Complexity of Prefix Distance of Subregular Languages

A projection to \(\varGamma '\subseteq \varGamma \) is given by the homomorphism that maps \(x\in \varGamma \) to x if \(x\in \varGamma '\) or to \(\epsilon \) otherwise.

Alhazov, A., Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Small size insertion and deletion systems. In: Martin-Vide, C. (ed.) Scientific Applications of Language Methods, pp. 459–524. Imperial College Press (2010)

Černo, P.: Clearing restarting automata and grammatical inference. In: Heinz, J., Colin de la Higuera, T.O. (eds.) Proceedings of the Eleventh International Conference on Grammatical Inference. JMLR Workshop and Conference Proceedings, vol. 21, pp. 54–68 (2012)

Černo, P., Mráz, F.: Clearing restarting automata. Fund. Inf. 104(1), 17–54 (2010)MathSciNetMATH

Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theoret. Comput. Sci. 27(3), 311–332 (1983)MathSciNetCrossRefMATH

Fernau, H., Paramasivan, M., Schmid, M., Vorel, V.: Characterization andcomplexity results on jumping finite automata. Accepted to Theoretical Computer Science (2015). http://arxiv.org/abs/1512.00482

Fernau, H., Paramasivan, M., Schmid, M.L.: Jumping finite automata: characterizations and complexity. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 89–101. Springer, Heidelberg (2015)CrossRef

Haussler, D.: Insertion languages. Inf. Sci. 31(1), 77–89 (1983)MathSciNetCrossRefMATH

Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley (2003)

Ito, M., Kari, L., Thierrin, G.: Insertion and deletion closure of languages. Theoret. Comput. Sci. 183(1), 3–19 (1997)MathSciNetCrossRefMATH

10.

Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 283–292. Springer, Heidelberg (1995)CrossRef

11.

Marcus, M., Păun, G.: Regulated Galiukschov semicontextual grammars. Kybernetika 26(4), 316–326 (1990)MathSciNetMATH

12.

Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23(7), 1555–1578 (2012)MathSciNetCrossRefMATH

13.

Meduna, A., Zemek, P.: Chapter 17 Jumping Finite Automata. In: Regulated Grammars and Automata, pp. 567–585. Springer, New York (2014)

14.

Mráz, F., Plátek, M., Vogel, J.: Restarting automata with rewriting. In: Král, J., Bartosek, M., Jeffery, K. (eds.) SOFSEM 1996. LNCS, vol. 1175, pp. 401–408. Springer, Heidelberg (1996)CrossRef

15.

Păun, G.: Two theorems about Galiukschov semicontextual languages. Kybernetika 21(5), 360–365 (1985)MathSciNetMATH

16.

Păun, G., Rozenberg, G., Salomaa, A.: Insertion-deletion systems. In: DNA Computing: New Computing Paradigms. Texts in Theoretical Computer Science, pp. 187–215. Springer, Heidelberg (1998)

17.

Vorel, V.: On basic properties of jumping finite automata. Int. J. Found. Comput. Sci., conditionally accepted in 2015. http://arxiv.org/abs/1511.08396

Title: Two Results on Discontinuous Input Processing
Author: Vojtěch Vorel
Publisher: Springer International Publishing
Book: Descriptional Complexity of Formal Systems
Print ISBN: 978-3-319-41113-2

Electronic ISBN: 978-3-319-41114-9

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-41114-9_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner