A Unifying Approach to Algebraic Systems Over Semirings
| Autor: | Peter Kostolányi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Power series
Mathematics::General Mathematics Mathematics::Rings and Algebras Pushdown automaton Sigma 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Algebra Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Equivalence (formal languages) Algebraic number Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Theory of Computing Systems. 63:615-633 |
| ISSN: | 1433-0490 1432-4350 |
| Popis: | A fairly general definition of canonical solutions to algebraic systems over semirings is proposed. This is based on the notion of summation semirings, traditionally known as ${\Sigma }$ -semirings, and on assigning unambiguous context-free languages to variables of each system. The presented definition applies to all algebraic systems over continuous or complete semirings and to all proper algebraic systems over power series semirings, for which it coincides with the usual definitions of their canonical solutions. As such, it unifies the approaches to algebraic systems over semirings studied in literature. An equally general approach is adopted to study pushdown automata, for which equivalence with algebraic systems is proved. Finally, the Chomsky-Schutzenberger theorem is generalised to the setting of summation semirings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink