Abstract
We study FAD-languages, which are regular languages defined by finite sets of forbidden factors, together with their “canonical” recognizing automata. We are mainly interested in the possible asymptotic orders of growth for such languages. We analyze certain simplifications of sets of forbidden factors and show that they “almost” preserve the canonical automata. Using this result and structural properties of canonical automata, we describe an algorithm that effectively lists all canonical automata having a strong component isomorphic to a given digraph, or reports that no such automata exist. This algorithm can be used, in particular, to prove the existence of a FAD-language over a given alphabet with a given exponential growth rate. On the other hand, we provide an example showing that the algorithm cannot prove non-existence of a FAD-language having a given growth rate. Finally, we provide some examples of canonical automata with a nontrivial condensation graph and of FAD-languages with a “complex” order of growth.
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., Perrin, D.: Symbolic dynamics and finite automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 463–505. Springer (1997)
Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words. Inform. Process. Lett. 67, 111–117 (1998)
Govorov, V.E.: Graded algebras. Math. Notes 12, 552–556 (1972)
Milnor, J.: Growth of finitely generated solvable groups. J. Diff. Geom. 2, 447–450 (1968)
Morse, M., Hedlund, G.A.: Symbolic dynamics. Amer. J. Math. 60, 815–866 (1938)
Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. Springer, New York (1978)
Schützenberger, M.P.: On finite monoids having only trivial subgroups. Information and Computation 8, 190–194 (1965)
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.: Polynomial languages with finite antidictionaries. RAIRO Inform. Théor. App. 43, 269–280 (2009)
Shur, A.M.: Languages with finite antidictionaries: growth index and properties of automata. Proc. Ural State Univ. 74, 220–245 (2010) (in Russian)
Shur, A.M.: Growth properties of power-free languages. Computer Science Review 6, 187–208 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shur, A.M. (2013). Languages with a Finite Antidictionary: Growth-Preserving Transformations and Available Orders of Growth. In: Béal, MP., Carton, O. (eds) Developments in Language Theory. DLT 2013. Lecture Notes in Computer Science, vol 7907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38771-5_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-38771-5_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38770-8
Online ISBN: 978-3-642-38771-5
eBook Packages: Computer ScienceComputer Science (R0)