| dbo:abstract
|
- La complexité en états (en anglais « state complexity ») est un thème en informatique théorique qui traite de la taille d'automates abstraits, tels que les diverses variantes des automates finis reconnaissant un langage rationnel donné. Un exemple typique dans ce domaine est le résultat selon lequel un automate fini non déterministe à états peut être simulé par un automate fini déterministe à au plus états, et que cette borne peut être atteinte. La complexité en états d'un langage régulier est la taille, mesurée en nombre d'états, du plus petit automate fini, soit déterministe, soit non déterministe qui reconnaît ce langage. La complexité opérationnelle (en anglais « operational state complexity ») est la description de la complexité en états des diverses opérations sur les langages qui préservent leur régularité. On distingue entre plusieurs problèmes dans cette thématique : la transformation d'un modèle d'automate en un autre, et la complexité des opérations sur les langages et leurs automates. Parfois, des résultats existent sur des sous-familles de langages réguliers. Enfin, il apparaît que dans le cas des langages sur un alphabet de taille donnée, et notamment sur un alphabet à une seule lettre (alphabet unaire), des résultats plus précis peuvent être formulés. Plusieurs exposés de synthèse ont été rédigés sur ces problèmes, par Holzer et Kutrib et par Gao et al.. La détermination de la complexité d'un opération ou d'une transformation demande deux informations : d'abord un procédé général dont on sait majorer le coût, en nombre d'états, dans tous les cas ; ensuite un jeu d'exemples qui montrent que la majoration est en fait une borne supérieure, c'est-à-dire effectivement atteinte. L'exemple le plus connu est la déterminisation d'un automate fini non déterministe à n états : l'algorithme de la construction par sous-ensembles fournit un automate qui a toujours au plus états ; la deuxième étape demande de fournir des exemples où cette borne est effectivement atteinte. (fr)
- La complexité en états (en anglais « state complexity ») est un thème en informatique théorique qui traite de la taille d'automates abstraits, tels que les diverses variantes des automates finis reconnaissant un langage rationnel donné. Un exemple typique dans ce domaine est le résultat selon lequel un automate fini non déterministe à états peut être simulé par un automate fini déterministe à au plus états, et que cette borne peut être atteinte. La complexité en états d'un langage régulier est la taille, mesurée en nombre d'états, du plus petit automate fini, soit déterministe, soit non déterministe qui reconnaît ce langage. La complexité opérationnelle (en anglais « operational state complexity ») est la description de la complexité en états des diverses opérations sur les langages qui préservent leur régularité. On distingue entre plusieurs problèmes dans cette thématique : la transformation d'un modèle d'automate en un autre, et la complexité des opérations sur les langages et leurs automates. Parfois, des résultats existent sur des sous-familles de langages réguliers. Enfin, il apparaît que dans le cas des langages sur un alphabet de taille donnée, et notamment sur un alphabet à une seule lettre (alphabet unaire), des résultats plus précis peuvent être formulés. Plusieurs exposés de synthèse ont été rédigés sur ces problèmes, par Holzer et Kutrib et par Gao et al.. La détermination de la complexité d'un opération ou d'une transformation demande deux informations : d'abord un procédé général dont on sait majorer le coût, en nombre d'états, dans tous les cas ; ensuite un jeu d'exemples qui montrent que la majoration est en fait une borne supérieure, c'est-à-dire effectivement atteinte. L'exemple le plus connu est la déterminisation d'un automate fini non déterministe à n états : l'algorithme de la construction par sous-ensembles fournit un automate qui a toujours au plus états ; la deuxième étape demande de fournir des exemples où cette borne est effectivement atteinte. (fr)
|
