Abstract
We prove that a minimal automaton has the minimal adjacency matrix rank and the minimal adjacency matrix nullity among all equivalent deterministic automata. Our proof uses equitable partition (from graph spectra theory) and Nerode partition (from automata theory). This result leads to the notion of rank of a regular language L, which is the minimal adjacency matrix rank of a deterministic automaton that recognises L. We then define and focus on rank-one languages. We also define the expanded canonical automaton of a rank-one language.
The full paper of this work with more detailed description and many useful examples is avalable at [12].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Béal, M.P., Crochemore, M.: Minimizing incomplete automata. In: Finite-State Methods and Natural Language Processing (FSMNLP 2008), pp. 9–16. Joint Research Center (2008), http://igm.univ-mlv.fr/~beal/Recherche/Publications/minimizingIncomplete.pdf
Choffrut, C., Goldwurm, M.: Rational transductions and complexity of counting problems. Mathematical Systems Theory 28(5), 437–450 (1995), http://dblp.uni-trier.de/db/journals/mst/mst28.html#ChoffrutG95a
Goldberg, A., Sipser, M.: Compression and ranking. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 440–448. ACM, New York (1985), http://doi.acm.org/10.1145/22145.22194
Mieghem, P.V.: Graph Spectra for Complex Networks. Cambridge University Press, New York (2011)
Nerode, A.: Linear automaton transformations. Proceedings of the American Mathematical Society 9(4), 541–544 (1958)
Osnaga, S.M.: On rank one matrices and invariant subspaces. Balkan Journal of Geometry and its Applications (BJGA) 10(1), 145–148 (2005), http://eudml.org/doc/126283
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, New York (2009)
Shur, A.M.: Combinatorial complexity of regular languages. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol. 5010, pp. 289–301. Springer, Heidelberg (2008)
Shur, A.M.: Combinatorial characterization of formal languages. CoRR abs/1010.5456 (2010), http://dblp.uni-trier.de/db/journals/corr/corr1010.html#abs-1010-5456
Sin’ya, R.: Rans: More advanced usage of regular expressions, http://sinya8282.github.io/RANS/
Sin’ya, R.: Text compression using abstract numeration system on a regular language. Computer Software 30(3), 163–179 (2013), English extended abstract is available at http://arxiv.org/abs/1308.0267 (in Japanese)
Sin’ya, R.: Graph spectral properties of deterministic finite au tomata (full paper, 12 pages) (2014), http://www.shudo.is.titech.ac.jp/members/sinya
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Sin’ya, R. (2014). Graph Spectral Properties of Deterministic Finite Automata. In: Shur, A.M., Volkov, M.V. (eds) Developments in Language Theory. DLT 2014. Lecture Notes in Computer Science, vol 8633. Springer, Cham. https://doi.org/10.1007/978-3-319-09698-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-09698-8_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09697-1
Online ISBN: 978-3-319-09698-8
eBook Packages: Computer ScienceComputer Science (R0)