From bidirectionality to alternation.
type: Item
instance of: scholarly article
title: From bidirectionality to alternation.
zbMATH Open document ID: 1044.68101
DOI: 10.1016/S0304-3975(02)00410-3
author: Nir Piterman
author: Moshe Y. Vardi
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1965280
zbMATH Keywords: Two-way automata
zbMATH Keywords: Nondeterministic finite automata
zbMATH Keywords: Nondeterministic Büchi automata
zbMATH Keywords: Alternating finite automata
zbMATH Keywords: Alternating Büchi automata
MaRDI profile type: Publication
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: On equations for regular languages, finite automata, and sequential networks
cites work: Alternation
cites work: Theories of automata on \(\omega\)-tapes: a simplified approach
cites work: Complexity results for two-way and multi-pebble automata and their logics
cites work: Q4356434
cites work: Automatic generation of efficient lexical processors using finite state techniques
cites work: Q5606985
cites work: Weak alternating automata are not that weak
cites work: Q2754072
cites work: Alternating Pushdown and Stack Automata
cites work: Testing and generating infinite sequences by a finite automaton
cites work: Alternating finite automata on \(\omega\)-words
cites work: Alternating automata on infinite trees
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Q5541339
cites work: Tree-size bounded alternation
cites work: Nondeterminism and the size of two way finite automata
cites work: Q5541340
cites work: Propositional dynamic logic of looping and converse is elementarily decidable
cites work: A note on the reduction of two-way automata to one-way automata
cites work: Endmarkers can make a difference
cites work: Q4219045
cites work: Properties that characterize LOGCFL
cites work: Q4501666
full work available at URL: s0304-3975(02)00410-3
OpenAlex ID: W1491652234
description: scientific article; zbMATH DE number 1965280