2024
Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration.
Proc. ACM Manag. Data, November, 2024
On the structure of solution-sets to regular word equations.
Theory Comput. Syst., August, 2024
A Closer Look at the Expressive Power of Logics Based on Word Equations.
Theory Comput. Syst., June, 2024
Semënov Arithmetic, Affine {VASS}, and String Constraints.
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024
SMTQuery: Analysing SMT-LIB String Benchmarks.
Proceedings of the Formal Methods: Foundations and Applications - 27th Brazilian Symposium, 2024
Enumerating m-Length Walks in Directed Graphs with Constant Delay.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024
Subsequence Matching and Analysis Problems for Formal Languages.
Proceedings of the 35th International Symposium on Algorithms and Computation, 2024
Layered and Staged Monte Carlo Tree Search for SMT Strategy Synthesis.
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024
Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds.
Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching, 2024
2023
ZaligVinder: A generic test framework for string solvers.
J. Softw. Evol. Process., April, 2023
On the Expressive Power of String Constraints.
Proc. ACM Program. Lang., January, 2023
Towards more efficient methods for solving regular-expression heavy string constraints.
Theor. Comput. Sci., 2023
Formal Languages via Theories over Strings: An Overview of Some Recent Results.
Bull. EATCS, 2023
On the Number of Factors in the LZ-End Factorization.
Proceedings of the String Processing and Information Retrieval, 2023
Matching Patterns with Variables Under Simon's Congruence.
Proceedings of the Reachability Problems - 17th International Conference, 2023
k-Universality of Regular Languages.
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023
Longest Common Subsequence with Gap Constraints.
Proceedings of the Combinatorics on Words - 14th International Conference, 2023
2022
Preface and Greeting Messages.
J. Autom. Lang. Comb., 2022
Absent Subsequences in Words.
Fundam. Informaticae, 2022
Combinatorial Algorithms for Subsequence Matching: A Survey.
Proceedings of the Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications, 2022
A Generic Information Extraction System for String Constraints.
CoRR, 2022
Formal Languages via Theories over Strings.
CoRR, 2022
Fast and Longest Rollercoasters.
Algorithmica, 2022
Matching Patterns with Variables Under Edit Distance.
Proceedings of the String Processing and Information Retrieval, 2022
Subsequences in Bounded Ranges: Matching and Analysis Problems.
Proceedings of the Reachability Problems - 16th International Conference, 2022
Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems.
Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022
2021
Reconstructing Words from Right-Bounded-Block Words.
Int. J. Found. Comput. Sci., 2021
On Turing Machines Deciding According to the Shortest Computations.
Axioms, 2021
Efficiently Testing Simon's Congruence.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021
The Edit Distance to k-Subsequence Universality.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021
Blocksequences of k-local Words.
Proceedings of the SOFSEM 2021: Theory and Practice of Computer Science, 2021
Matching Patterns with Variables Under Hamming Distance.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021
String Theories Involving Regular Membership Predicates: From Practice to Theory and Back.
Proceedings of the Combinatorics on Words - 13th International Conference, 2021
An SMT Solver for Regular Expressions and Linear Arithmetic over String Length.
Proceedings of the Computer Aided Verification - 33rd International Conference, 2021
2020
Pattern Matching with Variables: Efficient Algorithms and Complexity Results.
ACM Trans. Comput. Theory, 2020
Preface - Special Issue: A Collection of Papers in Honour of the 60th Birthday of Victor Mitrana.
Int. J. Found. Comput. Sci., 2020
Equations enforcing repetitions under permutations.
Discret. Appl. Math., 2020
A Length-aware Regular Expression SMT Solver.
CoRR, 2020
The Edit Distance to k-Subsequence Universality.
CoRR, 2020
The Power of String Solving: Simplicity of Comparison.
Proceedings of the AST@ICSE 2020: IEEE/ACM 1st International Conference on Automation of Software Test, 2020
Rule-based Word Equation Solving.
Proceedings of the FormaliSE@ICSE 2020: 8th International Conference on Formal Methods in Software Engineering, 2020
Scattered Factor-Universality of Words.
Proceedings of the Developments in Language Theory - 24th International Conference, 2020
2019
Rollercoasters: Long Sequences without Short Runs.
SIAM J. Discret. Math., 2019
Hide and seek with repetitions.
J. Comput. Syst. Sci., 2019
On Modelling the Avoidability of Patterns as CSP.
CoRR, 2019
k-Spectra of c-Balanced Words.
CoRR, 2019
On Solving Word Equations Using SAT.
Proceedings of the Reachability Problems - 13th International Conference, 2019
Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
k-Spectra of Weakly-c-Balanced Words.
Proceedings of the Developments in Language Theory - 23rd International Conference, 2019
Matching Patterns with Variables.
Proceedings of the Combinatorics on Words - 12th International Conference, 2019
2018
Revisiting Shinohara's algorithm for computing descriptive patterns.
Theor. Comput. Sci., 2018
Unary patterns under permutations.
Theor. Comput. Sci., 2018
Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.
Theory Comput. Syst., 2018
On the Complexity of Solving Restricted Word Equations.
Int. J. Found. Comput. Sci., 2018
The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability.
CoRR, 2018
The Satisfiability of Word Equations: Decidable and Undecidable Theories.
Proceedings of the Reachability Problems - 12th International Conference, 2018
Rollercoasters and Caterpillars.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
On Matching Generalised Repetitive Patterns.
Proceedings of the Developments in Language Theory - 22nd International Conference, 2018
2017
TCS Special Issue on Languages and Combinatorics in Theory and Nature.
Theor. Comput. Sci., 2017
TCS Special Issue: Combinatorics on Words - WORDS 2015.
Theor. Comput. Sci., 2017
The extended equation of Lyndon and Schützenberger.
J. Comput. Syst. Sci., 2017
J. Autom. Lang. Comb., 2017
Longest Gapped Repeats and Palindromes.
Discret. Math. Theor. Comput. Sci., 2017
Detecting One-Variable Patterns.
Proceedings of the String Processing and Information Retrieval, 2017
The Hardness of Solving Simple Word Equations.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017
Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017
2016
Detecting Unary Patterns.
CoRR, 2016
Efficiently Finding All Maximal alpha-gapped Repeats.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016
On the Solvability Problem for Restricted Classes of Word Equations.
Proceedings of the Developments in Language Theory - 20th International Conference, 2016
Factorizing a String into Squares in Linear Time.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016
2015
Hairpin lengthening: language theoretic and algorithmic results.
J. Log. Comput., 2015
k-Abelian pattern matching.
J. Discrete Algorithms, 2015
Cubic patterns with permutations.
J. Comput. Syst. Sci., 2015
Bounded Prefix-Suffix Duplication: Language Theoretic and Algorithmic Results.
Int. J. Found. Comput. Sci., 2015
On the Power of Accepting Networks of Evolutionary Processors with Special Topologies and Random Context Filters.
Fundam. Informaticae, 2015
Efficiently Finding All Maximal $α$-gapped Repeats.
CoRR, 2015
Testing k-binomial equivalence.
CoRR, 2015
Pattern Matching with Variables: Fast Algorithms and New Hardness Results.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015
On Prefix/Suffix-Square Free Words.
Proceedings of the String Processing and Information Retrieval, 2015
Longest Gapped Repeats and Palindromes.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015
Longest α-Gapped Repeat and Palindrome.
Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015
Unary Patterns with Permutations.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015
Square-Density Increasing Mappings.
Proceedings of the Combinatorics on Words - 10th International Conference, 2015
Prefix-Suffix Square Completion.
Proceedings of the Combinatorics on Words - 10th International Conference, 2015
2014
Accepting Networks of Evolutionary Processors with Subregular Filters.
Theory Comput. Syst., 2014
Prefix-suffix duplication.
J. Comput. Syst. Sci., 2014
Regular languages of partial words.
Inf. Sci., 2014
Inner Palindromic Closure.
Int. J. Found. Comput. Sci., 2014
The pseudopalindromic completion of regular languages.
Inf. Comput., 2014
Syllabic Languages and Go-through Automata.
Fundam. Informaticae, 2014
An algorithmic toolbox for periodic partial words.
Discret. Appl. Math., 2014
Bounded Prefix-Suffix Duplication.
Proceedings of the Implementation and Application of Automata, 2014
Testing Generalised Freeness of Words.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014
A Stronger Square Conjecture on Binary Words.
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014
Generalised Lyndon-Schützenberger Equations.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014
Two Variants of Synchronized Shuffle on Backbones.
Proceedings of the Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005)., 2014
2013
The hardness of counting full words compatible with partial words.
J. Comput. Syst. Sci., 2013
Networks of evolutionary processors: the power of subregular filters.
Acta Informatica, 2013
Finding Pseudo-repetitions.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013
On the Pseudoperiodic Extension of u^l = v^m w^n.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013
Discovering Hidden Repetitions in Words.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013
2012
Language classes generated by tree controlled grammars with bounded nonterminal complexity.
Theor. Comput. Sci., 2012
Complexity results for deciding Networks of Evolutionary Processors.
Theor. Comput. Sci., 2012
On external contextual grammars with subregular selection languages.
Theor. Comput. Sci., 2012
Networks of evolutionary processors: computationally complete normal forms.
Nat. Comput., 2012
On Subregular Selection Languages in Internal Contextual Grammars.
J. Autom. Lang. Comb., 2012
Generating Networks of Splicing Processors.
RAIRO Theor. Informatics Appl., 2012
String Matching with Involutions.
Proceedings of the Unconventional Computation and Natural Computation, 2012
Fine and Wilf's Theorem and Pseudo-repetitions.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012
The Avoidability of Cubes under Permutations.
Proceedings of the Developments in Language Theory - 16th International Conference, 2012
On Internal Contextual Grammars with Subregular Selection Languages.
Proceedings of the Descriptional Complexity of Formal Systems, 2012
Connecting Partial Words and Regular Languages.
Proceedings of the How the World Computes, 2012
Hairpin Lengthening and Shortening of Regular Languages.
Proceedings of the Languages Alive, 2012
2011
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors.
Nat. Comput., 2011
Bounded hairpin completion.
Inf. Comput., 2011
On Normal Forms for Networks of Evolutionary Processors.
Proceedings of the Unconventional Computation - 10th International Conference, 2011
Periodicity Algorithms for Partial Words.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011
Networks of Evolutionary Processors with Subregular Filters.
Proceedings of the Language and Automata Theory and Applications, 2011
Deciding Networks of Evolutionary Processors.
Proceedings of the Developments in Language Theory - 15th International Conference, 2011
<i>k</i>-Local Internal Contextual Grammars.
Proceedings of the Descriptional Complexity of Formal Systems, 2011
On Contextual Grammars with Subregular Selection Languages.
Proceedings of the Descriptional Complexity of Formal Systems, 2011
Deciding According to the Shortest Computations.
Proceedings of the Models of Computation in Context, 2011
Proceedings of the Computation, 2011
2010
A series of algorithmic results related to the iterated hairpin completion.
Theor. Comput. Sci., 2010
A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors.
Theory Comput. Syst., 2010
Some Remarks on the Hairpin Completion.
Int. J. Found. Comput. Sci., 2010
Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication
Proceedings of the Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, 2010
Small universal accepting hybrid networks of evolutionary processors.
Acta Informatica, 2010
Hard Counting Problems for Partial Words.
Proceedings of the Language and Automata Theory and Applications, 2010
Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010
Accepting Networks of Evolutionary Word and Picture Processors: A Survey.
Proceedings of the Scientific Applications of Language Methods., 2010
2009
Two complementary operations inspired by the DNA hairpin formation: Completion and reduction.
Theor. Comput. Sci., 2009
On small, reduced, and fast universal accepting networks of splicing processors.
Theor. Comput. Sci., 2009
On some algorithmic problems regarding the hairpin completion.
Discret. Appl. Math., 2009
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections
Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009
Networks of Evolutionary Picture Processors with Filtered Connections.
Proceedings of the Unconventional Computation, 8th International Conference, 2009
Accepting Networks of Evolutionary Processors: Complexity Aspects - Recent Results and New Challenges.
Proceedings of the ICAART 2009 - Proceedings of the International Conference on Agents and Artificial Intelligence, Porto, Portugal, January 19, 2009
Combinatorial Queries and Updates on Partial Words.
Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009
Filter Position in Networks of Evolutionary Processors Does Not Matter: A Direct Proof.
Proceedings of the DNA Computing and Molecular Programming, 15th International Conference, 2009
Some Remarks on Superposition Based on Watson-Crick-Like Complementarity.
Proceedings of the Developments in Language Theory, 13th International Conference, 2009
2008
On the Descriptional Complexity of Accepting Networks of Evolutionary Processors with Filtered Connections.
Int. J. Found. Comput. Sci., 2008
2007
Erratum to: "Accepting networks of splicing processors: Complexity results" [Theoret. Comput. Sci. 371(2007) 72-82].
Theor. Comput. Sci., 2007
Accepting networks of splicing processors: Complexity results.
Theor. Comput. Sci., 2007
Freeness of partial words.
Theor. Comput. Sci., 2007
On the size complexity of universal accepting hybrid networks of evolutionary processors.
Math. Struct. Comput. Sci., 2007
Accepting Networks of Evolutionary Processors with Filtered Connections.
J. Univers. Comput. Sci., 2007
All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size.
Inf. Process. Lett., 2007
On the recognition of context-free languages using accepting hybrid networks of evolutionary processors.
Int. J. Comput. Math., 2007
A Generalization of the Assignment Problem, and its Application to the Rank Aggregation Problem.
Fundam. Informaticae, 2007
Accepting Networks of Splicing Processors with Filtered Connections.
Proceedings of the Machines, Computations, and Universality, 5th International Conference, 2007
On the syllabification of words via go-through automata.
Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007
Hairpin Completion Versus Hairpin Reduction.
Proceedings of the Computation and Logic in the Real World, 2007
2006
An efficient approach for the rank aggregation problem.
Theor. Comput. Sci., 2006
Synchronized Shuffle on Backbones.
Fundam. Informaticae, 2006
All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006
2005
Parsing Local Internal Contextual Languages with Context-Free Choice.
Fundam. Informaticae, 2005
A Universal Accepting Hybrid Network of Evolutionary Processors.
Proceedings of the First International Workshop on Developments in Computational Models, 2005
Timed Accepting Hybrid Networks of Evolutionary Processors.
Proceedings of the Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach: First International Work-Conference on the Interplay Between Natural and Artificial Computation, 2005
Accepting Networks of Splicing Processors.
Proceedings of the New Computational Paradigms, 2005
2004
Solving 3CNF-SAT and HPP in Linear Time Using WWW.
Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004