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

Descripció completa

Dades bibliogràfiques
Autors principals:	Göös, M, Kiefer, S, Yuan, W
Format:	Conference item
Idioma:	English
Publicat:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022

Ítems similars

Markov chains and unambiguous automata
per: Baier, C, et al.
Publicat: (2023)

Markov chains and unambiguous Büchi automata
per: Baier, C, et al.
Publicat: (2016)

Markov Chains and Unambiguous Büchi Automata
per: Kiefer, S, et al.
Publicat: (2016)

On complementing unambiguous automata and graphs with many cliques and cocliques
per: Indzhev, E, et al.
Publicat: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
per: Kiefer, S, et al.
Publicat: (2019)

Unambiguous and finitely ambiguous automata
per: Widdershoven, C
Publicat: (2022)

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

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

An improved lower bound for the complementation of Rabin automata
per: Cai, Yang, et al.
Publicat: (2010)

Lower bounds for quantum-inspired classical algorithms via communication complexity
per: Nikhil S. Mande, et al.
Publicat: (2025-01-01)

Bounded Languages Meet Cellular Automata with Sparse Communication
per: Martin Kutrib, et al.
Publicat: (2009-07-01)

The Taxon Hypothesis Paradigm—On the Unambiguous Detection and Communication of Taxa
per: Urmas Kõljalg, et al.
Publicat: (2020-11-01)

Bounded Parikh Automata
per: Michaël Cadilhac, et al.
Publicat: (2011-08-01)

An unambiguous synthesis of Jacareubin /
per: 238391 Jefferson, A, et al.
Publicat: (1966)

On the Complexity of the Equivalence Problem for Probabilistic Automata
per: Kiefer, S, et al.
Publicat: (2012)

Probabilistic automata of bounded ambiguity
per: Fijalkow, N, et al.
Publicat: (2017)

Unambiguous ISAR Imaging Method for Complex Maneuvering Group Targets
per: Fengkai Liu, et al.
Publicat: (2022-05-01)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
per: Kiefer, S, et al.
Publicat: (2013)

On the Complexity of Equivalence and Minimisation for Q-weighted Automata
per: Stefan Kiefer, et al.
Publicat: (2013-03-01)

An unambiguous cloudiness index for nonwovens
per: Michael Godehardt, et al.
Publicat: (2022-04-01)

Unambiguous phase spaces for subregions
per: Josh Kirklin
Publicat: (2019-03-01)

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

Image-binary automata
per: Kiefer, S, et al.
Publicat: (2024)

Alternating Timed Automata over Bounded Time
per: Jenkins, M, et al.
Publicat: (2010)

Alternating Timed Automata over Bounded Time
per: Jenkins, M, et al.
Publicat: (2010)

On reachability for hybrid automata over bounded time
per: Brihaye, T, et al.
Publicat: (2011)

Freezing, Bounded-Change and Convergent Cellular Automata
per: Nicolas Ollinger, et al.
Publicat: (2022-01-01)

All about unambiguous polynomial closure
per: Thomas Place, et al.
Publicat: (2024-01-01)

Ultimate limits of approximate unambiguous discrimination
per: Quntao Zhuang
Publicat: (2020-11-01)

Learning of Structurally Unambiguous Probabilistic Grammars
per: Dana Fisman, et al.
Publicat: (2023-02-01)

Unambiguous State Discrimination with Intrinsic Coherence
per: Jin-Hua Zhang, et al.
Publicat: (2021-12-01)

Cooperative radar with signature method for unambiguity
per: S. Müller, et al.
Publicat: (2019-09-01)

Compute bound and i/o bound cellular automata simulations on FPGA logic
per: Murtaza, S., et al.
Publicat: (2013)

Unambiguous range extension for pulse‐Doppler radar via Poisson disk sampling
per: Boyuan Dong, et al.
Publicat: (2021-01-01)

Proving safety with trace automata and bounded model checking
per: Kroening, D, et al.
Publicat: (2015)

Unambiguous Acquisition and Tracking Technique for General BOC Signals
per: F. Shen, et al.
Publicat: (2015-09-01)

Communications in cellular automata
per: Guillaume Theyssier, et al.
Publicat: (2009-06-01)

Minimisation of multiplicity tree automata
per: Worrell, J, et al.
Publicat: (2017)

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
per: Yang, Lisa L.
Publicat: (2022)

Unambiguous quantum state elimination for qubit sequences
per: Jonathan Crickmore, et al.
Publicat: (2020-03-01)