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...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Göös, M, Kiefer, S, Yuan, W
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022

Míreanna comhchosúla

Markov chains and unambiguous automata
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2023)

Markov chains and unambiguous Büchi automata
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2016)

Markov Chains and Unambiguous Büchi Automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2016)

On complementing unambiguous automata and graphs with many cliques and cocliques
de réir: Indzhev, E, et al.
Foilsithe / Cruthaithe: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2019)

Unambiguous and finitely ambiguous automata
de réir: Widdershoven, C
Foilsithe / Cruthaithe: (2022)

Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
de réir: Qiqi Yan
Foilsithe / Cruthaithe: (2008-03-01)

Algorithms and lower bounds in finite automata size complexity
de réir: Kapoutsis, Christos, 1974-
Foilsithe / Cruthaithe: (2007)

An improved lower bound for the complementation of Rabin automata
de réir: Cai, Yang, et al.
Foilsithe / Cruthaithe: (2010)

Lower bounds for quantum-inspired classical algorithms via communication complexity
de réir: Nikhil S. Mande, et al.
Foilsithe / Cruthaithe: (2025-01-01)

Bounded Languages Meet Cellular Automata with Sparse Communication
de réir: Martin Kutrib, et al.
Foilsithe / Cruthaithe: (2009-07-01)

The Taxon Hypothesis Paradigm—On the Unambiguous Detection and Communication of Taxa
de réir: Urmas Kõljalg, et al.
Foilsithe / Cruthaithe: (2020-11-01)

Bounded Parikh Automata
de réir: Michaël Cadilhac, et al.
Foilsithe / Cruthaithe: (2011-08-01)

On the Complexity of the Equivalence Problem for Probabilistic Automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2012)

An unambiguous synthesis of Jacareubin /
de réir: 238391 Jefferson, A, et al.
Foilsithe / Cruthaithe: (1966)

Probabilistic automata of bounded ambiguity
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2017)

Unambiguous ISAR Imaging Method for Complex Maneuvering Group Targets
de réir: Fengkai Liu, et al.
Foilsithe / Cruthaithe: (2022-05-01)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2013)

On the Complexity of Equivalence and Minimisation for Q-weighted Automata
de réir: Stefan Kiefer, et al.
Foilsithe / Cruthaithe: (2013-03-01)

An unambiguous cloudiness index for nonwovens
de réir: Michael Godehardt, et al.
Foilsithe / Cruthaithe: (2022-04-01)

Unambiguous phase spaces for subregions
de réir: Josh Kirklin
Foilsithe / Cruthaithe: (2019-03-01)

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

Image-binary automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2024)

Alternating Timed Automata over Bounded Time
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2010)

Alternating Timed Automata over Bounded Time
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2010)

On reachability for hybrid automata over bounded time
de réir: Brihaye, T, et al.
Foilsithe / Cruthaithe: (2011)

Freezing, Bounded-Change and Convergent Cellular Automata
de réir: Nicolas Ollinger, et al.
Foilsithe / Cruthaithe: (2022-01-01)

All about unambiguous polynomial closure
de réir: Thomas Place, et al.
Foilsithe / Cruthaithe: (2024-01-01)

Ultimate limits of approximate unambiguous discrimination
de réir: Quntao Zhuang
Foilsithe / Cruthaithe: (2020-11-01)

Learning of Structurally Unambiguous Probabilistic Grammars
de réir: Dana Fisman, et al.
Foilsithe / Cruthaithe: (2023-02-01)

Unambiguous State Discrimination with Intrinsic Coherence
de réir: Jin-Hua Zhang, et al.
Foilsithe / Cruthaithe: (2021-12-01)

Cooperative radar with signature method for unambiguity
de réir: S. Müller, et al.
Foilsithe / Cruthaithe: (2019-09-01)

Compute bound and i/o bound cellular automata simulations on FPGA logic
de réir: Murtaza, S., et al.
Foilsithe / Cruthaithe: (2013)

Proving safety with trace automata and bounded model checking
de réir: Kroening, D, et al.
Foilsithe / Cruthaithe: (2015)

Unambiguous range extension for pulse‐Doppler radar via Poisson disk sampling
de réir: Boyuan Dong, et al.
Foilsithe / Cruthaithe: (2021-01-01)

Unambiguous Acquisition and Tracking Technique for General BOC Signals
de réir: F. Shen, et al.
Foilsithe / Cruthaithe: (2015-09-01)

Minimisation of multiplicity tree automata
de réir: Worrell, J, et al.
Foilsithe / Cruthaithe: (2017)

Communications in cellular automata
de réir: Guillaume Theyssier, et al.
Foilsithe / Cruthaithe: (2009-06-01)

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
de réir: Yang, Lisa L.
Foilsithe / Cruthaithe: (2022)

Unambiguous quantum state elimination for qubit sequences
de réir: Jonathan Crickmore, et al.
Foilsithe / Cruthaithe: (2020-03-01)