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

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Göös, M, Kiefer, S, Yuan, W
Định dạng:	Conference item
Ngôn ngữ:	English
Được phát hành:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022

Những quyển sách tương tự

Markov chains and unambiguous automata
Bằng: Baier, C, et al.
Được phát hành: (2023)

Markov chains and unambiguous Büchi automata
Bằng: Baier, C, et al.
Được phát hành: (2016)

Markov Chains and Unambiguous Büchi Automata
Bằng: Kiefer, S, et al.
Được phát hành: (2016)

On complementing unambiguous automata and graphs with many cliques and cocliques
Bằng: Indzhev, E, et al.
Được phát hành: (2022)

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
Bằng: Kiefer, S, et al.
Được phát hành: (2019)

Unambiguous and finitely ambiguous automata
Bằng: Widdershoven, C
Được phát hành: (2022)

Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
Bằng: Qiqi Yan
Được phát hành: (2008-03-01)

Algorithms and lower bounds in finite automata size complexity
Bằng: Kapoutsis, Christos, 1974-
Được phát hành: (2007)

An improved lower bound for the complementation of Rabin automata
Bằng: Cai, Yang, et al.
Được phát hành: (2010)

Lower bounds for quantum-inspired classical algorithms via communication complexity
Bằng: Nikhil S. Mande, et al.
Được phát hành: (2025-01-01)

Bounded Languages Meet Cellular Automata with Sparse Communication
Bằng: Martin Kutrib, et al.
Được phát hành: (2009-07-01)

Bounded Parikh Automata
Bằng: Michaël Cadilhac, et al.
Được phát hành: (2011-08-01)

The Taxon Hypothesis Paradigm—On the Unambiguous Detection and Communication of Taxa
Bằng: Urmas Kõljalg, et al.
Được phát hành: (2020-11-01)

On the Complexity of the Equivalence Problem for Probabilistic Automata
Bằng: Kiefer, S, et al.
Được phát hành: (2012)

Bounded-oscillation Pushdown Automata
Bằng: Pierre Ganty, et al.
Được phát hành: (2016-09-01)

Probabilistic automata of bounded ambiguity
Bằng: Fijalkow, N, et al.
Được phát hành: (2017)

An unambiguous synthesis of Jacareubin /
Bằng: 238391 Jefferson, A, et al.
Được phát hành: (1966)

Realisability of Pomsets via Communicating Automata
Bằng: Roberto Guanciale Dr, et al.
Được phát hành: (2018-10-01)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
Bằng: Kiefer, S, et al.
Được phát hành: (2013)

Unambiguous ISAR Imaging Method for Complex Maneuvering Group Targets
Bằng: Fengkai Liu, et al.
Được phát hành: (2022-05-01)

On the Complexity of Equivalence and Minimisation for Q-weighted Automata
Bằng: Stefan Kiefer, et al.
Được phát hành: (2013-03-01)

An unambiguous cloudiness index for nonwovens
Bằng: Michael Godehardt, et al.
Được phát hành: (2022-04-01)

Unambiguous phase spaces for subregions
Bằng: Josh Kirklin
Được phát hành: (2019-03-01)

On M-unambiguity of Parikh matrices
Bằng: Wen Chean Teh
Được phát hành: (2020-06-01)

Image-binary automata
Bằng: Kiefer, S, et al.
Được phát hành: (2024)

Alternating Timed Automata over Bounded Time
Bằng: Jenkins, M, et al.
Được phát hành: (2010)

Alternating Timed Automata over Bounded Time
Bằng: Jenkins, M, et al.
Được phát hành: (2010)

An Unambiguous Tracking Technique for Cosine-Phased BOC Signals with Low Complexity
Bằng: T. Li, et al.
Được phát hành: (2018-12-01)

Design of Unambiguous Combined Tracking Loop for GNSS Complex Subcarrier Signal
Được phát hành: (2018-02-01)

On reachability for hybrid automata over bounded time
Bằng: Brihaye, T, et al.
Được phát hành: (2011)

Freezing, Bounded-Change and Convergent Cellular Automata
Bằng: Nicolas Ollinger, et al.
Được phát hành: (2022-01-01)

Compute bound and i/o bound cellular automata simulations on FPGA logic
Bằng: Murtaza, S., et al.
Được phát hành: (2013)

All about unambiguous polynomial closure
Bằng: Thomas Place, et al.
Được phát hành: (2024-01-01)

Ultimate limits of approximate unambiguous discrimination
Bằng: Quntao Zhuang
Được phát hành: (2020-11-01)

Learning of Structurally Unambiguous Probabilistic Grammars
Bằng: Dana Fisman, et al.
Được phát hành: (2023-02-01)

Unambiguous State Discrimination with Intrinsic Coherence
Bằng: Jin-Hua Zhang, et al.
Được phát hành: (2021-12-01)

Cooperative radar with signature method for unambiguity
Bằng: S. Müller, et al.
Được phát hành: (2019-09-01)

Proving safety with trace automata and bounded model checking
Bằng: Kroening, D, et al.
Được phát hành: (2015)

Unambiguous range extension for pulse‐Doppler radar via Poisson disk sampling
Bằng: Boyuan Dong, et al.
Được phát hành: (2021-01-01)

Communications in cellular automata
Bằng: Guillaume Theyssier, et al.
Được phát hành: (2009-06-01)