| 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)
- 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20987 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| 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
| |
| 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)
- 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)
- 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)
- MS (fr)
- StearnsHunt (fr)
- jj (fr)
|
| prop-fr:journal
|
- International Journal of Foundations of Computer Science (fr)
- Developments in Language Theory (fr)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- Descriptional Complexity of Formal Systems (fr)
- Developments in Language Theory (fr)
|
| prop-fr:url
| |
| prop-fr:urlTexte
| |
| prop-fr:volume
|
- 22 (xsd:integer)
- 26 (xsd:integer)
- 112 (xsd:integer)
- 212 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Institute of Electrical & Electronics Engineers (fr)
- Institute of Electrical & Electronics Engineers (fr)
|
| dct:subject
| |
| 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)
- 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)
- Automate fini inambigu (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
*a(a+b)%5E2.svg){kind=link}
*a(a+b)%5E2.svg){kind=link}
