Average State Complexity of Partial Derivative Automata for Synchronised Shuffles

International Journal of Foundations of Computer Science

2026 | journal-article

On the Descriptional Complexity of Literal Shuffle

2026 | book-chapter

Language Quotients Revisited

International Journal of Foundations of Computer Science

2025 | journal-article

Automata for Synchronised Shuffle on Backbones

2025 | book-chapter

Two-Word Shuffle: Some Results

2025 | book-chapter

Compressed Structures for Partial Derivative Automata Constructions

International Journal of Foundations of Computer Science

2024 | journal-article

Block Languages and Their Bitmap Representations

2024 | book-chapter

Location automata for regular expressions with shuffle and intersection

Information and Computation

2023 | journal-article

On the average complexity of partial derivative transducers

Theoretical Computer Science

2023 | journal-article

Location automata for synchronised shuffle expressions

Journal of Logical and Algebraic Methods in Programming

2023 | journal-article

25th International Conference on Developments in Language Theory (DLT 2021): Preface

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

2023 | other

Approximate NFA universality and related problems motivated by information theory

Theor. Comput. Sci.

2023 | journal-article

Approximate NFA universality and related problems motivated by information theory & nbsp;

THEORETICAL COMPUTER SCIENCE

2023 | journal-article

Average Complexity of Partial Derivatives for Synchronised Shuffle Expressions

2023 | book-chapter

Approximate NFA Universality Motivated by Information Theory

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2022

2022 | conference-paper

Approximate NFA Universality and Related Problems Motivated by Information Theory

CoRR

2022 | other

Manipulation of Regular Expressions Using Derivatives: An Overview

IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2022)

2022 | conference-paper

On the size of partial derivatives and the word membership problem

Acta Informatica

2021 | journal-article

Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings

DLT

2021 | edited-book

Hot Current Topics of Descriptional Complexity

Advancing Research in Information and Communication Technology - IFIP's Exciting First 60+ Years, Views from the Technical Committees and Working Groups

2021 | book-chapter

Location Based Automata for Expressions with Shuffle

2021 | book-chapter

On the Uniform Distribution of Regular Expressions

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2021

2021 | conference-paper

On the Uniform Distribution of Regular Expressions

CoRR

2021 | other

Partial Derivative Automaton by Compressing Regular Expressions

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2021

2021 | conference-paper

Preface

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

2021 | other

The Prefix Automaton

J. Autom. Lang. Comb.

2021 | journal-article

Formal Methods. FM 2019 International Workshops - Porto, Portugal, October 7-11, 2019, Revised Selected Papers, Part I

FM Workshops (1)

2020 | edited-book

Formal Methods. FM 2019 International Workshops - Porto, Portugal, October 7-11, 2019, Revised Selected Papers, Part II

FM Workshops (2)

2020 | edited-book

Guest Column: Analytic Combinatorics and Descriptional Complexity of Regular Languages on Average

SIGACT News

2020 | journal-article

On the Average State Complexity of Partial Derivative Transducers

SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE

2020 | conference-paper

A mesh of automata

Information and Computation

2019 | journal-article

On Average Behaviour of Regular Expressions in Strong Star Normal Form

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

2019 | journal-article

Partial Derivatives of Regular Expressions over Alphabet-Invariant and User-Defined Labels

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

2019 | book

Some Applications of the Formalization of the Pumping Lemma for Context-Free Languages

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE

2019 | conference-paper

Automata for regular expressions with shuffle

Information and Computation

2018 | journal-article

Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018

2018 | conference-paper

Position automata for semi-extended expressions

Journal of Automata, Languages and Combinatorics

2018 | journal-article

RANDOMIZED GENERATION OF ERROR CONTROL CODES WITH AUTOMATA AND TRANSDUCERS

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

2018 | journal-article

Regular Expressions and Transducers over Alphabet-Invariant and User-Defined Labels

IAA

2018 | conference-paper

Symbolic Manipulation of Code Properties

Journal of Automata, Languages and Combinatorics

2018 | journal-article

The Computational Power of Parsing Expression Grammars

Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings

2018 | conference-paper

A Survey on Operational State Complexity

Journal of Automata, Languages and Combinatorics

2017 | journal-article

On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions

Journal of Automata, Languages and Combinatorics

2017 | journal-article

On the Average Complexity of Strong Star Normal Form

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2017

2017 | conference-paper

On the Mother of All Automata: The Position Automaton

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017

2017 | conference-paper

Preface

Role of Theory in Computer Science, The: Essays Dedicated to Janusz Brzozowski

2017 | other

The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski

2017 | edited-book

Automata serialization for manipulation and drawing

OpenAccess Series in Informatics

2016 | conference-paper

Channels with Synchronization/Substitution Errors and Computation of Error Control Codes

CoRR

2016 | other

Distinguishability Operations and Closures

FUNDAMENTA INFORMATICAE

2016 | journal-article

Formalization of the pumping lemma for context-free languages

Journal of Formalized Reasoning

2016 | journal-article

Generating error control codes with automata and transducers

Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Proceedings

2016 | conference-paper

Implementation of Code Properties via Transducers

Implementation and Application of Automata

2016 | conference-paper

On the Formalization of Some Results of Context-Free Language Theory

LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION

2016 | conference-paper

On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

Descriptional Complexity of Formal Systems - 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings

2016 | conference-paper

On the dissimilarity operation on finite languages

Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Proceedings

2016 | conference-paper

Position Automaton Construction for Regular Expressions with Intersection

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2016

2016 | conference-paper

Preface: Non-classical models of automata and applications VII

RAIRO - Theoretical Informatics and Applications

2016 | journal-article

Average Size of Automata Constructions from Regular Expressions

Bulletin of the EATCS

2015 | journal-article

Deciding Kleene algebra terms equivalence in Coq

Journal of Logical and Algebraic Methods in Programming

2015 | journal-article

Deciding synchronous Kleene algebra with derivatives

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

2015 | conference-paper

Formalization of context-free language theory

CoRR

2015 | other

Incomplete operational transition complexity of regular languages

Information and Computation

2015 | journal-article

Optimal State Reductions of Automata with Partially Specified Behaviors

SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE

2015 | conference-paper

Partial Derivative Automaton for Regular Expressions with Shuffle

Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings

2015 | conference-paper

Prefix and Right-Partial Derivative Automata

EVOLVING COMPUTABILITY

2015 | conference-paper

Seventh Workshop on Non-Classical Models of Automata and Applications - NCMA 2015, Porto, Portugal, August 31 - September 1, 2015. Proceedings

NCMA

2015 | edited-book

Universal Disjunctive Concatenation and Star

Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings

2015 | conference-paper

A Hitchhiker's Guide to descriptional complexity through analytic combinatorics

Theoretical Computer Science

2014 | journal-article

On the Equivalence of Automata for KAT-expressions

Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings

2014 | conference-paper

Partial Derivative and Position Bisimilarity Automata

IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2014

2014 | conference-paper

Symmetric Groups and Quotient Complexity of Boolean Operations

AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT II

2014 | conference-paper

The distinguishability operation on regular languages

Sixth Workshop on Non-Classical Models for Automata and Applications - NCMA 2014, Kassel, Germany, July 28-29, 2014. Proceedings

2014 | conference-paper

Incomplete Transition Complexity of Basic Operations on Finite Languages

Implementation and Application of Automata - 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings

2013 | conference-paper

Incomplete Transition Complexity of Some Basic Operations

SOFSEM 2013: Theory and Practice of Computer Science

2013 | conference-paper

On the Average Size of Glushkov and Equation Automata for KAT Expressions

Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings

2013 | conference-paper

Preface

Int. J. Found. Comput. Sci.

2013 | journal-article

Deciding regular expressions (in-)equivalence in Coq

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

2012 | conference-paper

Editorial

Journal of Automata, Languages and Combinatorics

2012 | journal-article

Finite Automata Minimization

Handbook of Finite State Based Models and Applications.

2012 | book-chapter

Implementation and Application of Automata - 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings

CIAA

2012 | edited-book

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

2012 | other

On the average size of glushkov and partial derivative automata

International Journal of Foundations of Computer Science

2012 | journal-article

Incremental DFA Minimisation

IMPLEMENTATION AND APPLICATION OF AUTOMATA

2011 | conference-paper

On the average state complexity of partial derivative automata: An analytic combinatorics approach

International Journal of Foundations of Computer Science

2011 | journal-article

Partial Derivative Automata Formalized in Coq

IMPLEMENTATION AND APPLICATION OF AUTOMATA

2011 | conference-paper

The Average Transition Complexity of Glushkov and Partial Derivative Automata

Developments in Language Theory - 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings

2011 | conference-paper

On the Average Number of States of Partial Derivative Automata

DEVELOPMENTS IN LANGUAGE THEORY

