Problème d'accessibilité

Le problème d'accessibilité consiste à atteindre une situation finale depuis une situation initiale.

Le problème d'accessibilité (aussi appelé le problème d'atteignabilité)[1] est, en informatique, le problème algorithmique qui consiste à déterminer si, dans un système, une situation finale est accessible/atteignable depuis une situation initiale. Le problème d'accessibilité a été étudié dans les automates finis, les automates cellulaires, les automates temporisés, les systèmes infinis, etc.

Graphe fini explicite

Le problème d'accessibilité dans un graphe orienté décrit explicitement est NL-complet. Reingold, dans un article de 2008, a démontré que le problème d'accessibilité pour un graphe non-orienté est dans LOGSPACE[2].

En vérification de modèles, l'accessibilité correspond à une propriété de vivacité.

Graphe fini implicite

En planification, plus précisément en planification classique, on s'intéresse à savoir si on peut atteindre un état depuis un état initial à partir d'une description des actions. La description des actions définissent un graphe des états implicites, qui est de taille exponentielle en la taille de la description.

En vérification de modèles symbolique, le modèle (le graphe sous-jacent) est décrit à l'aide d'une représentation symbolique comme des diagrammes de décision binaire.

Réseaux de Petri

Le problème d'accessibilité dans un réseau de Petri est décidable[3]. Dès 1976, on savait que ce problème était EXPSPACE-dur[4]. Il y a des résultats sur la façon d'implémenter ce problème en pratique[5]. En 2018, le problème a été démontré comme non-élémentaire[6].

