Testing membership in counter automaton languages

DOI10.1007/978-3-642-40328-6_38zbMATH Open1405.68164OpenAlexW2118242820MaRDI QIDQ2851885FDOQ2851885

Authors: Yonatan Goldhirsh, Michael Viderman 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_38

Recommendations

• Regular languages are testable with a constant number of queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Space Complexity vs. Query Complexity
• Space complexity vs. query complexity
• scientific article; zbMATH DE number 2019622

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Randomized algorithms (68W20)

Cited In (7)

• Automaton-Based Criteria for Membership in CTL
• Testing membership in parenthesis languages
• Title not available (Why is that?)
• Space complexity vs. query complexity
• \(\omega\)-regular languages are testable with a constant number of queries
• Regular languages are testable with a constant number of queries
• Space Complexity vs. Query Complexity

This page was built for publication: Testing membership in counter automaton languages

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