Campus Event Calendar
Event Entry
New for: D1
What and Who
Fine-Grained Complexity of Ambiguity Problems on Automata
Anita Dürr
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 29 April 2025
13:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
Two fundamental classes of finite automata are deterministic and nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word: unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It is known that deciding whether a given NFA is unambiguous and whether it is polynomially ambiguous is possible in quadratic time, and deciding finite ambiguity is possible in cubic time. We provide matching lower bounds showing these running times to be optimal, assuming popular fine-grained complexity hypotheses.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
649 2184 1396
passcode not visible
logged in users only
Nidhi Rathi, 04/29/2025 12:18
Nidhi Rathi, 04/28/2025 13:54
Nidhi Rathi, 03/24/2025 11:32 -- Created document.
Nidhi Rathi, 04/28/2025 13:54
Nidhi Rathi, 03/24/2025 11:32 -- Created document.