Go to:
Logótipo
You are in:: Start > Publications > View > On the average complexity of partial derivative transducers *,**,***
Map of Premises
FC6 - Departamento de Ciência de Computadores FC5 - Edifício Central FC4 - Departamento de Biologia FC3 - Departamento de Física e Astronomia e Departamento GAOT FC2 - Departamento de Química e Bioquímica FC1 - Departamento de Matemática
Publication

On the average complexity of partial derivative transducers *,**,***

Title
On the average complexity of partial derivative transducers *,**,***
Type
Article in International Scientific Journal
Year
2023
Authors
Konstantinidis, S
(Author)
Other
The person does not belong to the institution. The person does not belong to the institution. The person does not belong to the institution. Without AUTHENTICUS Without ORCID
António Machiavelo
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Nelma Moreira
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Rogério Reis
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page Without ORCID
Journal
Vol. 956
ISSN: 0304-3975
Publisher: Elsevier
Indexing
Publicação em ISI Web of Knowledge ISI Web of Knowledge - 0 Citations
Publicação em Scopus Scopus - 0 Citations
Other information
Authenticus ID: P-00Y-3E6
Abstract (EN): 2D regular expressions represent rational relations over two alphabets sigma and A. In standard 2D expressions (S2D-RE) the basic terms are generators of sigma* x A*, while in generalised 2D expressions (2D-RE) the basic terms are pairs of (ordinary) regular expressions over one alphabet (1D). In this paper we study the average state complexity of partial derivative standard transducers (TPD) for both S2D-RE and 2D-RE. For S2D-RE we obtain the same asymptotic bounds as for partial derivative automata. For 2D-RE, while in the worst case the number of states of TPD can be O (n2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O (n 2 ). We also show that asymptotically and on average the alphabetic size of a 2D-RE is half of its size. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic functions.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
Language: English
Type (Professor's evaluation): Scientific
No. of pages: 17
Documents
We could not find any documents associated to the publication.
Related Publications

Of the same authors

On the size of partial derivatives and the word membership problem (2021)
Article in International Scientific Journal
Konstantinidis, S; António Machiavelo; Nelma Moreira; Rogério Reis
Partial Derivative Automaton by Compressing Regular Expressions (2021)
Article in International Conference Proceedings Book
Konstantinidis, S; António Machiavelo; Nelma Moreira; Rogério Reis
On the Average State Complexity of Partial Derivative Transducers (2020)
Article in International Conference Proceedings Book
Konstantinidis, S; António Machiavelo; Nelma Moreira; Rogério Reis

Of the same journal

Weak linearization of the lambda calculus (2005)
Article in International Scientific Journal
Alves, S; Florido, M
Turing machines and bimachines (2008)
Article in International Scientific Journal
John Rhodes; Pedro V. Silva
Turing machines and bimachines (2008)
Article in International Scientific Journal
Rhodes, J; Pedro V. Silva
The k-word problem over DRH (2017)
Article in International Scientific Journal
Célia Borlido
The homomorphism problem for trace monoids (2003)
Article in International Scientific Journal
Pedro V. Silva

See all (36)

Recommend this page Top
Copyright 1996-2024 © Faculdade de Ciências da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2024-10-31 at 15:48:04 | Acceptable Use Policy | Data Protection Policy | Complaint Portal