scientific article; zbMATH DE number 6515829

MaRDI QIDQ3455037zbMATH OpenFDO

Authors Viliam Geffert, Abuzer Yakaryılmaz

Publication date 3 December 2015

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2717/0.html

zbMATH Keywords

alternating automatadescriptional complexitynondeterministic automataprobabilistic automatapromise problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Classical automata on promise problems
• Promise problems solved by quantum and classical finite automata
• Complexity of promise problems on classical and quantum automata
• On a class ofPautomata
• Promise problems complete for complexity classes
• scientific article; zbMATH DE number 2032360
• scientific article; zbMATH DE number 761756
• Classes of timed automata and the undecidability of universality
• Classes of timed automata and the undecidability of universality

Cited in

(10)

• Improved constructions for succinct affine automata
• Tight hierarchy of data-independent multi-head automata
• Language Recognition Power and Succinctness of Affine Automata
• Complexity of promise problems on classical and quantum automata
• Promise problems solved by quantum and classical finite automata
• Two double-exponential gaps for automata with a limited pushdown
• Minimal Size of Counters for (Real-Time) Multicounter Automata
• Classical automata on promise problems
• Language recognition power and succinctness of affine automata
• Exact Affine Counter Automata

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455037)