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

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Göös, M, Kiefer, S, Yuan, W
Fformat:	Conference item
Iaith:	English
Cyhoeddwyd:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022

Eitemau Tebyg

Markov chains and unambiguous automata
gan: Baier, C, et al.
Cyhoeddwyd: (2023)

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

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

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

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

Unambiguous and finitely ambiguous automata
gan: Widdershoven, C
Cyhoeddwyd: (2022)

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

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

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

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

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

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

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

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

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

Probabilistic automata of bounded ambiguity
gan: Fijalkow, N, et al.
Cyhoeddwyd: (2017)

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

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

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

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

Unambiguous phase spaces for subregions
gan: Josh Kirklin
Cyhoeddwyd: (2019-03-01)

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

Image-binary automata
gan: Kiefer, S, et al.
Cyhoeddwyd: (2024)

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

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

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

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

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

Ultimate limits of approximate unambiguous discrimination
gan: Quntao Zhuang
Cyhoeddwyd: (2020-11-01)

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

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

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

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

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

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

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

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

Minimisation of multiplicity tree automata
gan: Worrell, J, et al.
Cyhoeddwyd: (2017)

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

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