On approximating non-regular languages by regular languages

DOI10.3233/FI-2011-532zbMATH Open1234.68209OpenAlexW1826276606MaRDI QIDQ3100930FDOQ3100930

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

Recommendations

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

zbMATH Keywords

approximationfinite automatasquaringmajority language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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
• Title not available (Why is that?)
• Corrigendum to ``An optimal lower bound for nonregular languages

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)