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:
Completely Reachable Automata Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Unary Self-verifying Symmetric Difference Automata

Authors : Laurette Marais, Lynette van Zijl

Published in: Descriptional Complexity of Formal Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We investigate self-verifying nondeterministic finite automata, in the case of unary symmetric difference nondeterministic finite automata (SV-XNFA). We show that there is a family of languages \(\mathcal {L}_{n\ge 2}\) which can always be represented non-trivially by unary SV-XNFA. We also consider the descriptional complexity of unary SV-XNFA, giving an upper and lower bound for state complexity.

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 Minimal and Reduced Reversible Automata
next chapter State Complexity of Prefix Distance of Subregular Languages
Footnotes
1
In GF(2), \(1+1=0\).
 
Literature
1.
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 1st edn. Addison-Wesley Longman Publishing Co., Inc., Boston (1990)MATH
2.
3.
Van der Merwe, B., Tamm, H., Van Zijl, L.: Minimal DFA for symmetric difference NFA. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 307–318. Springer, Heidelberg (2012)CrossRef
4.
Assent, I., Seibert, S.: An upper bound for transforming self-verifying automata into deterministic ones. RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications 41(3), 261–265 (2007)MathSciNetCrossRefMATH
5.
Hromkovič, J., Schnitger, G.: On the power of Las Vegas II. Two-way finite automata. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 433–442. Springer, Heidelberg (1999)CrossRef
6.
Jirásková, G., Pighizzini, G.: Optimal simulation of self-verifying automata by deterministic automata. Inf. Comput. 209(3), 528–535 (2011). Special Issue: 3rd International Conference on Language and Automata Theory and Applications (LATA 2009)MathSciNetCrossRefMATH
7.
Vuillemin, J., Gama, N.: Compact normal form for regular languages as Xor automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 24–33. Springer, Heidelberg (2009)CrossRef
8.
Stone, H.S.: Discrete Mathematical Structures and their Applications. Science Research Associates, Chicago (1973)MATH
9.
Dornhoff, L.L., Hohn, F.E.: Applied Modern Algebra. Macmillan Publishing Co., Inc., Collier Macmillan Publishers, New York, London (1978)MATH
10.
Geffert, V., Pighizzini, G.: Pairs of complementary unary languages with “balanced” nondeterministic automata. Algorithmica 63(3), 571–587 (2010)MathSciNetCrossRefMATH
Metadata
Title
Unary Self-verifying Symmetric Difference Automata
Authors
Laurette Marais
Lynette van Zijl
Copyright Year
2016
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_14

Premium Partner

    Image Credits