[HTML][HTML] Alternation in two-way finite automata
C Kapoutsis, M Zakzok - Theoretical Computer Science, 2021 - Elsevier
The study of alternation in two-way finite automata (2 fa s) has been quite non-systematic.
Since the 1970's, various authors with a variety of motivations have studied 2 fa s with …
Since the 1970's, various authors with a variety of motivations have studied 2 fa s with …
Simplest Non-Regular Deterministic Context-Free Language
P Jancar, J Sima - arXiv preprint arXiv:2102.10416, 2021 - arxiv.org
We introduce a new notion of C-simple problems for a class C of decision problems (ie
languages), wrt a particular reduction. A problem is C-simple if it can be reduced to each …
languages), wrt a particular reduction. A problem is C-simple if it can be reduced to each …
Limited Existential and Universal Width Alternating Finite Automata
M Zakzok - 2024 - qspace.library.queensu.ca
There have been many studies on several models of limited nondeterministic finite automata
(NFAs), including studies on tree width, branching, guessing, and ambiguity of NFAs …
(NFAs), including studies on tree width, branching, guessing, and ambiguity of NFAs …