Notes et références

  1. ↑ (en) RP Organization Committee, « (RP'17) 11th International Workshop on Reachability Problems 2017 », sur rp17.cs.rhul.ac.uk (consulté le )
  2. ↑ Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ , p. 1–24 (lire en ligne)
  3. ↑ (en) Ernst W. Mayr, « An algorithm for the general Petri net reachability problem », STOC '81 Proceedings of the thirteenth annual ACM symposium on Theory of computing, Association for Computing Machinery,‎ , p. 238–246 (DOI 10.1145/800076.802477, lire en ligne, consulté le )
  4. ↑ R. Lipton, « The Reachability Problem Requires Exponential Space », Technical Report 62,‎ (lire en ligne)
  5. ↑ P. Küngas « Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies » (July 26–29, 2005) (lire en ligne)
    —Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation—SARA 2005
  6. ↑ (en) Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux et Filip Mazowiecki, « The Reachability Problem for Petri Nets is Not Elementary (Extended Abstract) », .

Read other articles:

Kepang kait

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Kepang kait – berita · surat kabar · buku · cendekiawan · JSTOR (Desember 2021) Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dar...

 

Région naturelle de France

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (mai 2016). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » En pratique : Quelles sources sont attendues ? Commen...

 

واشينغتونفيل (نيويورك)

واشينغتونفيل     الإحداثيات 41°26′00″N 74°10′00″W / 41.4333°N 74.1667°W / 41.4333; -74.1667   [1] تاريخ التأسيس 1731  تقسيم إداري  البلد الولايات المتحدة[2][3]  التقسيم الأعلى مقاطعة أورانج  خصائص جغرافية  المساحة 6.609124 كيلومتر مربع6.609121 كيلومتر مربع (1 أبر...

Bugasong, Antique

Peta yang menunjukkan letak Bugasong Bugasong adalah munisipalitas di provinsi Antique, Filipina. Pada tahun 2000, munisipalitas ini memiliki populasi sebesar 28.294 jiwa atau 5.768 rumah tangga. Pembagian wilayah Secara politis Bugasong terbagi atas 27 barangay, yaitu: Anilawan Arangote Bagtason Camangahan Cubay North Cubay South Guija Igbalangao Igsoro Ilaures Jinalinan Lacayon Maray Paliwan Pangalcagan Centro Ilawod (Pob.) Centro Ilaya (Pob.) Centro Pojo (Pob.) Sabang East Sabang West Tagu...

 

John J. McRae

American politician (1815–1868) For those of a similar name, see John McRae (disambiguation). John J. McRaeMember of the U.S. House of Representatives from Mississippi's 5th districtIn officeDecember 7, 1858 – January 12, 1861Preceded byJohn A. QuitmanSucceeded byLegrand W. Perce21st Governor of MississippiIn officeJanuary 10, 1854 – November 16, 1857Preceded byJohn J. PettusSucceeded byWilliam McWillieUnited States Senatorfrom MississippiIn officeDecember 1, 1851&...

 

Killshot (song)

2018 diss track by Eminem This article is about the Eminem song. For the Ben Frost song, see By the Throat (Ben Frost album). KillshotSingle by EminemReleasedSeptember 14, 2018RecordedSeptember 2018GenreHip hophardcore hip hoptrapLength4:14LabelShadyAftermathInterscopeSongwriter(s)Marshall MathersProducer(s)IllaDaProducerEminem singles chronology Fall (2018) Killshot (2018) Venom (2018) Killshot is a diss track by American rapper Eminem and produced by IllaDaProducer.[1] The song ...

Bhagat Singh

Halaman ini berisi artikel tentang revolusioner. Untuk imigran awal di AS, lihat Bhagat Singh Thind. Bhagat SinghBhagat Singh tampil pada 1929 setelah memotong rambutnyaLahir(1907-09-28)28 September 1907[a]Jaranwala Tehsil, Punjab, India BritaniaMeninggal23 Maret 1931(1931-03-23) (umur 23)Lahore, Punjab, India BritaniaOrganisasiNaujawan Bharat Sabha,Partai Kirti Kisan,Asosiasi Republikan Sosialis HindustanGerakan politikgerakan kemerdekaan India Bhagat Singh (IPA: [pə̀ɡə...

 

Trinity Christian Academy (Addison, Texas)

Private Christian school in Addison, Texas, United States The neutrality of this article is disputed. Relevant discussion may be found on the talk page. Please do not remove this message until conditions to do so are met. (May 2023) (Learn how and when to remove this template message) Trinity Christian AcademyAddress17001 Addison Rd.Addison, Texas 75001United StatesCoordinates32°58′56″N 96°50′16″W / 32.9821°N 96.8377°W / 32.9821; -96.8377InformationSchool t...

 

Corrales, Boyacá

Municipality and town in Boyacá Department, ColombiaCorrales, BoyacáMunicipality and town FlagLocation of the municipality and town of Corrales, Boyacá in the Boyacá Department of Colombia.Coordinates: 50°N 51°W / 50°N 51°W / 50; -51Country ColombiaDepartmentBoyacá DepartmentProvinceTundama ProvinceGovernment • MayorPedro Antonio López Prieto (2020-2023)Population • Total2,481Time zoneUTC-5 (Colombia Standard Time)Websitehttp://co...

Peder Ås

Fictional character The main building of the University of Oslo Faculty of Law Peder Ås, previously Peder Aas, is a fictional character and placeholder name used as an example in legal studies in Norway. The character is traditionally associated with the University of Oslo Faculty of Law, where it has occurred on every candidate of law exam since 1897, except in 1917. It continues to be used at all law schools in Norway. He has also been used in advertisements and plays. In the early years h...

 

Red wolf

Canid native to the southeastern United States This article is about the wild canine. For other uses, see Red wolf (disambiguation). Red wolfTemporal range: Holocene 10,000 years ago – present[1] A red wolf showing typical coloration Conservation status Critically Endangered  (IUCN 3.1)[2] Endangered (ESA)[3][4] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Mammalia Order: Carnivora Family: Canidae Genus: Cani...

 

Bawang Merah Bawang Putih

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Bawang Merah Bawang Putih – berita · surat kabar · buku · cendekiawan · JSTOR Untuk kegunaan lain, lihat Bawang Merah Bawang Putih (disambiguasi). Ilustrasi Bawang Merah Bawang Putih Bawang putih dan baw...

Nizam al-Mulk

Seljuk Abbasid Persian scholar, warrior, politician, and vizier (1018–1092) Not to be confused with Nizam-ul-Mulk, Asaf Jah I, founder of the Asaf Jahi dynasty. Nizam al-MulkVizier of the Seljuk EmpireIn office29 November 1064 – 14 October 1092MonarchAlp Arslan, Malik Shah IPreceded byAl-KunduriSucceeded byTaj al-Mulk Abu'l Ghana'im Personal detailsBornApril 10, 1018Tus, Ghaznavid EmpireDiedOctober 14, 1092 (aged 74)Nahavand, Seljuk EmpireSpouseUnnamed Bagrationi princess[1&#...

 

Reg Ellis (Australian sportsman)

For Reg Ellis (cricketer born 1917), see Reg Ellis (cricketer, born 1917). Australian rules footballer Reg Ellis Personal informationFull name Reginald Newnham EllisDate of birth (1891-02-22)22 February 1891Place of birth Randwick, New South WalesDate of death 26 May 1959(1959-05-26) (aged 68)Place of death Cheltenham, VictoriaOriginal team(s) Y.M.C.A. (Sydney)[1]Height 179 cm (5 ft 10 in)Weight 78 kg (172 lb)Position(s) DefenderPlaying career1Years ...

 

Trenton tomato pie

Type of Italian tomato pie For similarly named dishes, see Tomato pie.Trenton tomato pieSausage and mushroom Trenton tomato pieAlternative namesNew Jersey tomato pieTypePizzaPlace of originUnited StatesRegion or stateTrenton, New JerseyMain ingredientsPizza dough, tomato sauce, cheesePart of a series onPizza Main articles History of pizza Pizza delivery List of pizza varieties by country Pizza varieties Al taglio Altoona-style Beach California-style Capricciosa Chicago-style Chocolate Colorad...

Komitas Avenue

Street in Yerevan, Armenia Komitas AvenueKomitas Avenue at Arabkir districtNative nameԿոմիտասի պողոտա (Armenian)Length3 km (1.9 mi)LocationArabkir District, Yerevan, ArmeniaConstructionInauguration1938 Komitas Avenue (Armenian: Կոմիտասի պողոտա) is a 3 km-long avenue in the Armenian capital of Yerevan. Named after the prominent Armenian composer Komitas, the avenue is the arterial road of the Arabkir district. The avenue which was opened in 1938, star...

 

Ice-type model

In statistical mechanics, the ice-type models or six-vertex models are a family of vertex models for crystal lattices with hydrogen bonds. The first such model was introduced by Linus Pauling in 1935 to account for the residual entropy of water ice.[1] Variants have been proposed as models of certain ferroelectric[2] and antiferroelectric[3] crystals. In 1967, Elliott H. Lieb found the exact solution to a two-dimensional ice model known as square ice.[4] The ex...

 

Touat

Localisation de la région du Touat en Algérie. Le Touat[1] est une région de l'ouest du Sahara algérien, située au sud-ouest du Grand Erg occidental, dans la wilaya d'Adrar. Touat signifie en langue berbère « localité habitée »[réf. nécessaire]. La composition de la population du Touat est diverse. On y retrouve des Subsahariens, des Berbères, des Haratines, des Arabes. La région a été peuplée par une communauté juive dans l'Antiquité et au Moyen Âg...

Grup B Piala Dunia Wanita FIFA 2019

Grup B Piala Dunia Wanita FIFA 2019 merupakan salah satu dari enam grup Piala Dunia Wanita FIFA 2019 yang terdiri dari Afrika Selatan, Jerman, Spanyol, dan Tiongkok; dengan pertandingan yang berlangsung dari tanggal 8 hingga 17 Juni 2019.[1][2] Dua tim teratas, yakni Jerman dan Spanyol, serta tim peringkat ketiga, Tiongkok (sebagai salah satu dari empat tim peringkat ketiga terbaik), lolos ke babak 16 besar.[3] Tim peserta Posisi dalam pengundian Tim Pot Konfederasi Ja...

 

Sam Huff

American football player (1934–2021) For the baseball player, see Sam Huff (baseball). American football player Sam HuffHuff in college with West Virginia in 1955No. 70Position:LinebackerPersonal informationBorn:(1934-10-04)October 4, 1934Edna, West Virginia, U.S.Died:November 13, 2021(2021-11-13) (aged 87)Winchester, Virginia, U.S.Height:6 ft 1 in (1.85 m)Weight:230 lb (104 kg)Career informationHigh school:Farmington(Farmington, West Virginia)College:West Virg...