On approximating non-regular languages by regular languages

DOI10.3233/FI-2011-532MaRDI QIDQ3100930zbMATH OpenOpenAlexFDO

Authors G. Eisman, B. Ravikumar

Publication date 22 November 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-532

zbMATH Keywords

approximationfinite automatasquaringmajority language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the existence of regular approximations
• EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA
• scientific article; zbMATH DE number 88935
• STACS 2005
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(7)

• Asymptotic approximation by regular languages
• An optimal lower bound for nonregular languages
• Non-regular Maximal Prefix-Free Subsets of Regular Languages
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• On counting functions and slenderness of languages
• Corrigendum to ``An optimal lower bound for nonregular languages
• scientific article; zbMATH DE number 2213327 (Why is no real title available?)

This page was built for publication: On approximating non-regular languages by regular languages

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