Alternation in two-way finite automata
type: Item
instance of: scholarly article
title: Alternation in two-way finite automata
zbMATH Open document ID: 1504.68104
author: Christos Kapoutsis
author: Mohammad Zakzok
published in: Theoretical Computer Science
publication date: 2021-06-03T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7354759
zbMATH Keywords: two-way automata
zbMATH Keywords: alternation
zbMATH Keywords: state complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2020.12.011
OpenAlex ID: W3113059832
cites work: Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: Two-way automata and length-preserving homomorphisms
cites work: Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday
cites work: On equations for regular languages, finite automata, and sequential networks
cites work: Q3971274
cites work: Alternation
cites work: Constructions for alternating finite automata∗
cites work: An alternating hierarchy for finite automata
cites work: Complement for two-way alternating automata
cites work: Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
cites work: Complexity results for two-way and multi-pebble automata and their logics
cites work: Descriptional and Computational Complexity of Finite Automata
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: The complexity of concatenation on deterministic and alternating finite automata
cites work: Operations on Boolean and alternating finite automata
cites work: Descriptional Complexity of Operations on Alternating and Boolean Automata
cites work: Size Complexity of Two-Way Finite Automata
cites work: Q2957449
cites work: Square on deterministic, alternating, and Boolean finite automata
cites work: Alternating Pushdown and Stack Automata
cites work: On generalized language equations
cites work: Succinct representation of regular languages by Boolean automata
cites work: Succinct representation of regular languages by Boolean automata. II
cites work: From bidirectionality to alternation.
cites work: The theory of formal languages
cites work: Nondeterminism and the size of two way finite automata
cites work: Alternating finite automata and star-free languages
cites work: Probabilism versus Alternation for Automata
DOI: 10.1016/J.TCS.2020.12.011
description: scientific article; zbMATH DE number 7354759