Unary Self-verifying Symmetric Difference Automata

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9777
• 期：1
• 页码：180-191
• 全文大小：273 KB
• 参考文献：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.Van Zijl, L.: Generalized nondeterminism and the succinct representation of regular languages. Ph.D. thesis, University of Stellenbosch (1997). http://​www.​cs.​sun.​ac.​za/​~lvzijl/​publications/​boek.​ps.​gz
  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)MathSciNet CrossRef MATH
  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)MathSciNet CrossRef MATH
  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)MathSciNet CrossRef MATH
  
• 作者单位：Laurette Marais (16) (17)
  Lynette van Zijl (16)
  
  16. Department of Computer Science, Stellenbosch University, Stellenbosch, South Africa
  17. Meraka Institute, CSIR, Pretoria, South Africa
  
• 丛书名：Descriptional Complexity of Formal Systems
• ISBN：978-3-319-41114-9
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9777

文摘

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.