Geometrical regular languages and linear Diophantine equations: The strongly connected case
| Autor: | Jean-Marc Champarnaud, Hadrien Jeanne, Jean-Philippe Dubernard, Franck Guingne |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU), Equipe Combinatoire et algorithmes (CA - LITIS), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe RL, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA) |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Strongly connected component General Computer Science Diophantine set Diophantine equation 010102 general mathematics Regular language Geometrical language 0102 computer and information sciences 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] Theoretical Computer Science Arbitrarily large 010201 computation theory & mathematics Deterministic automaton Parikh image Nondeterministic finite automaton 0101 mathematics State diagram Minimal deterministic automaton Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2012, 449, pp.54-63 |
| ISSN: | 1879-2294 0304-3975 |
| Popis: | International audience; Given an arbitrarily large alphabet Σ, we consider the family of regular languages over Σ for which the deterministic minimal automaton has a strongly connected state diagram. We present a new method for checking whether such a language is semi-geometrical or not and whether it is geometrical or not. This method makes use of the enumeration of the simple cycles of the state diagram. It is based on the construction of systems of linear Diophantine equations, where the coefficients are deduced from the set of simple cycles |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect