Nondeterminism versus determinism of finite automata over directed acyclic graphs | Zendy

Andreas Potthoff | Zendy; Sebastian Seibert | Zendy; Wolfgang Thomas | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Nondeterminism versus determinism of finite automata over directed acyclic graphs

Author(s) -

Andreas Potthoff,

Sebastian Seibert,

Wolfgang Thomas

Publication year - 1994

Publication title -

bulletin of the belgian mathematical society - simon stevin

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.36

H-Index - 31

eISSN - 2034-1970

pISSN - 1370-1444

DOI - 10.36045/bbms/1103408550

Subject(s) - directed acyclic graph , automaton , equivalence (formal languages) , combinatorics , discrete mathematics , mathematics , directed graph , determinism , finite state machine , computer science , theoretical computer science , algorithm , physics , quantum mechanics

Three types of nite-state graph automata are compared over directed acyclic graphs (where vertices and edges are labelled). The automata are distinguished by the way how states are attached to an input graph (\vertexmarking", \edge-marking", and \1-sphere-marking"). We note the equivalence of these models, relate them to logical denability notions, and show that deterministic versions are strictly weaker (thus correcting an error of [9]).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research