About: Alternating Finite Automata with Limited Universal Branching

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Alternating Finite Automata with Limited Universal Branching Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Alternating Finite Automata with Limited Universal Branching
Creator	Keeler, Chris Salomaa, Kai
Source	PMC
abstract	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.
has issue date	2020-01-07(xsd:dateTime)
bibo:doi	10.1007/978-3-030-40608-0_13
has license	no-cc
sha1sum (hex)	72431b6decbbfe12d8b055b7fb20765d83c3b240
schema:url	https://doi.org/10.1007/978-3-030-40608-0_13
resource representing a document's title	Alternating Finite Automata with Limited Universal Branching
has PubMed Central identifier	PMC7206628
schema:publication	Language and Automata Theory and Applications
resource representing a document's body	covid:72431b6decbbfe12d8b055b7fb20765d83c3b240#body_text
is schema:about of	named entity 'universal' named entity 'universal' named entity 'universal' named entity 'NFA' named entity 'AFA' named entity 'tree width' named entity 'Maximum' named entity 'universal' named entity 'computation' named entity 'parallelism' named entity 'alternating finite automaton' named entity 'parallelism' named entity 'acceptance' named entity 'maximum' named entity 'decidable' named entity 'Hromkovič' named entity 'state complexity' named entity 'DFA' named entity 'DFAs' named entity 'tree width' named entity 'decidable' named entity 'child nodes' named entity 'tree width' named entity 'nondeterministic finite automata' named entity 'computation tree' named entity 'infix' named entity 'membership problem' named entity '6-tuple' named entity 'common multiple' named entity 'PSPACE-complete' named entity 'PSPACE-complete' named entity 'computation tree' named entity 'computation tree' named entity 'integer' named entity 'disjoint' named entity 'emptiness problem' named entity 'Kozen' named entity 'NFA' named entity 'nondeterminism' named entity 'strings' named entity 'pairwise coprime' named entity 'n-tuple' named entity 'universal state' named entity 'pairwise coprime' named entity 'DFA' named entity 'transition function' named entity 'NFAs' named entity 'tree width' named entity 'state complexity' named entity 'infix' named entity 'tuple' named entity 'automata' named entity 'tree width' named entity 'PSPACE-Complete' named entity 'ordered tuple' named entity 'infix' named entity 'constant factor' named entity 'computation tree' named entity 'nondeterminism' named entity 'strings' named entity 'NFA' named entity 'tuple' named entity 'boolean' named entity 'state complexity' named entity 'NFA' named entity 'polynomial time' named entity 'pairwise coprime' named entity 'computation tree' named entity 'pushdown automata' named entity 'tree width' named entity 'pushdown automata' named entity 'NFAs' named entity 'computation tree' named entity 'tree width' named entity 'Stockmeyer' named entity 'tree width' named entity 'tree width' named entity 'NFA' named entity 'depth-first' named entity 'nondeterminism' named entity 'polynomial transformation' named entity 'DFAs'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software