Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cross-Layer Adaptation in Multi-layer Autonomic Systems (Invited Talk) Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Two-Head Finite-State Acceptors with Translucent Letters

Authors : Benedek Nagy, Friedrich Otto

Published in: SOFSEM 2019: Theory and Practice of Computer Science

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Finite-state acceptors are studied that have two heads that read the input from opposite sides. In addition, a set of translucent letters is associated with each state. It is shown that these two-head automata are strictly more expressive than the model with a single head, but that they still only accept languages that have a semi-linear Parikh image. In fact, we obtain a characterization for the class of linear context-free trace languages in terms of a specific class of two-head finite-state acceptors with translucent letters.

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 Minimizing the Cost of Team Exploration
next chapter Do Null-Type Mutation Operators Help Prevent Null-Type Faults?
Literature
1.
Bedregal, B.R.C.: Some subclasses of linear languages based on nondeterministic linear automata. arXiv:​10276v1 (2016)
2.
Diekert, V., Rozenberg, G.: The Book of Traces. World Scientific, Singapore (1995)CrossRef
3.
Freund, R., Păun, Gh., Rozenberg, G., Salomaa, A.: Watson-Crick finite automata. In: Rubin, H., Wood, D.H. (eds.) DNA Based Computers, Proceedings of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 297–328. DIMACS/AMS (1999)
4.
5.
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)MATH
6.
7.
8.
Nagy, B.: A class of 2-head finite automata for linear languages. Triangle: Lang. Math. Approaches 8, 89–99 (2012)
9.
Nagy, B.: On a hierarchy of \(5^{\prime } \rightarrow 3^{\prime }\)sensing Watson-Crick finite automata languages. J. Log. Comput. 23, 855–872 (2013)MathSciNetCrossRef
10.
Nagy, B., Kovács, L.: Finite automata with translucent letters applied in natural and formal language theory. In: Nguyen, N.T., Kowalczyk, R., Fred, A., Joaquim, F. (eds.) Transactions on Computational Collective Intelligence XVII. LNCS, vol. 8790, pp. 107–127. Springer, Heidelberg (2014). https://​doi.​org/​10.​1007/​978-3-662-44994-3_​6CrossRef
11.
12.
13.
Nagy, B., Otto, F.: CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO Theor. Inform. Appl. 45, 413–448 (2011)MathSciNetCrossRef
14.
Nagy, B., Otto, F.: Finite-state acceptors with translucent letters. In: Bel-Enguix, G., Dahl, V., De La Puente, A.O. (eds.) BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology, Proceedings, pp. 3–13. SciTePress, Portugal (2011)
15.
Nagy, B., Otto, F.: On CD-systems of stateless deterministic R-automata with window size one. J. Comput. Syst. Sci. 78, 780–806 (2012)MathSciNetCrossRef
16.
Nagy, B., Otto, F.: Globally deterministic CD-systems of stateless R-automata with window size 1. Int. J. Comput. Math. 90, 1254–1277 (2013)MathSciNetCrossRef
17.
18.
Rosenberg, A.L.: A machine realization of the linear context-free languages. Inf. Control 10, 175–188 (1967)CrossRef
Metadata
Title
Two-Head Finite-State Acceptors with Translucent Letters
Authors
Benedek Nagy
Friedrich Otto
Copyright Year
2019
Book
SOFSEM 2019: Theory and Practice of Computer Science

Print ISBN: 978-3-030-10800-7

Electronic ISBN: 978-3-030-10801-4

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-10801-4_32

Premium Partner

    Image Credits