Reference List

Filter:

[RS59] Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM J Research Development, 3(2):114-129, 1959.
[Lup63] O. B. Lupanov. A comparison of two types of finite sources. Problemy Kibernetiki, 9:321-326, 1963. German translation: Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6 (1966), 328-335.
[PRS63] Mika Perles, Michael O. Rabin, and E. Shamir. The theory of definite automata. Electronic Computers, IEEE Transactions on, EC-12(3):233-243, June 1963. [ DOI ]
[SH63] Richard E. Stearns and Juris Hartmanis. Regularity preserving modifications of regular expressions. Information and Control, 6(1):55-69, 1963.
[Brz64] J. A. Brzozowski. Derivatives of regular expressions. JACM, 11(4):481-494, October 1964.
[Lyu64a] Yu I. Lyubich. Estimates for optimal determinization of nondeterministic autonomous automata. Sibirskii Matematichskii Zhurnal, 5:337–355, 1964. (in Russian).
[Lyu64b] Yu I. Lyubich. Estimates of the number of states that arise in the determinization of a nondeterministic autonomous automaton. Dokllady Akademii Nauk SSSR, pages 41-43, 1964. English translation in Soviet Mathematics Doklady, 5, 345–348 (1964).
[Sal64a] Arto Salomaa. On the reducibility of events represented in automata. Annales Academiae Scientiarum Fennicae, Series A(I. Mathematica 353), 1964.
[Sal64b] Arto Salomaa. Theorems on the representation of events in Moore-automata. Turun Yliopiston Julkaisuja Annales Universitatis Turkuensis, Series A(69), 1964.
[PP65] Azaria Paz and Bezalel Peleg. Ultimate-definite and symmetric-definite events and automata. J. ACM, 12(3):399-410, 1965. [ http ]
[Sch65] M. P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965.
[Mir66] Boris G. Mirkin. On dual automata. Kibernetika, 2:7-10, 1966. English translation in Cybernetics 2, 6–9 (1966).
[Hai69] L. H. Haines. On free monoids partially ordered by embedding. J. Combin. Theory, 6:94-98, 1969.
[Sal69] Arto Salomaa. Theory of Automata. Pergamon Press, Oxford, 1969.
[Mas70] A. N. Maslov. Estimates of the number of states of finite automata. Dokllady Akademii Nauk SSSR, 194:1266–1268, 1970. English translation in Soviet Mathematics Doklady, 11 , 1373-1375 (1970).
[Con71] John H. Conway. Regular algebra and finite machines. William Clowes& Sons, Great Britain, 1971.
[MP71] Robert McNaughton and Seymour Papert. Counter-free automata. In Research Monographs, volume 65. MIT Press, 1971.
[MF71] Albert R. Meyer and Michael J. Fischer. Economy of description by automata, grammars, and formal systems. In Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory, 13-15 October 1971, East Lansing, Michigan, USA, pages 188-191, Los Alamitos, 1971. IEEE Society Press.
[Moo71] Frank R. Moore. On the bounds for state-set size in the proofs of equivalence between deterministic, nondeter- ministic, and two-way finite automata. IEEE Transactions on computers, 2:1211-1214, 1971.
[Thi72] Gabriel Thierrin. Convex languages. In M. Nivat, editor, ICALP, pages 481-492. North-Holland, 1972.
[Man73] Robert Mandl. Precise bounds associated with the subset construction on various classes of nondeterministic finite automata. In Princeton Conference on Information and System Sciences, page 263–267, 1973.
[Mas73] A. N. Maslov. Cyclic shift operation for languages. Probl. Inf. Transm, 9:333–338, 1973.
[GK74] Arthur Gill and Lawrence T. Kou. Multiple-entry finite automata. J. Comput. System Sci., 9:1-19, 1974.
[SM76] Joel I. Seiferas and Robert McNaughton. Regularity-preserving relations. Theor. Comput. Sci., 2(2):147-154, 1976.
[SS78] William J. Sakoda and Michael Sipser. Nondeterminism and the size of two way finite automata. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, 1-3 May 1978, San Diego, California, USA, pages 275-286. ACM, 1978.
[Sip80] Michael Sipser. Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci., 21(2):195-202, 1980.
[CKS81] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. [ DOI ]
[Lei81] Ernst L. Leiss. Succint representation of regular languages by boolean automata. Theor. Comput. Sci., 13:323-330, 1981.
[Lei85] Ernst L. Leiss. Succinct representation of regular languages by boolean automata II. Theor. Comput. Sci., 38:133-136, 1985.
[Chr86] Marek Chrobak. Finite automata and unary languages. Theor. Comput. Sci., 47(3):149-158, 1986.
[RI89] Bala Ravikumar and Oscar H. Ibarra. Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput., 18(6):1263-1282, 1989.
[dLV90] A. de Luca and S. Varricchio. Some combinatorial properties of factorial languages. In R. Capocelli, editor, Sequences, pages 258-266. Springer, 1990.
[Rav90] Bala Ravikumar. Some applications of a technique of Sakoda and Sipser. SIGACT News, 21(4):73-77, 1990.
[Bir91] Jean-Camille Birget. Intersection of regular languages and state complexity. ACM SIGACT News, 22(2), 1991.
[JR91] Tao Jiang and Bala Ravikumar. A note on the space complexity of some decision problems for finite automata. Information Processing Letters, 1:25-31, 1991.
[YZ91] Sheng Yu and Qingyu Zhuang. On the state complexity of intersection of regular languages. ACM SIGACT News, 22(7):52-54, 1991.
[Rev92] Dominique Revuz. Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci., 92(1):181-189, 1992.
[Bir93] Jean-Camille Birget. Partial orders on words, minimal elements of regular languages and state complexity. Theor. Comput. Sci., 119(2):267-291, 1993.
[YZS94] Sheng Yu, Qingyu Zhuang, and Kai Salomaa. The state complexities of some basic operations on regular languages. Theor. Comput. Sci., 125(2):315-328, 1994.
[Bir96] Jean-Camille Birget. The state complexity of Σ L and its connection with temporal logic. Inf. Process. Lett., 58(4):185-188, 1996. [ http ]
[GS96] Ian Glaister and Jeffrey Shallit. A lower bound technique for the size of nondeterministic finite automata. Inf. Process. Lett., 59(2):75-77, 1996. [ http ]
[Hro97] Juraj Hromkovic. Communication Complexity and Parallel Computing. Springer, 1997.
[JK97] Helmut Jürgensen and Stavros Konstantinidis. Codes. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 1, pages 511-607. Springer, 1997.
[SY97] Kai Salomaa and Sheng Yu. NFA to DFA transformation for finite languages over arbitrary alphabets. Journal of Automata, Languages and Combinatorics, 2(3):177-186, 1997.
[Yu97] Sheng Yu. Regular languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 1, pages 41-110. Springer, 1997.
[MRS98] Alexandru Mateescu, Grzegorz Rozenberg, and Arto Salomaa. Shuffle on trajectories: Syntactic constraints. Theor. Comput. Sci., 197(1-2):1-56, 1998. [ http ]
[dLV99] A. de Luca and S. Varricchio. Finiteness and Regularity in Semigroups and Formal Languages. Springer, 1999.
[Nic99] Cyril Nicaud. Average state complexity of operations on unary automata. In Miroslaw Kutylowski, Leszek Pacholski, and Tomasz Wierzbicki, editors, Mathematical Foundations of Computer Science 1999, 24th International Symposium, MFCS'99, Szklarska Poreba, Poland, September 6-10, 1999, Proceedings, volume 1672 of Lecture Notes in Computer Science, pages 231-240. Springer, 1999. [ http ]
[IKT00a] Masami Ito, Lila Kari, and Gabriel Thierrin. Shuffle and scattered deletion closure of languages. Theor. Comput. Sci., 245(1):115-133, 2000. [ http ]
[IMP00] Kazuo Iwama, Akihiro Matsuura, and Mike Paterson. A family of NFA's which need 2n -α deterministic states. In Mogens Nielsen and Branislav Rovan, editors, Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings, volume 1893 of Lecture Notes in Computer Science, pages 436-445. Springer, 2000. [ http ]
[IKT00b] Kazuo Iwama, Yahiko Kambayashi, and Kazuya Takaki. Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theor. Comput. Sci., 237(1-2):485-494, 2000. [ http ]
[MP00] Carlo Mereghetti and Giovanni Pighizzini. Optimal simulations between unary automata. SIAM J. Comput., 30(6):1976-1992, 2000. [ http ]
[Nic00] Cyril Nicaud. Étude du comportement en moyenne des automates finis et des languages rationels. PhD thesis, Université de Paris 7, 2000.
[Yu01] Sheng Yu. State complexity of regular languages. Journal of Automata, Languages and Combinatorics, 6(2):221-234, 2001.
[CSY01] Cezar Câmpeanu, Nicolae Santean, and Sheng Yu. Minimal cover-automata for finite languages. Theor. Comput. Sci., 267(1-2):3-16, 2001. [ http ]
[CISY01] Cezar Câmpeanu, Karel Culik II, Kai Salomaa, and Sheng Yu. State complexity of basic operations on finite languages. In Oliver Boldt and Helmut Jürgensen, editors, Automata Implementation, 4th International Workshop on Implementing Automata, WIA'99, Potsdam, Germany, July 17-19, 1999, Revised Papers, volume 2214 of Lecture Notes in Computer Science, pages 60-70. Springer, 2001. [ http ]
[HSY01] Markus Holzer, Kai Salomaa, and Sheng Yu. On the state complexity of k-entry deterministic finite automata. Journal of Automata, Languages and Combinatorics, 6(4):453-466, 2001.
[Jir01] Galina Jirásková. Note on minimal finite automata. In Jiri Sgall, Ales Pultr, and Petr Kolman, editors, Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings, volume 2136 of Lecture Notes in Computer Science, pages 421-431. Springer, 2001. [ http ]
[Kir01] George Anton Kiraz. Compressed storage of sparse finite-state transducers. In Oliver Boldt and Helmut Jürgensen, editors, Automata Implementation, 4th International Workshop on Implementing Automata, WIA'99, Potsdam, Germany, July 17-19, 1999, Revised Papers, volume 2214 of Lecture Notes in Computer Science, pages 109-121. Springer, 2001. [ http ]
[Pig01] Giovanni Pighizzini. Unary language concatenation and its state complexity. In Sheng Yu and Andrei Paun, editors, Implementation and Application of Automata, 5th International Conference, CIAA 2000, London, Ontario, Canada, July 24-25, 2000, Revised Papers, volume 2088 of Lecture Notes in Computer Science, pages 252-262. Springer, 2001.
[Sha01] Jeffrey Shallit. State complexity and Jacobsthal's function. In Sheng Yu and Andrei Paun, editors, Implementation and Application of Automata, 5th International Conference, CIAA 2000, London, Ontario, Canada, July 24-25, 2000, Revised Papers, volume 2088 of Lecture Notes in Computer Science, pages 272-278. Springer, 2001.
[Shy01] Huei-Jan Shyr. Free Monoids and Languages. Hon Min Book Co., Taiwan, 2001.
[CSY02] Cezar Câmpeanu, Kai Salomaa, and Sheng Yu. Tight lower bound for the state complexity of shuffle of regular languages. Journal of Automata, Languages and Combinatorics, 7(3):303-310, 2002.
[Dom02] Michael Domaratzki. State complexity of proportional removals. Journal of Automata, Languages and Combinatorics, 7(4):455-468, 2002.
[GKK+02] Jonathan Goldstine, Martin Kappes, Chandra M. R. Kintala, Hing Leung, Andreas Malcher, and Detlef Wotschke. Descriptional complexity of machines with limited resources. J. UCS, 8(2):193-234, 2002. [ http ]
[Hro02] Juraj Hromkovic. Descriptional complexity of finite automata: Concepts and open problems. Journal of Automata, Languages and Combinatorics, 7(4):519-531, 2002.
[PS02] Giovanni Pighizzini and Jeffrey Shallit. Unary language operations, state complexity and Jacobsthal's function. International Journal of Foundations of Computer Science, 13(1):145-159, 2002.
[Yu02] Sheng Yu. State complexity of finite and infinite regular languages. Bulletin of the EATCS, 76:142-152, 2002.
[HK03a] Markus Holzer and Martin Kutrib. State complexity of basic operations on nondeterministic finite automata. In Jean-Marc Champarnaud and Denis Maurel, editors, Implementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers, volume 2608 of Lecture Notes in Computer Science, pages 148-157. Springer, 2003. [ http ]
[Ell03] Keith Ellul. Descriptional complexity measures of regular languages. Master's thesis, University of Waterloo, 2003.
[Chr03] Marek Chrobak. Errata to: "finite automata and unary languages". Theor. Comput. Sci., 302(1-3):497-498, 2003.
[ÉGLY03] Zoltán Ésik, Yuan Gao, Guangwu Liu, and Sheng Yu. Estimation of state complexity of combined operations. Theor. Comput. Sci., 410(35):3272-3280, October 2003. [ DOI | http ]
[HK03b] Markus Holzer and Martin Kutrib. Unary language operations and their nondeterministic state complexity. In Masami Ito and Masafumi Toyama, editors, Developments in Language Theory, 6th International Conference, DLT 2002, Kyoto, Japan, September 18-21, 2002, Revised Papers, volume 2450 of Lecture Notes in Computer Science, pages 162-172. Springer, 2003.
[CH04] Cezar Câmpeanu and Wing Hong Ho. The maximum state complexity for finite languages. Journal of Automata, Languages and Combinatorics, 9(2/3):189-202, 2004.
[DS04] Michael Domaratzki and Kai Salomaa. State complexity of shuffle on trajectories. Journal of Automata, Languages and Combinatorics, 9(2/3):217-232, 2004.
[SWY04] Arto Salomaa, Derick Wood, and Sheng Yu. On the state complexity of reversals of regular languages. Theor. Comput. Sci., 320(2-3):315-329, 2004. [ http ]
[HJS05] M. Hricko, Galina Jirásková, and Alexander Szabari. Union and intersection of regular languages and descriptional complexity. In Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini, and Detlef Wotschke, editors, Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems, pages 170-181, Milano, Italy, 2005. University of Milano.
[EKSwW05] Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming wei Wang. Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics, 10(4):407-437, 2005.
[Gef05] Viliam Geffert. (Non)determinism and the size of one-way finite automata. In Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini, and Detelf Wotschke, editors, Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems, page 23–37. University of Milano, Italy, 2005.
[JJS05] Jozef Jirásek, Galina Jirásková, and Alexander Szabari. State complexity of concatenation and complementation of regular languages. International Journal of Foundations of Computer Science, 16(3):511-529, 2005.
[Jir05] Galina Jirásková. State complexity of some operations on binary regular languages. Theor. Comput. Sci., 330(2):287-298, 2005.
[MP05] Filippo Mera and Giovanni Pighizzini. Complementing unary nondeterministic automata. Theor. Comput. Sci., 330(2):349-360, 2005. [ http ]
[Yu05] Sheng Yu. State complexity: Recent results and open problems. Fundam. Inform., 64(1-4):471-480, 2005.
[GH06] Hermann Gruber and Markus Holzer. Finding lower bounds for nondeterministic state complexity is hard. In Oscar H. Ibarra and Zhe Dang, editors, Developments in Language Theory, 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Proceedings, volume 4036 of Lecture Notes in Computer Science, pages 363-374. Springer, 2006. [ http ]
[Ram06] Narad Rampersad. The state complexity of L2 and Lk. Information Proceesing Lettes, 98:231-234, 2006.
[Yu06] Sheng Yu. On the state complexity of combined operations. In Oscar H. Ibarra and Hsu-Chun Yen, editors, Implementation and Application of Automata, 11th International Conference, CIAA 2006, Taipei, Taiwan, August 21-23, 2006, Proceedings, volume 4094 of Lecture Notes in Computer Science, pages 11-22. Springer, 2006. [ http ]
[Gef07a] Viliam Geffert. Magic numbers in the state hierarchy of finite automata. Inf. Comput., 205(11):1652-1670, 2007. [ http ]
[Gef07b] Viliam Geffert. State hierarchy for one-way finite automata. Journal of Automata, Languages and Combinatorics, 12(1-2):139-145, 2007.
[GH07] Hermann Gruber and Markus Holzer. On the average state and transition complexity of finite languages. Theor. Comput. Sci., 387(2):155-166, 2007. [ http ]
[GHK07] Hermann Gruber, Markus Holzer, and Martin Kutrib. The size of Higman-Haines sets. Theor. Comput. Sci., 387(2):167-176, 2007. [ http ]
[Sal07] Kai Salomaa. Descriptional complexity of nondeterministic finite automata. In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors, Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007, Proceedings, volume 4588 of Lecture Notes in Computer Science, pages 31-35. Springer, 2007.
[SY07] Kai Salomaa and Sheng Yu. On the state complexity of combined operations and their estimation. International Journal of Foundations of Computer Science, 18(4):683-698, July 2007.
[SSY07] Arto Salomaa, Kai Salomaa, and Sheng Yu. State complexity of combined operations. Theor. Comput. Sci., 383(2-3):140-152, 2007. [ http ]
[HS08] Yo-Sub Han and Kai Salomaa. State complexity of union and intersection of finite languages. Int. J. Found. Comput. Sci., 19(3):581-595, 2008. [ http ]
[JO08] Galina Jirásková and Alexander Okhotin. State complexity of cyclic shift. Rairo-Theoretical Informatics nd Applications, 42:335-360, March 2008. [ DOI ]
[CK08] Cezar Câmpeanu and Stavros Konstantinidis. State complexity of the subword closure operation with applications to DNA coding. International Journal of Foundations of Computer Science, 19(5):1099-1112, 2008.
[GÉLY08] Yuan Gao, Zoltán Ésik, Guangwu Liu, and Sheng Yu. State complexity of multiple boolean and catenation operations. Report, UWO(715), 2008. [ .pdf ]
[GSY08] Yuan Gao, Kai Salomaa, and Sheng Yu. The state complexity of two combined operations: Star of catenation and star of reversal. Fundamenta Informaticae, 83:75-89, January 2008.
[JJS08] Jozef Jirásek, Galina Jirásková, and Alexander Szabari. Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet. Int. J. Found. Comput. Sci., 19(3):617-631, 2008. [ http ]
[Jir08] Galina Jirásková. On the state complexity of complements, stars, and reversals of regular languages. In Masami Ito and Masafumi Toyama, editors, Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008. Proceedings, volume 5257 of Lecture Notes in Computer Science, pages 431-442. Springer, 2008. [ http ]
[LMVSY08] Guangwu Liu, Carlos Martín-Vide, Arto Salomaa, and Sheng Yu. State complexity of basic language operations combined with reversal. Inf. Comput., 206(9-10):1178-1186, 2008. [ url ]
[DO09] Michael Domaratzki and Alexander Okhotin. State complexity of power. Theor. Comput. Sci., 410(24-25):2377-2392, 2009.
[AB09] Thomas Ang and Janusz A. Brzozowski. Languages convex with respect to binary relations, and their closure properties. Acta Cybern., 19(2):445-464, 2009. [ http ]
[BPR09] Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata. Number 129 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009.
[BHK09] Henning Bordihn, Markus Holzer, and Martin Kutrib. Determination of finite automata accepting subregular languages. Theor. Comput. Sci., 410(35):3209-3222, 2009. [ http ]
[BGS09b] Janusz A. Brzozowski, Elyot Grant, and Jeffrey Shallit. Closures in formal languages: Concatenation, separation, and algorithms. CoRR, abs/0901.3763, 2009. [ http ]
[BGS09a] Janusz A. Brzozowski, Elyot Grant, and Jeffrey Shallit. Closures in formal languages and Kuratowski's theorem. In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 125-144. Springer, 2009. [ http ]
[BSX09] Janusz A. Brzozowski, Jeffrey Shallit, and Zhi Xu. Decision problems for convex languages. In Adrian Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 247-258. Springer, 2009. [ http ]
[BK09] Janusz A. Brzozowski and Stavros Konstantinidis. State-complexity hierarchies of uniform languages of alphabet-size length. Theor. Comput. Sci., 410(35):3223-3235, 2009. [ http ]
[DDS09] Mark Daley, Michael Domaratzki, and Kai Salomaa. State complexity of orthogonal catenation. CoRR, abs/0904.3366, 2009. [ http ]
[GY09] Yuan Gao and Sheng Yu. State complexity approximation. CoRR, abs/0907.5124, 2009. [ http ]
[GHK09] Hermann Gruber, Markus Holzer, and Martin Kutrib. More on the size of Higman-Haines sets: Effective constructions. Fundam. Inform., 91(1):105-121, 2009. [ http ]
[HSW09] Yo-Sub Han, Kai Salomaa, and Derick Wood. Nondeterministic state complexity of basic operations for prefix-free regular languages. Fundam. Inform., 90(1-2):93-106, 2009. [ http ]
[HS09] Yo-Sub Han and Kai Salomaa. State complexity of basic operations on suffix-free regular languages. Theor. Comput. Sci., 410(27-29):2537-2548, 2009. [ http ]
[HK09a] Markus Holzer and Martin Kutrib. Descriptional and computational complexity of finite automata. In Adrian Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 23-42. Springer, 2009. [ http ]
[HK09b] Markus Holzer and Martin Kutrib. Nondeterministic finite automata - recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci., 20(4):563-580, 2009. [ http ]
[Jir09a] Galina Jirásková. Concatenation of regular languages and descriptional complexity. In Anna E. Frid, Andrey Morozov, Andrey Rybalchenko, and Klaus W. Wagner, editors, Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings, volume 5675 of Lecture Notes in Computer Science, pages 203-214. Springer, 2009. [ http ]
[Jir09b] Galina Jirásková. Magic numbers and ternary alphabet. In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 300-311. Springer, 2009. [ http ]
[JO09a] Galina Jirásková and Alexander Okhotin. Nondeterministic state complexity of positional addition. CoRR, abs/0907.5072, 2009. [ http ]
[JO09b] Galina Jirásková and Palov Olejár. State complexity of union and intersection of binary suffix-free languages. Workshop on Non-Classical Models of Automata and Applications (NCMA),August 31 - September 1, 2009, Wroclaw, Poland, 2009.
[KRS09] Jui-Yi Kao, Narad Rampersad, and Jeffrey Shallit. On NFAs where all states are final, initial, or both. Theor. Comput. Sci., 410(47-49):5010-5021, 2009. [ http ]
[KMR+09] Dalia Krieger, Avery Miller, Narad Rampersad, Bala Ravikumar, and Jeffrey Shallit. Decimations of languages and state complexity. Theor. Comput. Sci., 410(24-25):2401-2409, 2009. [ http ]
[RSR09] Narad Rampersad, Jeffrey Shallit, and Bala Ravikumar. State complexity of unique rational operations. Theor. Comput. Sci., 410:2431-2441, 2009.
[Brz10b] Janusz A. Brzozowski. Quotient complexity of regular languages. Journal of Automata, Languages and Combinatorics, 15(1/2):71-89, 2010.
[BGN10a] Frédérique Bassino, Laura Giambruno, and Cyril Nicaud. The average state complexity of rational operations on finite languages. Int. J. Found. Comput. Sci., 21(4):495-516, 2010. [ http ]
[BGN10b] Frédérique Bassino, Laura Giambruno, and Cyril Nicaud. Complexity of operations on cofinite languages. In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, volume 6034 of Lecture Notes in Computer Science, pages 222-233. Springer, 2010. [ http ]
[Brz10a] Janusz A. Brzozowski. Complexity in convex languages. In Adrian Horia Dediu, Henning Fernau, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings, volume 6031 of Lecture Notes in Computer Science, pages 1-15. Springer, 2010. [ http ]
[BJS10] Janusz A. Brzozowski, Galina Jirásková, and Joshua Smith. Quotient complexity of bifix-, factor-, and subword-free languages. CoRR, abs/1006.4843, 2010. [ http ]
[BJZ10] Janusz A. Brzozowski, Galina Jirásková, and Chenglong Zou. Quotient complexity of closed languages. In Farid M. Ablayev and Ernst W. Mayr, editors, Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, volume 6072 of Lecture Notes in Computer Science, pages 84-95. Springer, 2010. [ http ]
[BJL10] Janusz A. Brzozowski, Galina Jirásková, and Baiyu Li. Quotient complexity of ideal languages. In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, volume 6034 of Lecture Notes in Computer Science, pages 208-221. Springer, 2010. [ http ]
[BL10] Janusz A. Brzozowski and Bo Liu. Quotient complexity of star-free languages. CoRR, abs/1012.3962, 2010. [ http ]
[CGKY10a] Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. State complexity of catenation combined with star and reversal. CoRR, abs/1008.1648, 2010. [ http ]
[CGKY10b] Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. State complexity of two combined operations: Reversal-catenation and star-catenation. CoRR, abs/1006.4646, 2010. [ http ]
[DDS10] Mark Daley, Michael Domaratzki, and Kai Salomaa. Orthogonal concatenation: Language equations and state complexity. Journal of Universal Computer Science, 16(5):653-675, 2010.
[HS10] Yo-Sub Han and Kai Salomaa. Nondeterministic state complexity for suffix-free regular languages. CoRR, abs/1008.1661, 2010. [ http ]
[HJK10] Markus Holzer, Sebastian Jakobi, and Martin Kutrib. The magic number problem for subregular language families. CoRR, abs/1008.1653, 2010. [ http ]
[JK10] Galina Jirásková and Monika Krausová. Complexity in prefix-free regular languages. Electron. Proc. Theor. Comput. Sci., 31:197-204, August 2010. [ http ]
[JM10] Galina Jirásková and Tomás Masopust. Complexity in union-free regular languages. In Yuan Gao, Hanlin Lu, Shinnosuke Seki, and Sheng Yu, editors, Developments in Language Theory, 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings, volume 6224 of Lecture Notes in Computer Science, pages 255-266. Springer, 2010. [ http ]
[Okh10] Alexander Okhotin. On the state complexity of scattered substrings and superstrings. Fundam. Inform., 99(3):325-338, 2010. [ http ]
[PR10] Elena V. Pribavkina and Emanuele Rodaro. State complexity of prefix, suffix, bifix and infix operators on regular languages. In Yuan Gao, Hanlin Lu, Shinnosuke Seki, and Sheng Yu, editors, Developments in Language Theory, volume 6224 of Lecture Notes in Computer Science, pages 376-386. Springer, 2010. [ http ]
[Seb10] Juraj Sebej. Reversal of regular languages and state complexity. Master's thesis, P. J. Šafárik, University of Kosice, Slovakia, 2010.
[GSY11] Yuan Gao, Kai Salomaa, and Sheng Yu. Transition complexity of incomplete DFAs. Fundam. Inform., 110(1-4):143-158, 2011. [ url ]
[BY11] J. Brzozowski and Y. Ye. Syntactic complexity of ideal and closed languages. In Giancarlo Mauri and Alberto Leporati, editors, DLT 2011, volume 6795 of LNCS, pages 117-128. Springer Berlin / Heidelberg, 2011.
[JO11] Galina Jirásková and Alexander Okhotin. On the state complexity of star of union and star of intersection. Fundam. Inform., 109(2):161-178, 2011. [ url ]
[MMR13] Eva Maia, Nelma Moreira, and Rogério Reis. Incomplete transition complexity of basic operations on finite languages. In Stavros Konstantinidis, editor, CIAA 2013, LNCS. Springer, 2013.