2010 | conference-paper

Small NFAs from Regular Expressions: Some Experimental Results

CoRR

2010 | other

Testing the Equivalence of Regular Languages

Journal of Automata, Languages and Combinatorics

2010 | journal-article

XML Description for Automata Manipulations

XATA 2010, XML: aplicações e tecnologias associadas

2010 | conference-paper

Antimirov and Mosses's rewrite system revisited

International Journal of Foundations of Computer Science

2009 | journal-article

FAdo and GUItar: Tools for Automata Manipulation and Visualization

IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS

2009 | conference-paper

Series-parallel automata and short regular expressions

Fundamenta Informaticae

2009 | journal-article

A Toolkit for an Oral History Digital Archive

Actas XATA 2008, XML: aplicações e tecnologias associadas

2008 | conference-paper

Exact generation of minimal acyclic deterministic finite automata

International Journal of Foundations of Computer Science

2008 | journal-article

Formal Modelling of Emotions in BDI Agents

COMPUTATIONAL LOGIC IN MULTI-AGENT SYSTEMS

2008 | conference-paper

KAT and PHL in Coq

Computer Science and Information Systems

2008 | journal-article

Enumeration and generation with a string automata representation

Theoretical Computer Science

2007 | journal-article

Acyclic automata with easy-to-find short regular expressions

IMPLEMENTATION AND APPLICATION OF AUTOMATA

2006 | journal-article

Aspects of enumeration and generation with a string automata representation

8th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2006 - Proceedings

2006 | conference-paper

Designing a solver for arithmetic constraints to support education in mathematics

Artificial Intelligence Applications and Innovations

2006 | conference-paper

Interactive manipulation of regular objects with FAdo

Proceedings of the 10th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education

2005 | conference-paper

On the density of languages representing finite set partitions

Journal of Integer Sequences

2005 | journal-article

On the representation of finite automata

7th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2005 - Proceedings

2005 | conference-paper

Towards an architecture for Emotional BDI agents

2005 Portuguese Conference on Artificial Intelligence, Proceedings

2005 | conference-paper

Apoo: an environment for a first course in assembly language programming

SIGCSE Bulletin

2001 | journal-article

Constraint Categorial Grammars

Progress in Artificial Intelligence, 7th Portuguese Conference on Artificial Intelligence, EPIA '95, Funchal, Madeira Island, Portugal, October 3-6, 1995, Proceedings

1995 | conference-paper

Resolution of Constraints in Algebras of Rational Trees

Progress in Artificial Intelligence, 6th Portuguese Conference on Artificial Intelligence, EPIA '93, Porto, Portugal, October 6-8, 1993, Proceedings

1993 | conference-paper

An History Based Interface

Proceedings of the ICLP 1991 Workshop on Logic Programming Environments, Paris, June 1991. Technical Report, University of Orléans, France, LIFO N 91-6

1991 | conference-paper

Natural Language Processing, EAIA '90, 2nd Advanced School in Artificial Intelligence, Guarda, Portugal, October 8-12, 1990, Proceedings

EAIA

1991 | edited-book

The Formal and Processing Models of CLG

EACL 1991, 5th Conference of the European Chapter of the Association for Computational Linguistics, April 9-11, 1991, Congress Hall, Alexanderplatz, Berlin, Germany

1991 | conference-paper

CLG(n): Constraint Logic Grammars

13th International Conference on Computational Linguistics, COLING 1990, University of Helsinki, Finland, August 20-25, 1990

1990 | conference-paper

General Introduction

Natural Language Processing, EAIA '90, 2nd Advanced School in Artificial Intelligence, Guarda, Portugal, October 8-12, 1990, Proceedings

1990 | conference-paper

Natural Language and Natural Menus Interfaces

Modelling the Innovation: Communications, Automation and Information Systems, Proceedings of the IFIP TC7 Conference on Modelling the Innovation: Communications, Automation and Information Systems, Rome, Italy, 21-23 March, 1990

1990 | conference-paper

Semantic Analysis of Time and Tense in Natural Language: An Implementation

EPIA 89, 4th Portuguese Conference on Artificial Intelligence, Lisbon, Portugal, September 26-29, 1989, Proceedings

1989 | conference-paper

Deciding KAT and Hoare Logic with Derivatives

| conference-paper

Exact Generation of Acyclic Deterministic Finite Automata

| book-chapter

State Elimination Ordering Strategies: Some Experimental Results

| conference-paper