Thread automaton

In automata theory, the thread automaton (plural: automata) is an extended type of finite-state automata that recognizes a mildly context-sensitive language class above the tree-adjoining languages.[1]

Formal definition

A thread automaton consists of

  • a set N of states,[note 1]
  • a set Σ of terminal symbols,
  • a start state AS ∈ N,
  • a final state AF ∈ N,
  • a set U of path components,
  • a partial function δ: N → U⊥, where U⊥ = U ∪ {⊥} for ⊥ ∉ U,
  • a finite set Θ of transitions.

A path u1...un ∈ U* is a string of path components ui ∈ U; n may be 0, with the empty path denoted by ε. A thread has the form u1...un:A, where u1...un ∈ U* is a path, and A ∈ N is a state. A thread store S is a finite set of threads, viewed as a partial function from U* to N, such that dom(S) is closed by prefix.

A thread automaton configuration is a triple ‹l,p,S›, where l denotes the current position in the input string, p is the active thread, and S is a thread store containing p. The initial configuration is ‹0,ε,{ε:AS}›. The final configuration is ‹n,u,{ε:AS,u:AF}›, where n is the length of the input string and u abbreviates δ(AS). A transition in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:

  • SWAP B →a C:   consumes the input symbol a, and changes the state of the active thread:
changes the configuration from   ‹l,p,S∪{p:B}›   to   ‹l+1,p,S∪{p:C}›
  • SWAP B →ε C:   similar, but consumes no input:
changes   ‹l,p,S∪{p:B}›   to   ‹l,p,S∪{p:C}›
  • PUSH C:   creates a new subthread, and suspends its parent thread:
changes   ‹l,p,S∪{p:B}›   to   ‹l,pu,S∪{p:B,pu:C}›   where u=δ(B) and pu∉dom(S)
  • POP [B]C:   ends the active thread, returning control to its parent:
changes   ‹l,pu,S∪{p:B,pu:C}›   to   ‹l,p,S∪{p:C}›   where δ(C)=⊥ and pu∉dom(S)
  • SPUSH [C] D:   resumes a suspended subthread of the active thread:
changes   ‹l,p,S∪{p:B,pu:C}›   to   ‹l,pu,S∪{p:B,pu:D}›   where u=δ(B)
  • SPOP [B] D:   resumes the parent of the active thread:
changes   ‹l,pu,S∪{p:B,pu:C}›   to   ‹l,p,S∪{p:D,pu:C}›   where δ(C)=⊥

One may prove that δ(B)=u for POP and SPOP transitions, and δ(C)=⊥ for SPUSH transitions.[2]

An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration.

Notes

  1. ^ called non-terminal symbols by Villemonte (2002), p.1r

References

  1. ^ Villemonte de la Clergerie, Éric (2002). "Parsing mildly context-sensitive languages with thread automata". Proceedings of the 19th international conference on Computational linguistics -. Vol. 1. pp. 1–7. doi:10.3115/1072228.1072256. Retrieved 2016-10-15.
  2. ^ Villemonte (2002), p.1r-2r

Read other articles:

BL 7.2-inch howitzer

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. BL 7.2 inci howitzer Mks I-V dan Mk 6, adalah serangkaian artileri berat yang digunakan oleh Angkatan Darat Inggris selama Perang Dunia II. Pada 1940 Angkatan Darat Inggris menyimpulkan bahwa satu-satunya artileri berat yang tersedia, howitzer BL 8-inc...

 

Dicționar enciclopedic român

Dicționar enciclopedic român adalah sebuah ensiklopedia dalam bahasa Rumania yang diterbitkan oleh Editura Politica antara tahun 1962 dan 1966. Daftar pustaka Academia Republicii Popular Române, Dicționar enciclopedic român, Editura Politică, București, 1962-1966 Artikel bertopik ensiklopedia ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

 

Холокост на Украине

Часть серии статей о Холокосте Идеология и политика Расовая гигиена · Расовый антисемитизм · Нацистская расовая политика · Нюрнбергские расовые законы Шоа Лагеря смерти Белжец · Дахау · Майданек · Малый Тростенец · Маутхаузен ·&...

لانكستر (إنجلترا)

  لمعانٍ أخرى، طالع لانكستر (توضيح).   لانكستر (إنجلترا) (بالإنجليزية: Lancaster)‏    لانكستر (إنجلترا) تقسيم إداري البلد المملكة المتحدة  [1][2] خصائص جغرافية إحداثيات 54°02′56″N 2°48′05″W / 54.048888888889°N 2.8013888888889°W / 54.048888888889; -2.8013888888889   الارتفاع 9 متر&#...

 

