Lower bounds for unambiguous automata via communication complexity

Lower bounds for unambiguous automata via communication complexity

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1. Complement: There is a language L recognised by an n-state UFA such that the complement language L requires NFAs with n Ω(log ˜ n) states. This...

Szczegółowa specyfikacja

Opis bibliograficzny
Główni autorzy:	Göös, M, Kiefer, S, Yuan, W
Format:	Conference item
Język:	English
Wydane:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022

Podobne zapisy

Markov chains and unambiguous automata
od: Baier, C, i wsp.
Wydane: (2023)

Markov chains and unambiguous Büchi automata
od: Baier, C, i wsp.
Wydane: (2016)

Markov Chains and Unambiguous Büchi Automata
od: Kiefer, S, i wsp.
Wydane: (2016)

On complementing unambiguous automata and graphs with many cliques and cocliques
od: Indzhev, E, i wsp.
Wydane: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
od: Kiefer, S, i wsp.
Wydane: (2019)

Unambiguous and finitely ambiguous automata
od: Widdershoven, C
Wydane: (2022)

Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
od: Qiqi Yan
Wydane: (2008-03-01)

Algorithms and lower bounds in finite automata size complexity
od: Kapoutsis, Christos, 1974-
Wydane: (2007)

An improved lower bound for the complementation of Rabin automata
od: Cai, Yang, i wsp.
Wydane: (2010)

Lower bounds for quantum-inspired classical algorithms via communication complexity
od: Nikhil S. Mande, i wsp.
Wydane: (2025-01-01)

Bounded Languages Meet Cellular Automata with Sparse Communication
od: Martin Kutrib, i wsp.
Wydane: (2009-07-01)

Bounded Parikh Automata
od: Michaël Cadilhac, i wsp.
Wydane: (2011-08-01)

The Taxon Hypothesis Paradigm—On the Unambiguous Detection and Communication of Taxa
od: Urmas Kõljalg, i wsp.
Wydane: (2020-11-01)

On the Complexity of the Equivalence Problem for Probabilistic Automata
od: Kiefer, S, i wsp.
Wydane: (2012)

Bounded-oscillation Pushdown Automata
od: Pierre Ganty, i wsp.
Wydane: (2016-09-01)

Probabilistic automata of bounded ambiguity
od: Fijalkow, N, i wsp.
Wydane: (2017)

An unambiguous synthesis of Jacareubin /
od: 238391 Jefferson, A, i wsp.
Wydane: (1966)

Realisability of Pomsets via Communicating Automata
od: Roberto Guanciale Dr, i wsp.
Wydane: (2018-10-01)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
od: Kiefer, S, i wsp.
Wydane: (2013)

Unambiguous ISAR Imaging Method for Complex Maneuvering Group Targets
od: Fengkai Liu, i wsp.
Wydane: (2022-05-01)

On the Complexity of Equivalence and Minimisation for Q-weighted Automata
od: Stefan Kiefer, i wsp.
Wydane: (2013-03-01)

An unambiguous cloudiness index for nonwovens
od: Michael Godehardt, i wsp.
Wydane: (2022-04-01)

Unambiguous phase spaces for subregions
od: Josh Kirklin
Wydane: (2019-03-01)

On M-unambiguity of Parikh matrices
od: Wen Chean Teh
Wydane: (2020-06-01)

Image-binary automata
od: Kiefer, S, i wsp.
Wydane: (2024)

Alternating Timed Automata over Bounded Time
od: Jenkins, M, i wsp.
Wydane: (2010)

Alternating Timed Automata over Bounded Time
od: Jenkins, M, i wsp.
Wydane: (2010)

An Unambiguous Tracking Technique for Cosine-Phased BOC Signals with Low Complexity
od: T. Li, i wsp.
Wydane: (2018-12-01)

Design of Unambiguous Combined Tracking Loop for GNSS Complex Subcarrier Signal
Wydane: (2018-02-01)

On reachability for hybrid automata over bounded time
od: Brihaye, T, i wsp.
Wydane: (2011)

Freezing, Bounded-Change and Convergent Cellular Automata
od: Nicolas Ollinger, i wsp.
Wydane: (2022-01-01)

Compute bound and i/o bound cellular automata simulations on FPGA logic
od: Murtaza, S., i wsp.
Wydane: (2013)

All about unambiguous polynomial closure
od: Thomas Place, i wsp.
Wydane: (2024-01-01)

Ultimate limits of approximate unambiguous discrimination
od: Quntao Zhuang
Wydane: (2020-11-01)

Learning of Structurally Unambiguous Probabilistic Grammars
od: Dana Fisman, i wsp.
Wydane: (2023-02-01)

Unambiguous State Discrimination with Intrinsic Coherence
od: Jin-Hua Zhang, i wsp.
Wydane: (2021-12-01)

Cooperative radar with signature method for unambiguity
od: S. Müller, i wsp.
Wydane: (2019-09-01)

Proving safety with trace automata and bounded model checking
od: Kroening, D, i wsp.
Wydane: (2015)

Unambiguous range extension for pulse‐Doppler radar via Poisson disk sampling
od: Boyuan Dong, i wsp.
Wydane: (2021-01-01)

Communications in cellular automata
od: Guillaume Theyssier, i wsp.
Wydane: (2009-06-01)