Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-03T01:29:05.818Z Has data issue: false hasContentIssue false
  • English
  • Français

The genus of regular languages

Published online by Cambridge University Press:  20 May 2016

GUILLAUME BONFANTE  and
FLORIAN DELOUP
GUILLAUME BONFANTE
Affiliation:
LORIA, Université de Lorraine, Campus scientifique, B.P. 239, 54506 Vandoeuvre-lès-Nancy Cedex, France Email: [email protected]
FLORIAN DELOUP
Affiliation:
Institut de Mathématiques, Université Paul Sabatier, Toulouse III, 118 Route de Narbonne, 31069 Toulouse cedex 9, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, an FSA can be seen as a graph for which the notion of genus arises. At the same time, an FSA has a semantics via its underlying language. It is then natural to make a connection between the languages and the notion of genus. After we introduce and justify the the notion of the genus for regular languages, the following questions are addressed. First, depending on the size of the alphabet, we provide upper and lower bounds on the genus of regular languages: we show that under a relatively generic condition on the alphabet and the geometry of the automata, the genus grows at least linearly in terms of the size of the automata. Second, we show that the topological cost of the powerset determinization procedure is exponential. Third, we prove that the notion of minimization is orthogonal to the notion of genus. Fourth, we build regular languages of arbitrary large genus: the notion of genus defines a proper hierarchy of regular languages.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Issue 1 , January 2018 , pp. 14 - 44
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bonfante, G. and Deloup, F. (2015). Computability of regular language genus, arxiv.org/abs/1511.09405.Google Scholar
Bezáková, I. and Pál, M. (1999). Planar Finite Automata, Master Thesis, Comenius University, Bratislava.Google Scholar
Book, R.V. and Chandra, A.K. (1976). Inherently nonplanar automata. Acta Informatica 6 (1) 89–94.CrossRefGoogle Scholar
Bredon, G.E. (1993). Geometry and Topology, Graduate Texts in Math., volume 139, Springer, New York.CrossRefGoogle Scholar
Carbone, A. (2009). Logical structures and genus of proofs. Annals of Pure and Applied Logic 161 (2) 139–149.CrossRefGoogle Scholar
Chen, R.-W., Kajitani, Y. and Chan, S.-P. (1983). A graph-theoretic via minimization algorithm for two-layer printed circuit boards. IEEE Transactions on Circuits and Systems 30 (5) 284–299.CrossRefGoogle Scholar
Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 128–140, http://math.dartmouth.edu/~euler/docs/originals/E053.pdf. (Reprinted and translated in Biggs, N.L., Lloyd, E.K. and Wilson, R.J. (1976). Graph Theory 1736–1936, Oxford University Press.)Google Scholar
Gao, Y., Moreira, N., Reis, R. and Yu, S. (2012). A review on state complexity of individual operations. Technical Report, Universidade do Porto.Google Scholar
Hopcroft, J., Motwani, R. and Ullman, J. (2006). Introduction to Automata Theory, Languages, and Computation (3rd edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.Google Scholar
Jaeger, F. (1985). A survey of the cycle double cover conjecture. Annals of Discrete Mathematics 27 in Cycles in Graphs, North-Holland Mathematics Studies 27, 1–12.Google Scholar
Myhill, J. (1957). Finite automata and the representation of events. Technical Report, WADD TR-57-624, Wright Patterson AFB, Ohio.Google Scholar
Nerode, A. (1958). Linear automaton transformations. Proceedings of the American Mathematical Society 9 541–544.CrossRefGoogle Scholar
Rozenberg, G. and Salomaa, A. (eds.) (2006). Handbook of Formal Languages, vol. 1, Springer.Google Scholar
Sakarovitch, J. (2009). Elements of Automata Theory, Cambridge University Press.CrossRefGoogle Scholar
Stallmann, M., Hughes, T. and Liu, W. (1990). Unconstrained via minimization for topological multilayer routing. IEEE Transactions on Computer-Aided Design 9 (9) 970–980.CrossRefGoogle Scholar
Statman, R. (1974). Structural Complexity of Proofs, Ph.D. dissertation. Department of Philosophy, Stanford University.Google Scholar
Huy Xuong, N. (1977). Sur quelques problems d'immersion d'un graphe dans une surface, Ch. 3, Ph.D. Thesis, Grenoble, France.Google Scholar
Youngs, J.W.T. (1963). Minimal imbeddings and the genus of a graph. Journal of Mathematics and Mechanics 12 303–305.Google Scholar
Yu, S. (2000). State complexity of regular languages. Journal of Automata, Languages and Combinatorics 6 221–234.Google Scholar