Descriptional Complexity of Bounded Regular Languages

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9777
• 期：1
• 页码：138-152
• 全文大小：410 KB
• 参考文献：1.Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185–190 (1992)MathSciNet CrossRef MATH
  2.Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35), 3209–3222 (2009)MathSciNet CrossRef MATH
  3.Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47(2), 149–158 (1986)MathSciNet CrossRef MATH
  4.Chrobak, M.: Errata to “Finite automata and unary languages”. Theoret. Comput. Sci. 302, 497–498 (2003)MathSciNet CrossRef
  5.Erickson, M.J.: Introduction to Combinatorics. Wiley, New York (1996)CrossRef MATH
  6.Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. CoRR abs/1509.03254 (2015). http://​arxiv.​org/​abs/​1509.​03254
  7.Ginsburg, S., Spanier, E.H.: Bounded regular sets. Proc. Amer. Math. Soc. 17(5), 1043–1049 (1966)MathSciNet CrossRef MATH
  8.Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw Hill, New York (1966)MATH
  9.Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59, 75–77 (1996)MathSciNet CrossRef MATH
  10.Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)MATH
  11.Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978)MathSciNet CrossRef MATH
  12.Ibarra, O.H., Ravikumar, B.: On bounded languages and reversal-bounded automata. Inf. Comput. 246, 30–42 (2016)MathSciNet CrossRef MATH
  13.Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. Int. J. Found. Comput. Sci. 23(6), 1291–1306 (2012)MathSciNet CrossRef MATH
  14.Leiss, E.L.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)MathSciNet CrossRef MATH
  15.Malcher, A., Pighizzini, G.: Descriptional complexity of bounded context-free languages. Inf. Comput. 227, 1–20 (2013)MathSciNet CrossRef MATH
  16.Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT 1971, pp. 188–191. IEEE (1971)
  17.Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal’s function. Int. J. Found. Comput. Sci. 13, 145–159 (2002)MathSciNet CrossRef MATH
  18.Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets. J. Autom. Lang. Comb. 2, 177–186 (1997)MathSciNet MATH
  19.Valiant, L.G.: Regularity and related problems for deterministic pushdown automata. J. ACM 22, 1–10 (1975)MathSciNet CrossRef MATH
  20.Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb. 6, 221–234 (2001)MathSciNet MATH
  21.Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125(2), 315–328 (1994)MathSciNet CrossRef MATH
  
• 作者单位：Andrea Herrmann (16)
  Martin Kutrib (16)
  Andreas Malcher (16)
  Matthias Wendlandt (16)
  
  16. Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392, Giessen, Germany
  
• 丛书名：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 the descriptional complexity of the subregular language classes of (strongly) bounded regular languages. In the first part, we study the costs for the determinization of nondeterministic finite automata accepting strongly bounded regular languages. The upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second part, we study for (strongly) bounded languages the deterministic operational state complexity of the Boolean operations as well as the operations reversal, concatenation, and iteration. In detail, we present upper and lower bounds and we develop for the proof of the lower bounds a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages.