Advertisement
Published in:
2019 | OriginalPaper | Chapter
On the Size of Logical Automata
Author : Martin Raszyk
Published in: SOFSEM 2019: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The state complexity of simulating 1NFA by 2DFA is a long-standing open question, which is of particular interest also due to its connection to the DLOG vs. NLOG problem for Turing machines.
What makes proving lower bounds on the size of deterministic two-way automata particularly hard is the fact that one has to consider any automaton, and unlike the designer, one does not have any meaning of the states at hand. This motivates the notion of logical automata whose states are annotated by formulas representing the meaning of a state.
In the paper at hand, we first introduce the notion of logical automata and present a general approach to proving lower bounds on the number of states of logical automata. We then apply this approach to derive an exponential lower bound on the size of logical automata over formulas with a restricted set of atomic predicates. Finally, we complement the lower bound with an (also exponential) upper bound.