This HTML5 document contains 7 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

n2:abstract

rdf:type

fabio:Abstract

rdf:value

We consider measures that limit universal parallelism in computations of an alternating finite automaton (AFA). Maximum pared tree width counts the largest number of universal branches in any computation and acceptance width counts the number of universal branches in the best accepting computation, i.e., in the accepting computation with least universal parallelism. We give algorithms to decide whether the maximum pared tree width or the acceptance width of an AFA are bounded by an integer k. For a constant k the algorithm for maximum pared tree width operates in polynomial time. An AFA with m states and acceptance width k can be converted to an NFA with [Formula: see text] states. We consider corresponding lower bounds for the transformation. The tree width of an AFA counts the number of all (existential and universal) branches of the computation. We give upper and lower bounds for converting an AFA of bounded tree width to a DFA.

dct:subject

Order theory Graph invariants Graph minor theory Finite automata

frbr:partOf

covid:72431b6decbbfe12d8b055b7fb20765d83c3b240