BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//SECURITY & APPLIED LOGIC - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://sal.cs.unibuc.ro
X-WR-CALDESC:Events for SECURITY & APPLIED LOGIC
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Europe/Bucharest
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20200329T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20201025T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20210328T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20211031T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20220327T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20221030T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Bucharest:20210325T100000
DTEND;TZID=Europe/Bucharest:20210325T120000
DTSTAMP:20260423T080326
CREATED:20210322T160836Z
LAST-MODIFIED:20210323T090618Z
UID:697-1616666400-1616673600@sal.cs.unibuc.ro
SUMMARY:Regular matching problems for infinite trees
DESCRIPTION:Title: Regular matching problems for infinite trees \nSpeaker: Mircea Marin (West University of Timișoara) \n\nAbstract:  \nWe study the matching problem “∃σ:σ(L)⊆R?” where L and R are regular tree languages over finite ranked alphabets X and Σ respectively\, and σ is a substitution such that σ(x) is a set of trees in T(Σ∪H)∖H for all x∈X. Here\, H denotes a set of holes which are used to define a concatenation of trees. Conway studied this problem in the special case for languages of finite words in his classical textbook Regular algebra and finite machines and showed that if L and R are regular\, then the problem “∃σ:∀x∈X:σ(x)≠∅∧σ(L)⊆R?” is decidable. Moreover\, there are only finitely many maximal solutions\, which are regular and effectively computable. We extend Conway’s results when L and R are regular languages of finite and infinite trees\, and language substitution is applied inside-out. We show that if L⊆T(X) and R⊆T(Σ) are regular tree languages then the problem “∃σ∀x∈X:σ(x)≠∅∧σio(L)⊆R?” is decidable. Moreover\, there are only finitely many maximal solutions\, which are regular and effectively computable. The corresponding question for the outside-in extension σoi remains open\, even in the restricted setting of finite trees. Our main result is the decidability of “∃σ:σio(L)⊆R?” if R is regular and L belongs to a class of tree languages closed under intersection with regular sets. Such a special case pops up if L is context-free.\nThis is joint work with Carlos Camino\, Volker Diekert\, Besik Dundua and Géraud Sénizergues. \n\nReferences: \n[1] C. Camino\, V. Diekert\, B. Dundua\, M. Marin\, G. Sénizergues\, Regular matching problems for infinite trees. arXiv:2004.09926 [cs.FL]\, 2021.
URL:https://sal.cs.unibuc.ro/event/regular-matching-problems-for-infinite-trees/
CATEGORIES:Logic Seminar
END:VEVENT
END:VCALENDAR