Deterministic generalized automata

DOI10.1016/S0304-3975(97)00166-7zbMath0915.68118MaRDI QIDQ1285583

Dora Giammarresi, Rosa Montalbano

Publication date: 28 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular languagesminimal automatageneralized automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Deciding determinism of caterpillar expressions ⋮ Obtaining shorter regular expressions from finite-state automata ⋮ The palindromization map ⋮ Prefix-free regular languages and pattern matching ⋮ Generalizations of 1-deterministic regular languages ⋮ THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA ⋮ Algorithms for learning regular expressions from positive data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• The node-deletion problem for hereditary properties is NP-complete
• Minimization algorithms for sequential transducers
• Economy of description for single-valued transducers
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Minimal NFA Problems are Hard
• Deterministic generalized automata
• Complexity results for multi-pebble automata and their logics

This page was built for publication: Deterministic generalized automata