More concise representation of regular languages by automata and regular expressions

DOI10.1016/j.ic.2010.01.002zbMath1192.68409OpenAlexW2029153962MaRDI QIDQ963066

Viliam Geffert, Carlo Mereghetti, Beatrice Palano

Publication date: 8 April 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.01.002

zbMATH Keywords

regular expressionspushdown automatadescriptional complexitystraight line programs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

A note on controllability of deterministic context-free~systems ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Processing succinct matrices and vectors ⋮ Pushdown and one-counter automata: constant and non-constant memory usage ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ The size-cost of Boolean operations on constant height deterministic pushdown automata ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Two double-exponential gaps for automata with a limited pushdown ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Pushdown automata and constant height: decidability and bounds ⋮ The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ The descriptional power of queue automata of constant length ⋮ Regular expression length via arithmetic formula complexity ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity measures for regular expressions
• Regular expressions into finite automata
• Characterization of Glushkov automata
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Alternation
• Regularity and Related Problems for Deterministic Pushdown Automata
• Probabilistic automata

This page was built for publication: More concise representation of regular languages by automata and regular expressions