Decidable weighted expressions with Presburger combinators

Autor: Nicolas Mazzocchi, Emmanuel Filiot, Jean-François Raskin
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL)
Computer Networks and Communications
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
020204 information systems
Kleene star
0202 electrical engineering
electronic engineering
information engineering
Mathematics
Discrete mathematics
Applied Mathematics
Decision problem
16. Peace & justice
Expression (mathematics)
Decidability
Undecidable problem
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computational Theory and Mathematics
010201 computation theory & mathematics
Iterated function
Combinatory logic
Presburger arithmetic
Computer Science::Formal Languages and Automata Theory
Sciences exactes et naturelles
Zdroj: Journal of computer and system sciences, 106
ISSN: 0022-0000
Popis: In this paper, we investigate the expressive power and the algorithmic properties of weighted expressions, which define functions from finite words to integers. First, we consider a slight extension of an expression formalism, introduced by Chatterjee. et. al. in the context of infinite words, by which to combine values given by unambiguous (max,+)-automata, using Presburger arithmetic. We show that important decision problems such as emptiness, universality and comparison are PSpace-c for these expressions. We then investigate the extension of these expressions with Kleene star. This allows to iterate an expression over smaller fragments of the input word, and to combine the results by taking their iterated sum. The decision problems turn out to be undecidable, but we introduce the decidable and still expressive class of synchronised expressions.
FCT2017 Acceptance
Databáze: OpenAIRE
Externí odkaz: