• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Language Equations with Addition in Positional Notation

Artur Jez, Alexander Okhotin, Language Equations with Addition in Positional Notation. TUCS Technical Reports 824, Turku Centre for Computer Science, 2007.

Abstract:

Language equations with an operation of adding numbers
written in a positional notation are considered.
It is shown that this operation together with union and intersection
invests equations with a sufficient expressive power
to simulate every trellis automaton,
as well as to specify some languages
not accepted by any trellis automaton.
The results have applications
to conjunctive grammars over a unary alphabet
and to language equations of a general form.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tJeOk07a,
  title = {Language Equations with Addition in Positional Notation},
  author = {Jez, Artur and Okhotin, Alexander},
  number = {824},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {language equations, conjunctive grammars, unary languages},
  ISBN = {978-952-12-1913-9},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication