Mohammad Zakzok

dblp:237/1675 · DBLP profile ↗
← Back
6ranked-venue papers
2as first author
5since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 6 · 2 first-author · 5 since 2021
YearPublicationVenuePosition
2025 Improved Upper Bounds for Determinizing NIDPDAs with Limited Nondeterminism
Mohammad Zakzok, Kai Salomaa
DLT1
2024 Converting finite width AFAs to nondeterministic and universal finite automata
Mohammad Zakzok, Kai Salomaa
Theor. Comput. Sci.1
2022 Improved complement for two-way alternating automata
Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok
Acta Informatica3
2021 Complement for two-way alternating automata
Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok
Acta Informatica3
2021 Alternation in two-way finite automata
abstract
The study of alternation in two-way finite automata ( 2 fas) has been quite non-systematic. Since the 1970's, various authors with a variety of motivations have studied 2 fas with various types of alternation and a variety of names, creating a fairly long list of sporadic contributions with little internal consistency. This article attempts to organize the subject into a single unifying framework. We start with a detailed account of all contributions to date, that reveals the large variety of approaches and the lack of consistency between them. We then identify and name four types of automata that these contributions have really studied over the years: general two-way Boolean finite automata ( 2 b fas); monotone 2 b fas; basic 2 b fas; and (monotone basic, or) alternating 2 b fas ( 2 a fas). Next, we identify four different ways by which authors have described how such automata compute, each offering a distinct view onto their operation: the circuit view, where computation is modeled by a circuit of Boolean gates; the formula view, where computation is modeled by a Boolean formula over configuration-variables; the run view, where decisions are determined by the existence of appropriate trees of configuration-goal pairs, called “runs”; and the (most classic) tree view, where computation is modeled by a tree of configurations. After carefully defining each 2 b fa type and each view, we prove the following. First, that within each type, every two of the four views are equivalent to each other, in the strong sense that each of them closely mimics the other at every step of the computation. Second, that not all types of 2 b fas are equivalent: although general 2 b fas are as powerful as monotone 2 b fas, and basic 2 b fas are as powerful as 2 a fas (up to polynomial differences in the number of states), general 2 b fas may need exponentially fewer states than 2 a fas.
Christos A. Kapoutsis, Mohammad Zakzok
Theor. Comput. Sci.2
2019 An Oracle Hierarchy for Small One-Way Finite Automata
Malek Anabtawi, Sabit Hassan, Christos A. Kapoutsis, Mohammad Zakzok
LATA4