java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/string_concat-noarr.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:37:45,658 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:37:45,661 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:37:45,678 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:37:45,679 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:37:45,680 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:37:45,682 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:37:45,684 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:37:45,686 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:37:45,687 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:37:45,689 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:37:45,689 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:37:45,690 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:37:45,691 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:37:45,692 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:37:45,696 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:37:45,698 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:37:45,699 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:37:45,701 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:37:45,702 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:37:45,703 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:37:45,706 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:37:45,706 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:37:45,706 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:37:45,707 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:37:45,708 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:37:45,709 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:37:45,709 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:37:45,711 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:37:45,711 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:37:45,711 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:37:45,712 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:37:45,712 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:37:45,713 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:37:45,714 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:37:45,714 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:37:45,734 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:37:45,734 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:37:45,735 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:37:45,735 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:37:45,736 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:37:45,736 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:37:45,737 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:37:45,742 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:37:45,742 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:37:45,742 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:37:45,743 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:37:45,743 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:37:45,743 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:37:45,743 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:37:45,744 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:37:45,744 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:37:45,744 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:37:45,744 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:37:45,744 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:37:45,746 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:37:45,746 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:37:45,805 INFO ]: Repository-Root is: /tmp [2018-06-22 15:37:45,820 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:37:45,823 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:37:45,825 INFO ]: Initializing SmtParser... [2018-06-22 15:37:45,825 INFO ]: SmtParser initialized [2018-06-22 15:37:45,826 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/string_concat-noarr.c.smt2 [2018-06-22 15:37:45,827 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:37:45,924 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/string_concat-noarr.c.smt2 unknown [2018-06-22 15:37:46,195 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/string_concat-noarr.c.smt2 [2018-06-22 15:37:46,200 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:37:46,206 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:37:46,207 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:37:46,207 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:37:46,207 INFO ]: ChcToBoogie initialized [2018-06-22 15:37:46,210 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,259 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46 Unit [2018-06-22 15:37:46,259 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:37:46,260 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:37:46,260 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:37:46,260 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:37:46,283 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,283 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,290 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,291 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,294 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,295 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,296 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... [2018-06-22 15:37:46,298 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:37:46,299 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:37:46,299 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:37:46,299 INFO ]: RCFGBuilder initialized [2018-06-22 15:37:46,299 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:37:46,319 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:37:46,319 INFO ]: Found specification of procedure False [2018-06-22 15:37:46,319 INFO ]: Found implementation of procedure False [2018-06-22 15:37:46,319 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:37:46,319 INFO ]: Found specification of procedure state [2018-06-22 15:37:46,319 INFO ]: Found implementation of procedure state [2018-06-22 15:37:46,319 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:37:46,319 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:37:46,319 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:37:46,477 INFO ]: Using library mode [2018-06-22 15:37:46,478 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:37:46 BoogieIcfgContainer [2018-06-22 15:37:46,478 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:37:46,479 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:37:46,479 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:37:46,482 INFO ]: TraceAbstraction initialized [2018-06-22 15:37:46,482 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:37:46" (1/3) ... [2018-06-22 15:37:46,483 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d53558e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:37:46, skipping insertion in model container [2018-06-22 15:37:46,483 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:46" (2/3) ... [2018-06-22 15:37:46,483 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d53558e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:37:46, skipping insertion in model container [2018-06-22 15:37:46,483 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:37:46" (3/3) ... [2018-06-22 15:37:46,485 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:37:46,494 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:37:46,504 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:37:46,542 INFO ]: Using default assertion order modulation [2018-06-22 15:37:46,542 INFO ]: Interprodecural is true [2018-06-22 15:37:46,542 INFO ]: Hoare is false [2018-06-22 15:37:46,542 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:37:46,543 INFO ]: Backedges is TWOTRACK [2018-06-22 15:37:46,543 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:37:46,543 INFO ]: Difference is false [2018-06-22 15:37:46,543 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:37:46,543 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:37:46,556 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:37:46,566 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:37:46,566 INFO ]: Found error trace [2018-06-22 15:37:46,569 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:46,569 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:46,575 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:37:46,577 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:46,577 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:46,614 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:46,614 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:46,614 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:46,639 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:46,786 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:37:46,789 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:37:46,789 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:37:46,790 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:37:46,806 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:37:46,806 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:37:46,808 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:37:46,880 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:46,880 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:37:46,880 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:37:46,882 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:37:46,882 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:46,892 INFO ]: With dead ends: 13 [2018-06-22 15:37:46,892 INFO ]: Without dead ends: 13 [2018-06-22 15:37:46,894 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:37:46,906 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:37:46,927 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:37:46,928 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:37:46,928 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:37:46,930 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:37:46,930 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:46,930 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:37:46,930 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:37:46,930 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:37:46,931 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:37:46,931 INFO ]: Found error trace [2018-06-22 15:37:46,931 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:46,932 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:46,932 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:37:46,932 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:46,932 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:46,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:46,933 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:46,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:46,973 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:47,271 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:37:47,271 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:47,271 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:47,283 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:47,348 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:47,363 INFO ]: Computing forward predicates... [2018-06-22 15:37:47,577 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:37:47,614 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:47,614 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:37:47,615 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:37:47,615 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:37:47,615 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:37:47,616 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:37:47,829 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:47,830 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:37:47,830 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:37:47,831 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:37:47,831 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:47,831 INFO ]: With dead ends: 15 [2018-06-22 15:37:47,831 INFO ]: Without dead ends: 15 [2018-06-22 15:37:47,832 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:37:47,832 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:37:47,837 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:37:47,837 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:37:47,837 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:37:47,837 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:37:47,838 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:47,838 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:37:47,838 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:37:47,838 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:37:47,838 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:37:47,838 INFO ]: Found error trace [2018-06-22 15:37:47,838 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:47,838 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:47,839 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:37:47,841 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:47,841 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:47,842 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:47,842 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:47,842 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:47,905 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:48,534 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:37:48,544 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:37:48,544 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:48,544 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:48,555 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:37:48,632 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:37:48,632 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:48,635 INFO ]: Computing forward predicates... [2018-06-22 15:37:49,113 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:37:49,149 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:49,149 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 15:37:49,149 INFO ]: Interpolant automaton has 8 states [2018-06-22 15:37:49,149 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 15:37:49,150 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 15:37:49,150 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-22 15:37:49,910 WARN ]: Spent 430.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 18 [2018-06-22 15:37:50,020 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:50,020 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:37:50,022 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:37:50,022 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 15:37:50,022 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:50,023 INFO ]: With dead ends: 17 [2018-06-22 15:37:50,023 INFO ]: Without dead ends: 17 [2018-06-22 15:37:50,024 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:37:50,024 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:37:50,031 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:37:50,031 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:37:50,031 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:37:50,032 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:37:50,032 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:50,032 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:37:50,032 INFO ]: Interpolant automaton has 8 states. [2018-06-22 15:37:50,032 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:37:50,032 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:37:50,033 INFO ]: Found error trace [2018-06-22 15:37:50,033 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:50,033 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:50,033 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:37:50,033 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:50,033 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:50,035 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:50,035 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:50,035 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:50,076 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:50,294 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 15:37:50,652 WARN ]: Spent 313.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:37:50,758 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:37:50,758 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:50,758 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:50,770 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:37:50,833 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:37:50,833 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:50,836 INFO ]: Computing forward predicates... [2018-06-22 15:37:51,077 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:37:51,109 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:51,109 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 15:37:51,110 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:37:51,110 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:37:51,110 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:37:51,110 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-22 15:37:51,357 WARN ]: Spent 188.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 29 [2018-06-22 15:37:51,633 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:51,633 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:37:51,634 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:37:51,634 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 15:37:51,635 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:51,635 INFO ]: With dead ends: 19 [2018-06-22 15:37:51,635 INFO ]: Without dead ends: 19 [2018-06-22 15:37:51,635 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:37:51,636 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:37:51,639 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:37:51,639 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:37:51,639 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:37:51,639 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:37:51,640 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:51,640 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:37:51,640 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:37:51,640 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:37:51,640 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:37:51,640 INFO ]: Found error trace [2018-06-22 15:37:51,640 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:51,641 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:51,641 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:37:51,641 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:51,641 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:51,642 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:51,642 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:51,642 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:51,671 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:51,988 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:37:51,988 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:51,988 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:52,001 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:37:52,028 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:37:52,028 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:52,032 INFO ]: Computing forward predicates... [2018-06-22 15:38:03,504 WARN ]: Spent 10.02 s on a formula simplification. DAG size of input: 1416 DAG size of output: 11 [2018-06-22 15:38:04,877 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:38:04,907 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:04,907 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 15 [2018-06-22 15:38:04,908 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:38:04,908 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:38:04,908 INFO ]: CoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:38:04,908 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 15 states. [2018-06-22 15:38:05,425 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 34 [2018-06-22 15:38:06,136 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 25 [2018-06-22 15:38:06,266 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:06,266 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:38:06,269 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:38:06,269 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-22 15:38:06,269 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:06,270 INFO ]: With dead ends: 21 [2018-06-22 15:38:06,270 INFO ]: Without dead ends: 21 [2018-06-22 15:38:06,270 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 20 SyntacticMatches, 3 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 12.3s TimeCoverageRelationStatistics Valid=103, Invalid=277, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:38:06,270 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:38:06,274 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:38:06,274 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:38:06,275 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:38:06,275 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:38:06,275 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:06,275 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:38:06,275 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:38:06,275 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:38:06,276 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:38:06,276 INFO ]: Found error trace [2018-06-22 15:38:06,276 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:06,276 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:06,276 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:38:06,276 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:06,276 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:06,278 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:06,278 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:06,278 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:06,329 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:06,776 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 33 [2018-06-22 15:38:06,942 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:38:06,942 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:06,942 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:38:06,958 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:38:07,078 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:38:07,078 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:07,082 INFO ]: Computing forward predicates... [2018-06-22 15:38:07,468 WARN ]: Spent 213.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 9 [2018-06-22 15:38:07,803 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 27 [2018-06-22 15:38:08,273 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:38:08,297 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:08,297 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:38:08,298 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:38:08,298 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:38:08,299 INFO ]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:38:08,299 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:38:08,538 WARN ]: Spent 189.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 43 [2018-06-22 15:38:08,944 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 27 [2018-06-22 15:38:09,140 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 34 [2018-06-22 15:38:09,331 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 42 [2018-06-22 15:38:09,355 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:09,355 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:38:09,355 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:38:09,355 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:38:09,356 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:09,356 INFO ]: With dead ends: 23 [2018-06-22 15:38:09,356 INFO ]: Without dead ends: 23 [2018-06-22 15:38:09,357 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=151, Invalid=449, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:38:09,357 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:38:09,360 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:38:09,360 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:38:09,361 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:38:09,361 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:38:09,361 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:09,361 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:38:09,361 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:38:09,361 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:38:09,362 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:38:09,362 INFO ]: Found error trace [2018-06-22 15:38:09,362 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:09,362 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:09,362 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:38:09,362 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:09,362 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:09,363 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:09,363 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:09,363 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:09,429 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:09,815 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 20 [2018-06-22 15:38:10,091 WARN ]: Spent 180.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-22 15:38:10,425 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:38:10,425 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:10,425 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:38:10,435 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:38:10,483 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:38:10,483 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:10,487 INFO ]: Computing forward predicates... [2018-06-22 15:38:18,918 WARN ]: Spent 7.58 s on a formula simplification. DAG size of input: 1258 DAG size of output: 46 [2018-06-22 15:38:19,271 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 30 [2018-06-22 15:38:19,459 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 27 [2018-06-22 15:38:20,308 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:38:20,337 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:20,337 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-22 15:38:20,337 INFO ]: Interpolant automaton has 29 states [2018-06-22 15:38:20,337 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 15:38:20,338 INFO ]: CoverageRelationStatistics Valid=128, Invalid=684, Unknown=0, NotChecked=0, Total=812 [2018-06-22 15:38:20,338 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-22 15:38:21,014 WARN ]: Spent 639.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 85 [2018-06-22 15:38:21,183 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 25 [2018-06-22 15:38:21,408 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 31 [2018-06-22 15:38:21,723 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 28 [2018-06-22 15:38:21,971 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 35 [2018-06-22 15:38:22,385 WARN ]: Spent 386.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 38 [2018-06-22 15:38:22,669 WARN ]: Spent 249.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 58 [2018-06-22 15:38:22,702 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:22,702 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:38:22,703 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:38:22,703 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-22 15:38:22,705 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:22,705 INFO ]: With dead ends: 25 [2018-06-22 15:38:22,705 INFO ]: Without dead ends: 25 [2018-06-22 15:38:22,706 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 12.0s TimeCoverageRelationStatistics Valid=265, Invalid=995, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 15:38:22,706 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:38:22,709 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:38:22,709 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:38:22,710 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:38:22,710 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:38:22,710 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:22,710 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:38:22,710 INFO ]: Interpolant automaton has 29 states. [2018-06-22 15:38:22,710 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:38:22,711 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:38:22,711 INFO ]: Found error trace [2018-06-22 15:38:22,711 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:22,711 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:22,711 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:38:22,711 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:22,711 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:22,712 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:22,712 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:22,712 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:22,762 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:23,977 WARN ]: Spent 989.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 16 [2018-06-22 15:38:25,411 WARN ]: Spent 1.36 s on a formula simplification. DAG size of input: 36 DAG size of output: 36 [2018-06-22 15:38:25,671 WARN ]: Spent 157.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 35 [2018-06-22 15:38:26,262 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:38:26,262 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:26,262 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:38:26,278 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:38:26,326 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:26,331 INFO ]: Computing forward predicates... [2018-06-22 15:38:36,056 WARN ]: Spent 8.93 s on a formula simplification. DAG size of input: 1236 DAG size of output: 15 [2018-06-22 15:38:37,050 WARN ]: Spent 959.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 62 [2018-06-22 15:38:37,458 WARN ]: Spent 331.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 46 [2018-06-22 15:38:37,609 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 32 [2018-06-22 15:38:37,869 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 Received shutdown request... [2018-06-22 15:38:51,390 INFO ]: Timeout while computing interpolants [2018-06-22 15:38:51,591 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:38:51,591 WARN ]: Verification canceled [2018-06-22 15:38:51,595 WARN ]: Timeout [2018-06-22 15:38:51,595 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:38:51 BoogieIcfgContainer [2018-06-22 15:38:51,595 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:38:51,595 INFO ]: Toolchain (without parser) took 65394.63 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 255.4 MB in the beginning and 1.1 GB in the end (delta: -870.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 15:38:51,596 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:38:51,596 INFO ]: ChcToBoogie took 53.05 ms. Allocated memory is still 303.0 MB. Free memory was 254.4 MB in the beginning and 252.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:51,597 INFO ]: Boogie Preprocessor took 37.91 ms. Allocated memory is still 303.0 MB. Free memory was 252.4 MB in the beginning and 251.4 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:51,597 INFO ]: RCFGBuilder took 179.03 ms. Allocated memory is still 303.0 MB. Free memory was 251.4 MB in the beginning and 242.4 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:51,598 INFO ]: TraceAbstraction took 65115.79 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 242.4 MB in the beginning and 1.1 GB in the end (delta: -883.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 15:38:51,602 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.05 ms. Allocated memory is still 303.0 MB. Free memory was 254.4 MB in the beginning and 252.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 37.91 ms. Allocated memory is still 303.0 MB. Free memory was 252.4 MB in the beginning and 251.4 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 179.03 ms. Allocated memory is still 303.0 MB. Free memory was 251.4 MB in the beginning and 242.4 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 65115.79 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 242.4 MB in the beginning and 1.1 GB in the end (delta: -883.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 0 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 65.0s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 6.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 83 SDtfs, 147 SDslu, 323 SDs, 0 SdLazy, 276 SolverSat, 184 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 226 GetRequests, 117 SyntacticMatches, 8 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 344 ImplicationChecksByTransitivity, 29.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 28.4s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 29 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 241116 SizeOfPredicates, 222 NumberOfNonLiveVariables, 942 ConjunctsInSsa, 216 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/string_concat-noarr.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-38-51-620.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/string_concat-noarr.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-38-51-620.csv Completed graceful shutdown