Accepting runs in a two-way finite automaton

An accepting run in a two-way finite automaton M is a sequence of states that M enters during some accepting computation. The set of all such runs is denoted by Lrun,M. We study the complexity of Lrun,M when M is a 2NFA (2DFA). We also look at the complexity of “position sampling” (the sequence of s...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2018-06, Vol.260, p.1-8
Main Authors: Ibarra, Oscar H., Dang, Zhe, Li, Qin
Format: Article
Language:English
Subjects:
Accepting run
Sampling
Two-way automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An accepting run in a two-way finite automaton M is a sequence of states that M enters during some accepting computation. The set of all such runs is denoted by Lrun,M. We study the complexity of Lrun,M when M is a 2NFA (2DFA). We also look at the complexity of “position sampling” (the sequence of states that M enters in specified positions of some accepted input) in a 2NFA. In particular, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2018.03.002