1995 World Championships in Athletics – Men's 100 metres

Men's 100 metres at the 1995 World ChampionshipsVenueUllevi StadiumDates5 August (heats and quarter-finals)6 August (semi-finals and final)Competitors91Winning time9.97Medalists  Donovan Bailey   Canada Bruny Surin   Canada Ato Boldon   Trinidad and Tobago← 19931997 → Events at the1995 World ChampionshipsTrack events100 mmenwomen200 mmenwomen400 mmenwomen800 mmenwomen1500 mmenwomen5000 mmenwomen10,000 mmenwomen100 m...

 

Results of the 2019 New South Wales state election (Legislative Council)

Legislative Council election for New South Wales, Australia in March 2019 2019 New South Wales state election (Legislative Council) ← 2015 26 March 2019 2023 → 21 of the 42 seats on the Legislative Council21 seats needed for a majority   First party Second party Third party   L/NP Leader Don Harwin Adam Searle None Party Coalition Labor Greens Seats before 19 12 3 Seats won 8 7 2 Seats after 17 14 3 Seat change 3 2 Popular vote 1,549,75...

Supercoppa del Brasile 1991

Supercoppa del Brasile 1991Supercopa do Brasil 1991 Competizione Supercopa do Brasil Sport Calcio Edizione 2ª Organizzatore CBF Date 27 gennaio 1991 Luogo  Brasile Risultati Vincitore Corinthians(1º titolo) Secondo Flamengo Statistiche Incontri disputati 1 Gol segnati 1 (1 per incontro) Cronologia della competizione 1990 2020 Manuale La Supercoppa del Brasile 1991 (ufficialmente in portoghese Supercopa do Brasil 1991) è stata la seconda e ultima edizione della Supercoppa del Bra...

 

Béthines

BéthinescomuneBéthines – Veduta LocalizzazioneStato Francia Regione Nuova Aquitania Dipartimento Vienne ArrondissementMontmorillon CantoneMontmorillon TerritorioCoordinate46°33′N 0°59′E / 46.55°N 0.983333°E46.55; 0.983333 (Béthines)Coordinate: 46°33′N 0°59′E / 46.55°N 0.983333°E46.55; 0.983333 (Béthines) Superficie36,07 km² Abitanti493[1] (2009) Densità13,67 ab./km² Altre informazioniCod. postale86310 Fuso...

 

Население Татарстана

