More Concise Representation of Regular Languages by Automata and Regular Expressions

DOI10.1007/978-3-540-85780-8_28MaRDI QIDQ3533024zbMATH OpenOpenAlexFDO

Authors Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_28

zbMATH Keywords

descriptional complexitypushdown automataregular expressionsstraight line programs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• More concise representation of regular languages by automata and regular expressions
• Descriptional complexity of regular languages
• scientific article; zbMATH DE number 7699973
• Provably shorter regular expressions from finite automata
• scientific article; zbMATH DE number 6136496

Cites work

• Alternation
• Characterization of Glushkov automata
• Complexity measures for regular expressions
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Probabilistic automata
• Regular expressions into finite automata
• Regularity and Related Problems for Deterministic Pushdown Automata

Cited in

(14)

• Succinct representation of regular sets using gotos and Boolean variables
• Succinct representations of languages by DFA with different levels of reliability
• Queue automata of constant length
• Descriptional complexity -- an introductory survey
• Series-Parallel Automata and Short Regular Expressions
• scientific article; zbMATH DE number 1870546 (Why is no real title available?)
• scientific article; zbMATH DE number 6136496 (Why is no real title available?)
• Extended to multi-tilde-bar regular expressions and efficient finite automata constructions
• Implementation and Application of Automata
• scientific article; zbMATH DE number 7699973 (Why is no real title available?)
• Representing regular languages of infinite words using mod 2 multiplicity automata
• Regular languages: to finite automata and beyond (invited talk)
• Obtaining shorter regular expressions from finite-state automata
• More concise representation of regular languages by automata and regular expressions

This page was built for publication: More Concise Representation of Regular Languages by Automata and Regular Expressions

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