Geometrical Regular Languages and Linear Diophantine Equations
| Autor: | Jean-Philippe Dubernard, Franck Guingne, Hadrien Jeanne, Jean-Marc Champarnaud |
|---|---|
| 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), Markus Holzer and Martin Kutrib and Giovanni Pighizzini |
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
Strongly connected component Diophantine equation 010102 general mathematics 0102 computer and information sciences 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] Set (abstract data type) Algebra Arbitrarily large Regular language 010201 computation theory & mathematics Simple (abstract algebra) 0101 mathematics State diagram Connectivity Mathematics |
| Zdroj: | Lecture Notes in Computer Science Descriptional Complexity of Formal Systems-13th International Workshop, DCFS 2011, Giessen/Limburg, Germany, July 25-27, 2011. Proceedings DCFS 2011 DCFS 2011, Jul 2011, Giessen/Limburg, Germany. pp.107-120 Descriptional Complexity of Formal Systems ISBN: 9783642225994 DCFS |
| ISSN: | 0302-9743 |
| Popis: | International audience; We present a new method for checking whether a regular language over an arbitrarily large alphabet is semi-geometrical or whether it is geometrical. This method makes use first of the partitioning of the state diagram of the minimal automaton of the language into strongly connected components and secondly of the enumeration of the simple cycles in each component. It is based on the construction of systems of linear Diophantine equations the coefficients of which are deduced from the the set of simple cycles. This paper addresses the case of a strongly connected graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|