Численность населения республики по данным Росстата составляет 4 003 016[1] чел. (2024). Татарстан занимает 8-е место по численности населения среди субъектов Российской Федерации[2]. Плотность населения — 59,00 чел./км² (2024). Городское население — 76,72[3] % (20...

Olivier Latry

French musician Olivier LatryOlivier Latry at the organ of Lille CathedralBorn(1962-02-22)22 February 1962Boulogne-sur-Mer, FranceEducationConservatoire national supérieur de musique et de danse de ParisConservatoire à rayonnement régional de Boulogne-BillancourtConservatoire à rayonnement régional de Saint-Maur-des-FossésOccupations Organist Improviser Composer Academic teacher Organizations Notre-Dame de Paris Conservatoire de Paris Notable workSalve ReginaTitleOrganiste titulaire de ...

 

Chef (South Park)

Fictional character from South Park Fictional character Jerome McElroySouth Park characterFirst appearanceCartman Gets an Anal Probe (1997)Last appearanceSouth Park: The Stick of Truth (2014)Created byTrey ParkerMatt StoneDesigned byTrey ParkerMatt StoneVoiced byIsaac HayesTrey Parker (singing, in The Succubus)Peter Serafinowicz (as Darth Chef)In-universe informationAliasesAbdul Mohammed Jabar Rauf Kareem Ali (in Chef Goes Nanners), Charlie (in Return to Sleepaway Camp)OccupationSchool cafete...

 

Abu Mansur al-Baghdadi

For other uses, see Baghdadi (disambiguation). Arab Shafi'i scholar, Heresiologist and mathematician Abū Manṣūr al-Baghdādī(أَبُو مَنْصُورالبغدادي)TitleImamPersonalBornc. 980Baghdad[1]Died1037 (429 AH)[1](aged c. 56–57)Isfayayin[1]ReligionIslamEraIslamic golden ageRegionKhorasanDenominationSunniJurisprudenceShafi'i[1]CreedAsh'ari[2][3]Main interest(s)Theology (Kalam), Islamic Jurisprudence, Principles of Islamic juri...

Jazz

Disambiguazione – Se stai cercando altri significati, vedi Jazz (disambigua). JazzOrigini stilisticheMusica afroamericanaRagtimeSpiritualGospelBluesFolkMusica classica Origini culturaliTra gli anni dieci e gli anni venti negli Stati Uniti meridionali Strumenti tipicipianoforte, sassofono, tromba, contrabbasso, basso elettrico, batteria, chitarra, voce, clarinetto, trombone, vibrafono, tuba, cornetta, flauto traverso Popolaritàdagli anni '20 agli anni '70, arrivando a suscitare interesse e...

 

517th Air Defense Group

517th Air Defense Group 37th Fighter-Interceptor Squadron North American F-86D Sabre at Ethan Allen AFBActive1945, 1953–1955Country United StatesBranch United States Air ForceRoleAir DefensePart ofAir Defense CommandMilitary unit The 517th Air Defense Group is a disbanded United States Air Force organization. Its last assignment was with the 4711th Air Defense Wing at Ethan Allen Air Force Base, Vermont. It was inactivated on 18 August 1955. The group was originally activate...

 

Championnat de France de rugby à XV de 2e division fédérale 2015-2016

Fédérale 2 2015-2016 Généralités Sport Rugby à XV Organisateur(s) FFR Date de septembre 2015 au juin 2016 Nations France Hiérarchie Hiérarchie 4e échelon Niveau supérieur Fédérale 1 2015-2016 Niveau inférieur Fédérale 3 2015-2016 Navigation Fédérale 2 2014-2015 Fédérale 2 2016-2017 modifier Cette page présente la saison 2015-2016 de Fédérale 2 dont les phases de poule débutent en septembre 2015 pour se terminer en avril 2016. Composition et classement des poules[1...

Horn clause

Type of logical formula In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form that gives it useful properties for use in logic programming, formal specification, universal algebra and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.[1] Definition A Horn clause is a disjunctive clause (a disjunction of literals) with at most one positive, i.e. unnegated, literal....

 

I compagni

I compagniBernard Blier, Renato Salvatori e Marcello Mastroianni in una scena del filmPaese di produzioneItalia, Francia, Jugoslavia Anno1963 Durata128 min Dati tecnicib/n Generedrammatico RegiaMario Monicelli SoggettoAge & Scarpelli, Mario Monicelli SceneggiaturaAge & Scarpelli, Mario Monicelli ProduttoreFranco Cristaldi Casa di produzioneLux Film, Vides Cinematografica (Roma), Méditerranée Cinéma Production (Parigi), Avala Film (Belgrado) Distribuzione in italianoParamoun...

 

Linda Manzer

Linda ManzerOCOccupationLuthierInstrumentGuitarYears active1970s–presentWebsitewww.manzer.comMusical artist Linda Jane Manzer OC (born July 2, 1952) is a Canadian master luthier renowned for her archtop, flat top, and harp guitars. Career Manzer was a folk singer in high school and played guitar. Her career began when she wanted a dulcimer, but she couldn't afford to buy one, so she built one from a kit. She attended two art colleges, where she studied painting. For the craft of making fla...

Hof (Saale)

Wappen Deutschlandkarte Basisdaten Koordinaten: 50° 19′ N, 11° 55′ O50.32194444444411.918888888889500Koordinaten: 50° 19′ N, 11° 55′ O Bundesland: Bayern Regierungsbezirk: Oberfranken Höhe: 500 m ü. NHN Fläche: 58,02 km2 Einwohner: 46.963 (31. Dez. 2023)[1] Bevölkerungsdichte: 809 Einwohner je km2 Postleitzahlen: 95028, 95030, 95032 Vorwahl: 09281 Kfz-Kennzeichen: HO Gemeindeschlüssel: 09 ...

 

The Company's in Love

1932 film The Company's in LoveLien Deyers and Gustav Fröhlich at the swimming bathsGermanDie verliebte Firma Directed byMax OphülsWritten byBruno GranichstaedtenErnst MarischkaFritz ZeckendorfStarringGustav FröhlichAnny AhlersLien DeyersCinematographyKarl PuthEdited byElse BaumMusic byBruno GranichstaedtenProductioncompanyDeutsches Lichtspiel-SyndikatDistributed byDeutsches Lichtspiel-SyndikatRelease date 22 February 1932 (1932-02-22) Running time73 minutesCountryGermanyLan...