http://fr.dbpedia.org/resource/Automate_fini_inambigu (original) (raw)
En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers.
| Property | Value |
|---|---|
| dbo:abstract | En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers. Le nombre d'états d'un automate inambigu peut être exponentiellement plus petit qu'un automate déterministe équivalent. En contre-partie, certains problèmes sont plus difficiles à résoudre pour les automates inambigus que pour les automates déterministes. Par exemple, partant d'un automate A, un automate A' reconnaissant le complément du langage accepté par A se construit en temps linéaire si A est déterministe, mais il a été démontré qu'il ne peut être calculé en temps polynomial si A est inambigu. La notion d'automate inambigu se généralise à d'autres modèles de machines ou de calcul. Un présentation générale a été donnée par Thomas Colcombet. (fr) |
| dbo:thumbnail | wiki-commons:Special:FilePath/AutomateNonDéterministe_à_n+1_états.jpg?width=300 |
| dbo:wikiPageExternalLink | http://im.saske.sk/~jiraskov/UFA/ufa.pdf%7Clangue=%7Cauteur1=%7Cdate=%7Cissn= http://old.automata.rwth-aachen.de/download/papers/loeding/IPL-IL12.pdf http://ac.els-cdn.com/S0890540112000090/1-s2.0-S0890540112000090-main.pdf%3F_tid=fbc8bd62-2d3d-11e6-b5c9-00000aab0f26&acdnat=1465365672_b3c53f97e1ad2b07bde6f7525860bbd0 http://old.automata.rwth-aachen.de/users/loeding/unambiguous-dlt13.pdf https://www.irif.fr/~colcombe/Publications/DCFS15-colcombet.pdf |
| dbo:wikiPageID | 10072822 (xsd:integer) |
| dbo:wikiPageLength | 20987 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 188079532 (xsd:integer) |
| dbo:wikiPageWikiLink | category-fr:Automates_finis_et_langages_réguliers dbpedia-fr:Alphabet dbpedia-fr:Automate_de_Büchi dbpedia-fr:Automate_fini_déterministe dbpedia-fr:Automate_fini_non_déterministe dbpedia-fr:Automate_pondéré dbpedia-fr:Automate_transposé category-fr:Théorie_des_automates dbpedia-fr:Complexité_en_espace dbpedia-fr:Fonction_de_Landau dbpedia-fr:Grammaire_formelle dbpedia-fr:Langage_formel dbpedia-fr:Langage_rationnel dbpedia-fr:Mot_(mathématiques) dbpedia-fr:P_(complexité) dbpedia-fr:Produit_cartésien dbpedia-fr:Rang_(algèbre_linéaire) dbpedia-fr:Théorie_des_automates dbpedia-fr:Transducteur_fini dbpedia-fr:Étoile_de_Kleene dbpedia-fr:Fichier:AutomateNonDéterministe_à_n+1_états.jpg dbpedia-fr:Fichier:Unambiguous_finite_autaton_for_(a b)*a(a b)^2.svg dbpedia-fr:Fichier:Unambiguous_finite_automaton.svg |
| prop-fr:année | 1972 (xsd:integer) 1981 (xsd:integer) 1983 (xsd:integer) 2011 (xsd:integer) 2012 (xsd:integer) 2013 (xsd:integer) 2015 (xsd:integer) 2016 (xsd:integer) |
| prop-fr:arxiv | 802.325400 (xsd:double) |
| prop-fr:auteur | Albert R. Meyer (fr) Alexander Okhotin (fr) André Arnold (fr) Christof Löding (fr) Dimitri Isaak (fr) Harry B. Hunt (fr) Larry J. Stockmeyer (fr) Richard E. Stearns (fr) |
| prop-fr:collection | Lecture Notes in Computer Science (fr) |
| prop-fr:doi | 10.100700 (xsd:double) 10.101600 (xsd:double) 10.110900 (xsd:double) 10.114200 (xsd:double) |
| prop-fr:id | MS (fr) StearnsHunt (fr) jj (fr) |
| prop-fr:journal | International Journal of Foundations of Computer Science (fr) Developments in Language Theory (fr) |
| prop-fr:libellé | Arnold (fr) Allauzen et al. (fr) Colcombet (fr) Isaak et Löding (fr) Jirásek et al. (fr) Löding (fr) Meyer et Stockmeyer (fr) Okhotin (fr) Stearns et Hunt (fr) |
| prop-fr:mois | mars (fr) septembre (fr) août (fr) octobre (fr) |
| prop-fr:nom | Allauzen (fr) Colcombet (fr) Jirásek (fr) Jirásková (fr) Mohri (fr) Rastogi (fr) Šebej (fr) |
| prop-fr:numéro | 1 (xsd:integer) 4 (xsd:integer) 14 (xsd:integer) |
| prop-fr:numéroDansCollection | 9118 (xsd:integer) 9840 (xsd:integer) |
| prop-fr:pages | 15 (xsd:integer) 29 (xsd:integer) 74 (xsd:integer) 125 (xsd:integer) 221 (xsd:integer) 578 (xsd:integer) 883 (xsd:integer) |
| prop-fr:passage | 3 (xsd:integer) 243 (xsd:integer) |
| prop-fr:prénom | Thomas (fr) Cyril (fr) Jozef (fr) Ashish (fr) Galina (fr) Juraj (fr) Mehryar (fr) |
| prop-fr:périodique | 13 (xsd:integer) 22 (xsd:integer) Theoretical Computer Science (fr) Information Processing Letters (fr) Information and Computation (fr) |
| prop-fr:titre | The equivalence problem for regular expressions with squaring requires exponential space (fr) On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata (fr) Efficient inclusion testing for simple classes of unambiguous \u03c9-automata (fr) Operations on unambiguous automata (fr) Rational ω-languages are non-ambiguous (fr) Unambiguity in Automata Theory (fr) Unambiguous Finite Automata (fr) Unambiguous finite automata over a unary alphabet (fr) General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers (fr) |
| prop-fr:titreOuvrage | Descriptional Complexity of Formal Systems (fr) Developments in Language Theory (fr) |
| prop-fr:url | http://im.saske.sk/~jiraskov/UFA/ufa.pdf%7Clangue=%7Cauteur1=%7Cdate=%7Cissn= http://ac.els-cdn.com/S0890540112000090/1-s2.0-S0890540112000090-main.pdf%3F_tid=fbc8bd62-2d3d-11e6-b5c9-00000aab0f26&acdnat=1465365672_b3c53f97e1ad2b07bde6f7525860bbd0 http://old.automata.rwth-aachen.de/users/loeding/unambiguous-dlt13.pdf https://www.irif.fr/~colcombe/Publications/DCFS15-colcombet.pdf |
| prop-fr:urlTexte | http://old.automata.rwth-aachen.de/download/papers/loeding/IPL-IL12.pdf |
| prop-fr:volume | 22 (xsd:integer) 26 (xsd:integer) 112 (xsd:integer) 212 (xsd:integer) |
| prop-fr:wikiPageUsesTemplate | dbpedia-fr:Modèle:' dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Article_détaillé dbpedia-fr:Modèle:Chapitre dbpedia-fr:Modèle:Citation_étrangère dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Boîte_déroulante/début dbpedia-fr:Modèle:Boîte_déroulante/fin dbpedia-fr:Modèle:Math dbpedia-fr:Modèle:Théorème dbpedia-fr:Modèle:Palette_Automates_finis_et_langages_réguliers |
| prop-fr:éditeur | Institute of Electrical & Electronics Engineers (fr) |
| dct:subject | category-fr:Automates_finis_et_langages_réguliers category-fr:Théorie_des_automates |
| rdfs:comment | En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais « unambiguous finite automaton », abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes langages formels, à savoir les langages réguliers. (fr) |
| rdfs:label | Automate fini inambigu (fr) |
| owl:sameAs | dbr:Unambiguous_finite_automaton wikidata:Q1306211 dbpedia-de:Eindeutiger_endlicher_Automat dbpedia-fa:ماشین_محدود_غیرمبهم http://g.co/kg/g/120ndpgm |
| prov:wasDerivedFrom | wikipedia-fr:Automate_fini_inambigu?oldid=188079532&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/AutomateNonDéterministe_à_n+1_états.jpg wiki-commons:Special:FilePath/Unambiguous_finite_autaton_for_(a b)*a(a b)^2.svg wiki-commons:Special:FilePath/Unambiguous_finite_automaton.svg |
| foaf:isPrimaryTopicOf | wikipedia-fr:Automate_fini_inambigu |
| is dbo:wikiPageWikiLink of | dbpedia-fr:Automate_fini_déterministe dbpedia-fr:Automate_fini_non_déterministe dbpedia-fr:Automate_à_pile_visible dbpedia-fr:Complexité_en_états dbpedia-fr:Langage_rationnel dbpedia-fr:Larry_J._Stockmeyer |
| is oa:hasTarget of | tag-fr:WdtFrResource |
| is foaf:primaryTopic of | wikipedia-fr:Automate_fini_inambigu |
