2 citations · 8 across the 9 of their papers we have counts for
11 papers · 1 filter
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
Directed Regular and Context-Free Languages
Moses Ganardi, Irmak Saglam, Georg Zetzsche
We study the problem of deciding whether a given language is directed. A language is \emph{directed} if every pair of words in have a common (scattered) superword in . D…
Checking Refinement of Asynchronous Programs against Context-Free Specifications
Pascal Baumann, Moses Ganardi, Rupak Majumdar +2
In the language-theoretic approach to refinement verification, we check that the language of traces of an implementation all belong to the language of a specification. We consider…
Revisiting Membership Problems in Subclasses of Rational Relations
Pascal Bergsträßer, Moses Ganardi
We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The…
Unboundedness problems for machines with reversal-bounded counters
Pascal Baumann, Flavio D'Alessandro, Moses Ganardi +4
We consider a general class of decision problems concerning formal languages, called ``(one-dimensional) unboundedness predicates'', for automata that feature reversal-bounded coun…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For…